Ostrov chameleonů

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?

10 komentářů u „Ostrov chameleonů“

  1. 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.

  3. 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ů:

    1. zůstane stejný – počet zástupců barev A a B klesl shodně o jednu
    2. zvýší se o 3 – při změně se počet zástupců A, resp. B snížil o jednu, zatímco počet C vzrostl o dva

    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. 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. [4] Což jde ještě minimalizovat:

    …
    0 2 43
    2 1 42
    1 0 44

    ;-) Ale dál už opravdu vlak nejede.

  6. [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. [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 ;)

  9. [8] Já už jsem prostě takovej ;)

    A tuhle znáte? href=„http://­www.hellish.cz/we­blog/proti-vetru“ rel=„nofollow ugc“>http://ww­w.hellish.cz/we­blog/proti-vetru

  10. 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 ;-)

Napsat komentář