Úloha 5.u3: Rubikova kostka (4 b)

Zadáno v čísle 24.5.

Řešeno v čísle 24.7.

Zadání

Rubikova kostka se rozpadla a zbylo z ní 26 barevných dílků. My nevíme, jak byla předtím obarvena, ani jaké barvy k tomu byly použity. Kolik nejméně těchto dílků potřebujeme, abychom na jejich základě byli schopni její obarvení zrekonstruovat (určit barvy a jejich rozložení na složené kostce)? Kolik takových dílků potřebujeme, máme-li k dispozici pouze její rohové dílky? A co v případě, že naopak rohové dílky k dispozici vůbec nemáme?

Řešení

V zadání této úlohy se vyskytla jistá nejednoznačnost. Úloha byla původně myšlena tak, že cílem je najít minimální počet dílků, který při vhodném výběru už může stačit na jednoznačné stanovení původního obarvení. Většina řešení se držela tohoto zadání, ovšem nabízel se zde ještě jiný výklad, a sice hledání počtu dílků, které mi budou ke stanovení obarvení určitě stačit, ať už je můj výběr jakýkoli. Tato verze úlohy byla o něco obtížnější než ta původní, proto byli její řešitelé odměněni bonusovými body. Vzorové řešení se však bude vztahovat k původní verzi.

Rozdělme si úlohu na tři situace dle toho, z jakých dílků můžeme vybírat: 1. všechny dílky, 2. pouze rohové dílky, 3. pouze nerohové dílky.

  1. Je zřejmé, že paletu barev použitých k obarvení kostky nelze stanovit s využitím méně než dvou dílků. Dále je zřejmé, že se dvěma dílky to provést lze právě tehdy, jsou-li to rohové dílky v protilehlých rozích, také že v této situaci však ještě není jednoznačné rozmístění barev a že toto rozmístění už je jednoznačné za přítomnosti libovolného dalšího rohového dílku. Ke stanovení původního obarvení kostky v první otázce v zadání nám tedy stačí vhodný výběr tří dílků.

  2. Protože v předchozí části úlohy nebylo třeba nerohových dílků, řešení v této situaci představují opět tři rohové dílky.

  3. Uvědomme si, že bez rohových dílků jsme schopni o každé stěně získat pouze informaci, s kterými dalšími stěnami sousedí. Předpokládejme, že jsme nalezli obarvení kostky, které lze zkonstruovat z dílků, které máme k dispozici. Nyní vyměňme barvy dvou protilehlých stěn. Tím jsme získali nové obarvení (nedá se z předchozího získat pouhým otáčením kostky), které stále vyhovuje podmínkám daným dostupnými dílky, neboť každá stěna stále sousedí právě s těmi stěnami, s nimiž sousedila předtím. Tedy bez ohledu na to, kolik nerohových dílků použijeme, vždy existují alespoň dvě neekvivalentní obarvení, která obě souhlasí se všemi danými podmínkami. Bez použití rohových dílků tudíž nikdy nelze obarvení kostky zrekonstruovat jednoznačně.

Ve složitější verzi úlohy (viz první odstavec) je při využití všech dílků kostky potřeba vytáhnout alespoň 19 dílků, při využití pouze rohových dílků je potřeba alespoň 5 dílků a bez rohových dílků obarvení pochopitelně opět zrekonstruovat nelze.

Evžen