Riešky tábor - Milí naši Rieškari, ako je už zvykom, aj tento rok sme si pre Vás pripravili Letný tábor Riešok. Je to desaťdňová akcia počas ktorej sa zabavíte, niečo naučíte a hlavne … Prejsť na článok
×2. príklad - Vzorové riešenie
Zadanie
Jedného dňa sa rozhodol Feynman dať svojim študentom neoznámenú písomku. Písomka pozostáva z 2 úloh. Za správnu odpoveď dostane študent 3 body, za žiadnu 1 bod a za nesprávnu -1 bod. Feynman tvrdí, že aspoň 4 žiaci budú mať rovnako veľa bodov. Koľko najmenej žiakov muselo byť v triede, aby si Feynman mohol byť istý, že nech písomku napíšu akokoľvek, určite tam takí štyria budú?
Vzorové riešenie
Najskôr sa pozrieme, aké jednotlivé počty bodov mohli Feynmanovi žiaci dosiahnúť. Máme 3 možnosti pre obidve otázky: správna odpoveď (3 body), nesprávna odpoveď (-1bod), neodpovedal (1 bod), a z toho vyplýva, že máme dokopy 3 \cdot 3 = 9 možností (Ku každému možnému obodovaniu prvej otázky vieme napárovať 3 možné obodovania druhej). Jednotlivé možnosti vyzerajú takto:
počet bodov z prvej otázky | počet bodov z druhej otázky | spolu |
|---|---|---|
3 | 3 | 6 |
3 | 1 | 4 |
3 | -1 | 2 |
1 | 3 | 4 |
1 | 1 | 2 |
1 | -1 | 0 |
-1 | 3 | 2 |
-1 | 1 | 0 |
-1 | -1 | -2 |
Z tabuľky vidíme, že je 5 rôznych počtov bodov z testu (6, 4, 2, 0, -2). Teraz sa môžeme zamyslieť, ako nájdeme najmenší počet študentov taký, kde určite majú aspoň 4 študenti rovnaký počet bodov. Čo tak sa na to pozrieť z opačnej strany? Ideme nájsť najväčší počet študentov kde sa taká skupinka nutne nemusí nachádzať. To znamená, že existuje aspoň 1 rozdelenie, kde všetky skupiny budú obsahovať menej ako 4 študentov.
Pozrime sa na prípad, že máme 15 študentov. Pri tomto počte ich vieme rozdeliť do piatich skupín po 3 (toto rozdelenie nazvyme "vyvážené"). Ako vidíme je to jediné rozdelenie 15 študentov, kde všetky skupinky maju pod 4 študentov. Iné rozdelenie dosiahneme tým, že vo vyváženom rozdelení premiestnime nejakých študentov z jednej skupinky do druhej. Toto nám ale zaručí vznik skupinky s aspoň 4 študentmi, keďže pridáme nejakých študentov do skupinky s 3 študentmi.
Pridaním 16. študenta máme zaručené, že aspoň jedna skupinka bude mať aspoň 4 študentov. Všetky rozdelenia 15 okrem vyváženeho už obsahujú skupinku aspoň 4 študentov. To znamená, že aj po pridaní študenta bude takáto skupinka existovať. Pri vyváženom rozdelení sa musí študent pridať do jednej skupinky 3 študentov, tým pádom by nám vznikla skupinka s 3 + 1 = 4 študentmi.
To znamená, že v triede muselo byť aspoň 16 študentov.
Komentár
Väčšina z vás síce došla k správnemu výsledku, ale nepodarilo sa vám úplne poriadne zdôvodniť, prečo to tak naozaj je. Väčšinou ste povedali, že keď je ich 15 tak, že v každej skupinke sú traja, tak keď pridáme ďalšieho, tak už v nejakej skupinke budú štyria. To je pravda, ale my chceme ukázať nielen to, ale že dokonca keď tých 16 ľudí rozdelíme úplne hocijako, tak stále budú niekde aspoň štyria. V tomto príklade to síce vyzerá pomerne zrejmé (preto sme za to nestrhávali body), ale aj tak je lepšie to poriadne vysvetliť, hlavne pri ťažších príkladoch, kde to už také zrejmé nie je.