4. Procvičování / Přelévání mléka
Úloha [15]
Mlékařka má osm litrů mléka ve dvou nádobách, pětilitrové a třílitrové, zapomněla si však dnes litrovou odměrku.
Přichází zákaznice s dvoulitrovou nádobou, ale žádá jen litr mléka.
Může mlékařka najít postup, jak odměřit do dvoulitrové nádoby jeden litr mléka, smí-li použít jen přelévání mezi těmito třemi nádobami?
Pokud ano, popište postup.
Pokud ne, zdůvodněte, proč ne.
Nápověda
Použijte podobný princip jako v úloze o převozníkovi - zakreslete si všechna možná množství mléka v nádobách (na každém vrcholu tedy bude údaj ve tvaru (x,y,z) - x litrů mléka v pětilitrové nádobě, y litrů v třílitrové a z litrů v dvoulitrové). V tomto grafu pak budeme hledat vhodnou cestu.
Řešení
Všechny možnosti rozlití mléka si zakreslíme jako vrcholy grafu. Na každém vrcholu budou vždy tři čísla - počet mléka v první nádobě, druhé a třetí (zvolíme si například pořadí "pětilitrová, třílitrová, dvoulitrová").
Pokud se z jednoho vrcholu dokážeme dostat do druhého, zakreslíme mezi vrcholy hranu.
Rozepíšeme si tedy všechny možné stavy - v součtu dávají 8 litrů (množství mléka, které má mlékařka k dispozici) a v každé nádobě je maximálně tolik mléka, kolik se tam vejde (vrchol (6,1,1) nepadá v úvahu, protože první nádoba má kapacitu 5 litrů).
Všechny stavy:
(5,3,0), (5,2,1), (5,1,2), (4,3,1), (4,2,2), (3,3,2)
Proč budou hrany grafu orientované?
Například ze stavu (4,2,2) se dokážeme dostat do (3,3,2) (z první nádoby budeme lít do druhé třílitrové). Zpět to však nejde, protože cestou zpět nedokážeme odměřit litr.
Jak vypadají v grafu všechny možnosti přelití mléka?
Co je pro nás hledaný výsledek?
Začínáme ve vrcholu (5,3,0) a hledáme cestu do vrcholů, které mají na posledním místě 1 (1 litr mléka má být nádobě, kterou si přinesla zákaznice), tedy (4,3,1) a (5,2,1).
Žádnou takovou cestu nenajdeme - tím jsme ukázali, že úloha nemá řešení.