7. príklad - Vzorové riešenie
Zadanie
Sú dané dve kladné celé čísla n a k, pričom n \geq k > 1. Kúzelník má 2n kariet. Každá karta má na sebe z jednej strany napísané jedno z čísel 1, 2, \dots, n, pričom každé z týchto čísel sa vyskytuje na práve dvoch kartách. Vyloží ich doradu na piesok tak, aby neboli vidno čísla. Teraz v každom ťahu vedúci ukážu na ľubovoľných k kariet. Kúzelník im ich ukáže, potom týchto k kariet zamieša (tak ako mu vyhovuje) a položí ich na rovnaké pozície odkiaľ ich zobral (ale teraz môžu byť v inom poradí). Pre aké hodnoty k je možné, aby po konečnom počte ťahov vedúci s istotou ukázali na k kariet tak, aby medzi nimi bola aspoň jedna dvojica rovnakých kariet?
Vzorové riešenie
Keď obchodník zamieša karty, nevieme, ktorá je ktorá. Môžeme sa ale pozrieť na niektoré z nich znova a tým zistiť, ako ich zamiešal. Tie, na ktoré sa pozrieme síce potom zamieša znova a teda o nich veľa vedieť nebudeme, ale dozvieme sa, ktoré karty sú tie, na ktoré sme sa pozreli prvýkrát a nie druhýkrát.
Príklad
n = 4;k = 3
Na začiatku napríklad otočíme tri karty takto:
Teraz ich obchodník nejako zamieša a vráti naspäť.
Teraz vieme, že prvé tri karty sú 1, 2 a 3, nevieme však, ktorá je ktorá. Otočíme ďalšie tri karty:
Teraz vieme, ako obchodník zamiešal prvé tri karty - trojku položil na druhé miesto, jednotku na prvé a teda dvojku musel položiť úplne vľavo.
Teraz obchodník karty 1, 3 a 4 zamiešal, takže nevieme, kde je tá štvorka, trojka a jednotka. Stále ale vieme, že karta najvac vľavo je dvojka.
Takto môžeme otočiť ďalšiu a ďalšiu trojicu až do poslednej. Tým budeme presne vedieť, čo je na prvých piatich kartách. Keďže máme iba čísla 1 - 4, musí byť medzi nimi aspoň jedna dvojica rovnakých kariet. Potom môžeme proste otočiť tie dve (s ľubovoľnou ďalšou) a máme zaručene dvojicu rovnakých.
Pre všeobecné n, k
Na začiatku otočíme prvú až k-tu kartu, potom druhú až k+1-vú, ... až posledných k. Budeme teda vedieť, aké číslo je na prvých 2n-k kartách. Pre k \lt n platí n-k \gt 0 a teda 2n - k \gt n. Teda vieme, aké číslo je na viac ako n kartách. Je ale iba n rôznych čísel a teda na aspoň dvoch z nich sú rovnaké čísla. Ukážeme teda na tie dve (a ešte hocijaké ďalšie) a vieme, že je tam dvojica rovnakých.
Jediný prípad, kedy toto nefunguje je pre n=k. Vtedy totiž budeme mať informáciu iba o n kartách a teda medzi nimi nemusí byť žiadna dvojica. Pozrime sa teda na tento prípad podrobnejšie:
Pre k=n
Môžeme skúšať rôzne stratégie pre vedúcich, ale žiadna nevyzerá, že funguje. Tak poďme skúsiť dokázať, že ak obchodník namiešava karty správne, vedúci môžu otáčať donekonečna a nikdy sa im nepodarí otočiť dve rovnaké.
Keď k=n, jediný spôsob ako môžu neotočiť dve rovnaké je otočiť jednu jednotku, jednu dvojku, ... až jedno n. Takže vlastne dokazujeme, že obchodník vždy vie namiešať karty tak, aby otočili jednu z každej.
Vedúci môžu postupne získavať nejaké informácie o niektorých kartách. Tak sa pozrime na ten príklad, keď majú najviac informácií, ako môžu mať - vedia, aké čísla sú na všetkých kartách okrem tých, ktoré otočili v poslednom ťahu (tie totiž obchodník mohol zamiešať a môžu byť hocijako). Keďže v poslednom ťahu museli otočiť jednu jednotku, jednu dvojku..., tak tie ostatné (o ktorých vedia) sú tiež jedna jednotka, jedna dvojka, ... Vyzerá to teda nejako takto:
Vedúci teraz otočia niektoré z kariet, ktoré poznajú (ako si vyberú) a "naslepo" nejaké z tých, ktoré boli teraz otočené. Môže sa však stať, že z nich nešťastnou náhodou otočia práve tie, ktoré nevybrali z tých, ktoré poznajú (napríklad ak z tých, ktoré poznali vybrali jednotku a dvojku, tak sa im môže stať, že z tých ostatných vyberú práve 3, 4, ..., n. Tým sa zasa dostanú do takej istej pozície (majú informácie najviac o n kartách) a toto isté sa môže zopakovať znova a znova. Vždy môžu mať smolu a otočiť presne jednu z každej karty. Teda pre k=n nevedia s istotou po žiadnom počte ťahov otočiť dve rovnaké.
Odpoveď:
Keď 2 \le k \lt n, vedia vedúci ukázať na dvojicu rovnakých. Keď k=n, vie im obchodník zamiešavať karty tak, že dvojicu nikdy neotočia