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.
Š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$.
a. (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?
b. (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.
c. (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?
Štepi chce prejsť balíkom kariet, ktoré mu ostali, raz. Vie, že mu chýba jedna karta, teda jedno číslo z čísel od $1$ do $100$. Na to, aby zistil ktoré to je, môže použiť súčet čísel, ktoré mu ostali. Súčet čísel na všetkých kartách je $1 + 2 + … + 100 = 100\cdot 101/2 = 5050$. Keď od toho odpočíta súčet kariet, ktoré mu ostali, dostane číslo, ktoré je na karte, ktorú mu vzala Hanka.
Teraz chceme zistiť, ktoré 2 čísla chýbajú z postupnosti od $1$ po $100$. Ak by sme spravili len to, čo v prvej podúlohe, získame súčet čísel, ktoré hľadáme. Podľa súčtu nevieme presne zistiť, ktoré 2 čísla Štepimu chýbajú, chceli by sme teda ešte nejakú informáciu navyše.
Ak by sme mali ešte súčin kariet, ktoré Štepimu chýbajú, vedeli by sme zistiť, ktoré sú tie chýbajúce karty. Ak by sme však chceli vynásobiť všetky čísla od $1$ po $100$ a potom to deliť číslami na Štepiho kartách, vyšli by nám príliš veľké čísla, ktoré si Štepi nedokáže pamätať. Chceme teda nájsť nejaký iný spôsob.
Iná informácia, ktorú na toto vieme využiť, je súčet štvorcov (druhých mocnín) čísel na kartách. Súčet štvorcov všetkých čísel od $1$ do $100$ je $1^2 + 2^2 +\dots + 100^2 = (100\cdot 101\cdot 201)/6$ (toto vieme jednoducho dokázať pomocou indukcie), takže si vie dopočítať súčet štvorcov chýbajúcich kariet.
Označme chýbajúce čísla $x$ a $y$. Takto budeme vedieť ich súčet $A = x+y$ a súčet ich štvorcov $B = x^2+y^2$. Pomocou nejakých úprav rovníc vieme dopočítať $x$ a $y$.
$$\begin{aligned} A^2 = (x + y)^2 &= x^2 + 2xy + y^2 \ A^2 - B &= 2xy \ A^2 - 2(A^2 - B) &= 2B - A^2 = x^2 - 2xy + y^2 = (x - y)^2 \ \sqrt{2B - A^2} &= x - y \ (A + \sqrt{2B - A^2)} / 2 &= x \end{aligned}$$
A z toho už dopočítame aj $y$.
Aby sa nám úloha ľahšie riešila, predstavme si na začiatok, že máme karty pred sebou a môžeme s nimi niečo robiť a nemusíme si ich pamätať. Máme veľa rovnakých kariet a chceme sa zbaviť tých rôznych. Ako by sme to mohli spraviť bez toho, aby sme tie karty počítali?
Predstavme si, že si zoberieme našu kôpku kariet, a kým v nej existuje nejaká dvojica rôznych kariet, tak takúto dvojicu zoberieme a zahodíme. Keď toto budeme opakovať, na konci nám ostane niekoľko rovnakých kariet. Musia to byť tie karty, ktoré hľadáme, lebo ich je aspoň $51$ a dvojíc je najviac $50$.
Ako vieme toto urobiť, keď sa nemôžeme pozerať naraz na celý balíček? Predstavme si teraz, že prechádzame balíček len raz, ale ešte pred sebou môžeme mať vyloženú kôpku kariet (ktorá je na začiatku prázdna).
Keď nám príde nová karta, tak: - ak je kôpka prázdna, alebo je nová karta rovnaká ako karta na vrchu kôpky, tak ju pridáme na kôpku, - a ak je nová karta iná ako tá na vrchu kôpky, tak kartu z vrchu kôpky odoberieme a obe (aj tú z kôpky, aj tú novú) zahodíme.
V každom momente budú všetky karty na kôpke rovnaké. Takto teda nakoniec zahodíme všetky dvojice rovnakých kariet, na ktoré natrafíme, a ostanú nám len tie zvyšné rovnaké, ktoré hľadáme.
No a nakoniec si už len všimneme, že na toto nepotrebujeme mať kôpku kariet pred sebou, vieme si ju iba pamätať. Keďže všetky karty na kôpke sú rovnaké, tak si stačí pamätať, čo a koľko toho je na kôpke, a tým už vieme úlohu vyriešiť.