Adventný Logboj - Adventný Logboj je individuálna súťaž v riešení logických úloh, v ktorej môžu súťažiť základoškoláci, stredoškoláci aj starší. Na stránke súťaže bude každý decembrový deň až do vianoc sprístupnená jedna úloha, … Prejsť na článok
×8. príklad - Vzorové riešenie
Zadanie
Majme 52 rôznych žolíkových kariet, teda máme z každého zo 4 znakov 13 rôznych kariet. Ideme hádať, aký znak má horná karta. Po každom pokuse sa pozrieme na danú kartu a potom ju zahodíme preč, teda sa už nebude nachádzať v balíku. Dokážte, že ak budeme hádať znak, ktorého je v balíku aktuálne najviac (v prípade remízy ľubovoľne), tak uhádneme aspoň 13 znakov.
Vzorové riešenie
Najprv si trošku ssprehľadníe zápis riešenia. Vytvorme si označenie MAX. Takto budeme označovať "najvyššiu početnosť nejakého znaku karty v balíčku". Teda, koľko najviac kariet rovnakého znaku sa nachádza v balíčku. Všimnime si, že keďže odoberáme karty iba po jednej, tak sa nám MAX môže meniť iba tak, že sa zníži o jedna, lebo nevieme z tohto počtu odobrať naraz viac ako jednu kartu.
Pre naše riešenie sú kľúčové dve pozorovania:
1. Ak sa nám zníži MAX, tak v predošlom ťahu musela byť nejaká karta ostro viac početná ako ostatné.
Vieme si rozmyslieť, že toto platí, pretože karty odoberáme iba po jednom. Teda nikdy sa nemôže stať, že máme dva druhy rovnako (a najviac) početné, a potom jedným odobraním karty sa početnosti oboch z nich znížia.
2. Vždy, keď sa nám MAX zníži, tak sme uhádli znak karty.
Viem, že keď sa MAX zníži, tak to je práve vtedy, keď je jeden znak ostro viac početný ako ostatné, a teda podľa zadania hádame ju. Ak teda vytiahneme znak ktorý sme hádali, tak sme uhádli a MAX sa zníži. Ak ho nevytiahneme a neuhádli sme, tak MAX sa nezmení.
Teda, už stačí iba spojiť spojiť tieto dve pozorovania. Keďže MAX je na začiatku 13 a na konci 0, tak sa musel 13-krát znížiť o jedna. A teda sme určite 13-krát uhádli.