Ostrov chameleonů [příspěvek v archivu]
Na jednom ostrově žije 45 chameleonů: 15 zelených, 17 žlutých a 13 oranžových. Když se potkají dva chameleoni různých barev (řekněme zelený a žlutý), změní oba barvu na tu třetí (zde tedy na oranžovou). Můžou skončit všichni se stejnou barvou?
Petr Staníček, 23. 5. 2008 000 16.20 • Rubrika: Mozkomor • 10 komentářů u textu s názvem Ostrov chameleonů
10 komentářů k článku »Ostrov chameleonů«
[1] Vložil(a): Hellish 23. 5. 2008 v 16.52
Tak já to zkusím.
Chameleoni nemůžou mít nikdy stejnou barvu. Aby se to povedlo, muselo by být možné utvořit ve dvou barevných skupinách stejný počet chameleonů (pak by se spárovali a přidali by se ke třetí barevné skupině).
Když se potkají dva chameleoni z různých barev, stanou se z nich dva chameleoni zbývající barvy. Tedy každým „tahem“ (setkáním dvou chameleonů) dvě skupiny oslábnou každá o jednoho chameleona a třetí získá dva nové. Takže každým „tahem“ se jedna skupina stane početnější o 3 chameleony vůči zbývajícím dvěma skupinám (dva chameleony získá zatímco ostatní jednoho ztratí). A tady je ten problém. Pokud máme výchozí skupiny, jejichž počet se liší o dva chameleony, a každým „tahem“ umíme jednu skupinu posílit o tři chameleony, nikdy nemůžeme vytvořit dvě stejně početné skupiny. A tedy není možné, aby nakonec měli všichni chameleoni stejnou barvu.
[2] Vložil(a): roj 25. 5. 2008 v 16.26
Hellish to myslim rekl zcela jasne, souhlasim.
[3] Vložil(a): Pixy 25. 5. 2008 v 17.32
Přesně tak. Potkají-li se chameloni A a B, přebarví se oba na C. Při každé změnětedy rozdíl mezi libovolnými dvěma druhy chamelonů:
Aby vůbec bylo možné provést eliminaci jedné barvy aspoň teoreticky, musí být proto počáteční rozdíl mezi dvěma barvami násobkem 3. Podotýkám jen, že 0 je taky násobkem tří, tedy nulový rozdíl (stejný počet) dvou barev k cíli vede také.
[4] Vložil(a): JT 26. 5. 2008 v 18.15
Jen bych doplnil, že eliminace jedné barvy je samozřejmě možná i za daných počátečních podmínek, minimální cesta je:
13 15 17
12 14 19
11 13 21
…
2 4 39
1 3 41
0 2 43
Dvě barvy ovšem eliminovat tímto způsobem nejdou.
[5] Vložil(a): Pixy 26. 5. 2008 v 20.19
[4] Což jde ještě minimalizovat:
…
0 2 43
2 1 42
1 0 44
[6] Vložil(a): JT 26. 5. 2008 v 21.46
[5] Jistě, náčelníku
To je ale řešení trošku jiného zadání, než
„eliminace jedné barvy“ (co nejmenším počtem kroků).
[7] Vložil(a): Hellish 27. 5. 2008 v 23.28
[4] – Eliminace jedné barvy je přeci možná za jakýchkoliv počátečních podmínek, takže řešení této „varianty“ ztrácí na zajímavosti ;)
[8] Vložil(a): Pixy 27. 5. 2008 v 23.49
[7] Ale no tak, proč jim to děláš?
[9] Vložil(a): Hellish 28. 5. 2008 v 14.31
[8] Já už jsem prostě takovej ;)
A tuhle znáte? href=„http://www.hellish.cz/weblog/proti-vetru“ rel=„nofollow ugc“>http://www.hellish.cz/weblog/proti-vetru
[10] Vložil(a): honzahucin 30. 5. 2008 v 10.47
Je to pěkná úloha, [1] a [3] to vysvětlují dost jasně, tak snad ještě exaktní formulace: cesta k tomu, aby všichni chameleoni měli nakonec stejnou barvu, existuje právě tehdy, pokud aspoň dvě skupiny splňují podmínku, že rozdíl počátečních počtů jejich členů je dělitelný třemi.
[3] Rozdíl se nemusí zvýšit o 3, ale i snížit o 3
Váš komentář
Upozornění: Pokud vás téma tohoto příspěvku nezajímá, nebaví, dotýká se vás či vás dokonce uráží, tak prosím odejděte a pokud možno se nadále ve vlastním zájmu dalším podobným vyhýbejte. Hlavně se to prosím nesnažte autorovi sdělovat v komentářích, takové příspěvky nikoho nezajímají a budou nejspíš vymazány. Totéž platí pro vaše názory na osobu autora, na jiné přispěvatele, mluvení z cesty, ze spaní či pod vlivem omamných látek a další podobné výlevy nesouvisející s tématem článku. Jinými slovy, toto je prostor soukromého blogu určený pro komentování příspěvku publikovaného výše, nikoli k chatování a volné diskusi. Děkuji za pochopení.
Abyste mohli komentovat, musíte se přihlásit.