5. príklad - Vzorové riešenie

Kategórie:
5
6
7
8
9

Zadanie

Máme dve 30 \, \text{ml} fľaše, v ktorých sa vždy objem elixíru pravdy (veritaserum) zaokrúhľuje:
  1. V prvej fľaši na najbližší menší alebo rovný násobok 2 \, \text{ml}.
  2. V druhej fľaši na najbližší násobok 3 \, \text{ml}.
Prvá (ktorá zaokrúhľuje na 2 \, \text{ml}) je plná elixíru, a druhá je prázdna. My môžeme preliať ľubovoľný celý počet ml z jednej fľaše do druhej koľkokrát chceme, a vždy sa v nich hneď ako prelievanie dokončíme objem zaokrúli podľa pravidiel. Koľko najviac ml elixíru vieme mať dokopy vo fľašiach a ako by sme mali prelievať, aby sme to dosiahli iba prelievaním medzi dvoma fľašami, ktoré máme k dispozícií? Nezabudnite ukázať, že viac elixíru vo fľašiach určite nemôže byť.

Vzorové riešenie

Opravovali: Danko, Peter, maria

Pozrime sa najprv na to, ako vôbec môžeme preliatím získať viac vody. Zo zadania je zrejmé, že v 1. fľaši sa objem nikdy nezaokrúhli na vyššie číslo. Celkový objem vody teda musíme zväčšovať zaokrúhľovaním v 2. fľaši. V nej môže po preliatí zostať rôzny objem, nás však zaujíma iba jeho zvyšok po delení tromi. Rozoberieme teda všetky tri možnosti.

Keď prelejeme číslo deliteľné 3, tak objem v 2. fľaši sa nebude na nič zaokrúhľovať, objem v nej zostane násobkom 3.

Ak prelievame objem, ktorý má zvyšok 1 po delení tromi, teda je o 1 väčší ako násobok 3, tak pri prelievaní z 1. fľaše do 2 sa nám objem v 2. fľaši zaokrúhlením zmenší o 1. Ak však prelievame takýto objem z 2. fľaše do 1., tak sa nám objem v 2. fľaši zväčší naspäť o 1, keďže ubudlo o 1 viac ako násobok 3. Ak sa nám ešte podarí, aby bol prelievaný objem párny, nestratíme vodu zaokrúhľovaním v 1. fľaši a celkový objem sa zväčší o 1.

Ak pracujeme s objemom so zvyškom 2, teda o 1 menším ako násobok 3, tak sa po odliatí do 2. fľaše zaokrúhli nahor. Opäť ak to bude zároveň aj párne číslo, nestratíme vodu zaokrúhľovaním nadol v 1. fľaši a celkový objem sa zväčší o 1. Opačným preliatím vodu nezískame, keďže nám v 2. fľaši ostane objem, ktorý sa zaokrúhli nadol.

Vidíme teda teraz, že po jednom preliatí sa nám môže objem zväčšiť maximálne o 1, keď odlievame z 2. fľaše párne číslo o 1 väčšie ako násobok 3 (4,10,\ldots) alebo keď do nej prilievame párne číslo o 2 väčšie ako násobok 3 (2,8,\ldots).

Teraz už poďme skúsiť prelievať, a uvidíme, kam sa dostaneme. Skúsime čo najviac využívať, že vieme preliať 2 ml do 2. fľaše a získať pri tom vodu. Začíname s 30 ml vody, vždy prelievame po 2 ml, a keď sa nám voda minie, prelejeme si čo najviac naspäť:

  1. 10-krát prelejeme 2 ml z 1. fľaše do 2. fľaše. Vo fľašiach máme 10 ml a 30 ml.
  2. Prelejeme 20 ml z fľaše 2 do 1 vo fľašiach máme 30 a 9 ml.
  3. 7-krát prelejeme 2 ml z fľaše 1 do fľaše 2. Vo fľašiach máme 16 ml a 30 ml.
  4. Prelejeme 14 ml z 2. fľaše do 1. vo fľašiach máme 30 a 15 ml.
  5. 5-krát prelejeme 2 ml z 1. fľaše do 2. Vo fľašiach máme 20 ml a 30 ml.
  6. Prelejeme 10 ml z 2. fľaše do 1. Vo fľašiach máme 30 a 21 ml.
  7. 3-krát prelejeme 2 ml z 1. fľaše do 2. fľaše. Vo fľašiach máme 24 ml a 30 ml.
  8. Prelejeme 6 ml z 2. fľaše do 1. vo fľašiach máme 30 a 24 ml.
  9. 2-krát prelejeme 2 ml z 1. fľaše do 2. fľaše. Vo fľašiach máme 26 ml a 30 ml
  10. Prelejeme 4 ml z 2. fľaše do 1. Vo fľašiach máme 30 a 27 ml.
  11. Prelejeme 2 ml z 1. fľaše do 2. fľaše. Vo fľašiach máme 28 ml a 30 ml, spolu 58 ml.

Ani po dlhšom snažení sa nám nepodarí dosiahnuť väčší objem. Pokúsime sa teda ukázať, že sme naozaj dosiahli maximum, ako to vyžaduje zadanie. Keďže po každom preliatí vieme zväčšiť množstvo vody najviac o 1 ml vieme, že krok pred tým ako zväčšíme objem na nejaké čislo, museli sme ho tesne predtým mať o 1 menší, a niekedy pred tým ešte o 1 menší až po 30 ml. Teda ak by sme chceli dosiahnuť 60 ml, museli by sme pred tým vo fľašiach mať 59 ml. Vo fľašiach ale 59 ml nemôžeme mať, pretože jediný spôsob ako to dosiahnuť by bol, že v jednej z fľaší je 29 ml s v druhej 30. 29 ale nie je deliteľné 2 ani 3, a teda by sa v v oboch fľašiach zaokrúhlilo. Nevieme teda dosiahnuť 59 ani 60 ml, a našich dosiahnutých 58 ml je naozaj najviac.

Odpoveď: Najviac vieme dosiahnuť 58 ml vody, napríklad spôsobom ako je popísané v riešení.

Komentár

Skoro všetkým riešiteľom sa úspešne podarilo nájsť postup, akým dostaneme 58 ml elixíru, a aj ukázali, že ďalším prelievaním z tohto stavu viac elixíru nedostaneme. To, žiaľ, nie je dôkaz, že viac elixíru nedostaneme, ak budeme prelievať úplne iným spôsobom. Napríklad by bolo treba ukázať, prečo nevieme dostať 59 alebo 60 ml jedným preliatím z iného stavu, napríklad s iným objemom elixíru.