MA0002 — řešení DÚ č. 11
Cvičení 11.1 Potřebujeme převézt přes řeku kozu, vlka a zelí v loďce, která
uveze pouze převozníka a jednu z „věcí“. Jak to můžeme udělat, aby vlk nesežral
kozu a koza zelí?
Řešení:
Velice známá úloha s množstvím obměn lze řešit dle následující tabulky, kde
vlk je značen V, koza K a zelí Z:
1. břeh loď 2. břeh
VZ → K –
VZ ← K
V → Z K
V ← K Z
K → V Z
K ← VZ
– → K VZ
Cvičení 11.2 Máme plnou 12 l nádobu a dvě prázdné nádoby – 7 l a 4 l.
Přeléváním rozdělte vodu tak, aby ve dvou nádobách bylo 6 l vody.
Řeěení:
Řešení je opět zadáno tabulkou objemů tekutiny v nádobách, v záhlaví jsou
uvedeny objemy nádob.
12 l 7 l 4 l
12 – –
5 7 –
5 3 4
9 3 –
9 – 3
2 7 3
2 6 4
6 6 –
Cvičení 11.3 (*) Adam, Bedřich a Cyril mají skleničky s obsahem 5 dl, 3 dl
a 2 dl. Na začátku jsou v Adamově skleničce 4 dl, zbylé dvě jsou prázdné. Jak
je potřeba přelít víno tak, aby Adam měl ve své skleničce 2 dl a Bedřich a Cyril
každý 1 dl?
118
Řešení:
Tuto úlohu je možné vyřešit pouze za předpokladu, že si Adam s Cyrilem
vymění skleničky, pokud bychom totiž získali 2 dl vína v Adamově skleničce,
nejsme schopni rozlít Bedřichovi a Cyrilovi po 1 dl. Řešení s vyměněnými
skleničkami je následující:
Adam (5 dl) Bedřich (3 dl) Cyril (2 dl)
4 – –
1 3 –
1 1 2
Cvičení 11.4 Tři misionáři a tři lidožrouti se potřebují přepravit přes řeku
na dvoumístné loďce. Je nežádoucí, aby se na některém břehu ocitlo více lidožroutů
než misionářů. Loďka sama nepopluje. Zorganizujte přepravu.
Řešení:
Vycházíme ze skutečnosti, že na lodi nejsou lidožrouti sami sobě nebezpeční,
protože musí pádlovat (mohou spolu plout i dva lidožrouti). Řešení je znázorněno
v tabulce.
1. břeh loď 2. břeh
MMLL → ML –
MMLL ← L M
MML → LL M
MML ← L ML
ML → ML ML
ML ← L MML
M → LL MML
M ← L MMLL
– → ML MMLL
Cvičení 11.5 Manželé Adamcovi byli na večírku s dalšími třemi manželskými
páry. Zdravili se podáním ruky. Nikdo nepodal ruku sám sobě, svému
partnerovi ani víckrát téže osobě. Když to skončilo, tak se pan Adamec zeptal,
kolikrát kdo podal ruku. Od každého dostal jinou odpověď. Kolika lidem
podala ruku paní Adamcová?
Řešení:
Na večírku jsou čtyři páry, jestliže si nikdo nepodal ruku se svým partnerem,
mohl každý podat ruku nejvýše šesti lidem. Pan Adamec získal 7 různých
odpovědí, musely to být odpovědi 0, 1, . . . 6.
Osoba X1 si potřásla rukou s 6 osobami a nepotřásla si rukou pouze se svým
doprovodem X2. Jelikož si všichni kromě X2 potřásli rukou s X1, pouze
osoba X2 mohla panu Adamcovi odpovědět, že si s nikým rukou nepotřásla.
Tím máme vysvětlenou zelenou část obrázku níže, body X1, X2 už s žádnými
dalšími propojovat nebudeme.
Nazvěme Y1 osobu, která si potřásla rukou s 5 přáteli. Nemohla si potřást
rukou s X2 ani se svým doprovodem Y2, se všemi ostatními si rukou potřásla,
což máme v obrázku vyznačeno oranžovou barvou. Všechny osoby
119
mimo X1, X2, Y1, Y2 si již podle obrázku podali ruku právě se dvěma osobami,
proto jedině osoba Y2, mohla říci, že podala ruku pouze jedné osobě.
Tím máme vysvětlenou i oranžovou část obrázku.
Dále si pojmenujme osobu jež přivítala 4 přátele Z1. Ta si musela potřást
rukou ještě se dvěma ze zbývajících tří osob – osoba, se kterou si rukou nepotřásla,
musí být její doprovod Z2. Zbývá nám tedy osoba Z2, která uvítala
2 přátele, a dvě zbylé osoby, které obě uvítali právě 3 přátele. Protože panu
Adamcovi odpověděl každý jinak, musí být právě zbývající dvě osoby Adam-
covi.
Paní Adamcová podala ruku 3 osobám.
Cvičení 11.6 (*) Sedm kamarádů se před prázdninami dohodlo, že každý
pošle pohled 3 kamarádům tak, aby každý poslal pohled tomu, od kterého pohled
dostal nebo dostane. Navrhněte, kdo bude komu posílat pohlednice, aby
byla podmínka splněna.
Řešení:
Když každý pošle 3 pohledy, bude dohromady odesláno 7 · 3 = 21 pohledů.
Odešle-li osoba A pohled osobě B, musí i osoba B odeslat pohled osobě A.
Proto je počet „poštovních tras“ roven polovině poslaných pohledů, to však
není možné.
Plán sedmi kamarádů nelze uskutečnit.
Cvičení 11.7 V klubu hádankářů mají deset pater. Ve výtahu jsou tlačítka
+3; −4; : 2.
(a) Lze se z libovolného patra dostat do jiného libovolného patra?
(b) Kolikrát zmáčkneme knoflík pro cestu z pátého do devátého patra?
Řešení:
(a) Abychom zajistili možnost dostat se z libovolného patra do jiného libovolného
patra, stačí vytvořit posloupnost pater začínající i končící
stejným patrem, v níž získáme pomocí operací na tlačítkách všechna
patra od 1 do 10 (vytvoříme „kružnici“, po které se můžeme dostat
z jakéhokoli bodu do jakéhokoli bodu). Začněme například v prvním
patře:
1 + 3 → 4 : 2 → 2 + 3 → 5 + 3 → 8 : 2 → 4 + 3 → 7 + 3 → 10 − 4 →
6 : 2 → 3 + 3 → 6 + 3 → 9 − 4 → 5 − 4 → 1
Z libovolného patra se lze dostat do jiného libovolného
patra.
(b) Využijeme vytvořené posloupnosti, přičemž z šestého patra budeme
cestovat rovnou do devátého patra.
5 + 3 → 8 : 2 → 4 + 3 → 7 + 3 → 10 − 4 → 6 + 3 → 9
Z pátého do devátého patra se lze dostat pomocí šesti stisknutí
tlačítek.
120
Cvičení 11.8 (*) Hostitel pořádá každý den v týdnu večeři pro své přátele.
Každý den pozve tři hosty. Jak může během týdne pozvat svých (a) 7;
(b) 15 přátel tak, aby se každí dva z nich potkali alespoň jednou, případně
právě jednou?
Řešení:
(a) Pojmenujme si hosty Aleš, Bára, Cecil, Dana, Emil, Fábio a Gabriela
(dále budeme užívat pouze jejich počáteční písmena). Hosty můžeme
pozvat například podle tabulky níže, kdy se každý host s každým potká
právě jednou.
Po Út St Čt Pá So Ne
A A A B C B C
B D F D E E D
C E G F F G G
(b) K hostům pozvaným z předchozí varianty ještě přidáme Helenu, Ivana,
Janu, Karla, Ludmilu, Marka, Nikolu a Ondru. Jelikož v předchozí
variantě bylo o 8 osob méně a podařilo se nám je sezvat takovým
způsobem, že se každý s každým potkal právě jednou (kdyby se někteří
potkali více než jednou, jiní by se nepotkali vůbec), je jen logické, že
se nám to u 15 osob nepodaří. Pokud bychom se problémem zabývali
hlouběji, došli bychom k závěru, že právě jednou by se každý s každým
potkal v případě, že by byl hostitel extrémně pohostinný a zval by
trojice hostů celý týden na 5 jídel denně.
121