4. príklad - Vzorové riešenie
Kategórie:
5
6
7
8
Zadanie
Okolo kruhového stola je 8 miest na sedenie. Škriatok postupne ukazuje na prázdne stoličky. Keď škriatok ukáže na prázdnu stoličku, tak sa jeden z ľudí sediacich na 2 susedných miestach musí presunúť na túto prázdnu stoličku. Ak vedľa nesedí žiaden človek, tak sa škriatok rozhnevá. Koľko najmenej ľudí musí sedieť za stolom, aby vedeli zaručiť, že sa škriatok nikdy nerozhnevá, nech ukazuje na ktorékoľvek miesta v akomkoľvek poradí? Ľudia si na začiatku môžu vybrať ako chcú sedieť.
Vzorové riešenie
Opravovali: AlenaChladna, Majko, Michal_P., ZuzkaK
Pozrime sa najskôr na to, kedy sa škriatok môže rozhnevať:
Uvedomíme si, že škriatok sa rozhnevá práve vtedy, keď vedľa seba sú 3 voľné stoličky, pretože škriatok môže ukázať na tú strednú z nich a rozhnevá sa.
Teraz sa pozrime na to, aké počty ľudí môžu byť za stolom:
Menej ako 3 ľudia za stolom nemôžu byť, lebo kedže máme 8 stoličiek, tak keď sa akokoľvek usadia 2 ľudia, tak určite budú existovať aspoň 2 stoličky, na ktoré sa nikto nevie presunúť.
Ak za stolom sedia 3 ľudia:
Jediné usadenie 3 ľudí tak, aby neboli hneď na začiatku tri po sebe prázdne miesta je takéto:
Stoličky si označíme od 1 po 8 ako na obrázku.
Ak by škriatok ukázal na stoličku jeden, tak sa tam musí premiestniť niekto zo stoličiek 2 alebo 8. Potom ale môžeme vidieť, že buď trojica miest 2, 3, 4 alebo trojica 6, 7, 8 budú prázdne, čo už vieme, že sa škriatok rozhnevá.
Ak za stolom sedia 4 ľudia:
Existuje viacero riešení, zamerajme sa teraz na jedno z nich:
Rozmiestnenie 4 ľudí môže byť napr. takéto:
Teraz si môžeme všimnúť, že ak sa každý z ľudí bude hýbať len medzi dvoma susednými stoličkami (prvý človek sa bude hýbať len medzi stoličkami 1 a 2, druhý medzi stoličkami 3 a 4, tretí medzi stoličkami 5 a 6, štvrtý medzi stoličkami 7 a 8), tak keby škriatok ukázal na hociakú stoličku, tak si tam niekto vie sadnúť a preto sa škriatok nenahnevá.
Zistili sme teda, že ak nechceme, aby sa škriatok rozhneval, tak za stolom musia sedieť najmenej 4 ľudia.