5. Kúzla s kartami

Táto úloha je teoretická. Ako svoje riešenie odovzdaj PDF súbor, v ktorom bude tvoje riešenie aj so zdôvodnením, prečo je správne. Po konci kola ti riešenie opraví vedúci, a napíše ti komentár – povie ti kde si spravil/a chyby, prípadne ti poradí ako vieš svoje riešenia zlepšiť.

Ak máš akékoľvek otázky ohľadom tejto úlohy, napíš Štepimu ([email protected]) alebo Emke ([email protected]).

Štepi sa pomaly ale isto začína s domorodcami nudiť. Keď už naozaj nevie, čo má robiť, rozhodne sa pozrieť do batohu. Keď sa prehrabe cez kopu Miškiných suvenírov až na spodok, zistí, že si zbalil karty presne pre takéto prípady. Rýchlo ich ide ukázať domorodcom a cestou už mieša karty a rozmýšľa, akú hru ich naučí najskôr.

Papagáj Hanka sa podobne ako Štepi tiež začína nudiť. Rozhodne sa zistiť, čo robia ostatní a ako prvého stretne práve Štepiho. Štepi jej povie, že si ide zahrať karty s domorodcami a Hanka by sa chcela pridať a zahrať si s nimi. Štepimu sa tento nápad veľmi nepáči lebo vie, že Hanka mu zakaždým karty pri hraní pokrčí. No keď jej to Štepi povie, Hanka sa urazí a jednu kartu mu vezme.

Úloha

Štepi je nešťastný, lebo si chcel s domorodcami zahrať karty, ale Hanka mu kartu vráti len pod podmienkou, že zistí, ktorá karta mu chýba. Našťastie je Štepi veeeľmi šikovný a vie rýchlo sčítavať, odčítavať, násobiť aj deliť. Rád by si zahral karty čo najskôr, a preto by chcel balíkom kariet prejsť len raz a za ten čas zistiť, akú kartu mu Hanka vzala. Nevie si zapamätať celý balík, najviac si vie zapamätať \(7\) čísel \(x_1\), \(x_2\) … \(x_7\), kde \(1 \leq x \leq 1 000 000\).

1. (20 bodov) Štepi mal kôpku kariet s číslami od \(1\) po \(100\) a Hanka mu z nej vzala 1 kartu. Chcel by nájsť spôsob, ako zistiť, ktorá karta mu chýba. Ako by vedel zistiť, aká karta mu chýba, ak balíkom kariet prejde len raz?

2. (45 bodov) Hanku zaujíma, či Štepi bude vedieť zistiť, aké karty mu vzala, aj keď vezme dve. Štepi má karty od \(1\) po \(100\) a balík je zamiešaný. Znova prejde balíkom kariet len raz. Ako by vedel zistiť, ktoré 2 karty mu chýbajú?

Hanku už prestalo baviť brať Štepimu karty a ide si radšej nájsť nejakú novú zábavu. Štepi si však stále chce s domorodcami zahrať karty, ale naozaj sa mu nechce hrať s balíkom, v ktorom nejaké karty chýbajú. Keďže domorodci si tiež chceli zahrať karty so Štepim, rozmýšľajú, ako by to vyriešili. Našťastie si jeden z nich spomenie na zabudnutý balík kariet, ktorý raz niekde našli.

3. (35 bodov) Štepi si pri miešaní rýchlo prezrel karty a zistil, že sa tam často opakujú niektoré karty. Od domorodcov sa dozvedel, že v balíku je presne \(100\) kariet a aspoň polovicu balíku tvorí jedna rovnaká karta. Štepiho teraz zaujíma, ktorá to je. Ako by Štepi vedel po prejdení celej postupnosti len raz zistiť, ktoré z čísel tvorí viac ako polovicu balíka?