Riešky výlet - Ahojte Rieškari, jar je v plnom prúde, vonku je pekne a my sa chystáme na výlet! Zoberte batohy, hry, frisbee, kamarátov a hlavne dobrú náladu a poďte sa s nami … Prejsť na článok
×4. príklad - Vzorové riešenie
Zadanie
Danko má v batohu 10 červených, 13 žltých, 12 bielych, 16 zelených a 18 modrých ponožiek. Koľko ponožiek musí náhodne vytiahnuť, aby mal istotu, že bude mať aspoň z niektorej farby kladný párny počet? Nezabudnite vysvetliť, prečo pre menšie počty nebude mať istotu.
Vzorové riešenie
Ak chceme mať istotu, že z aspoň jednej farby ponožiek bude párny počet, tak vlastne chceme, aby sa tento počet nedal dostať vybratím nepárneho počtu alebo nuly z každej farby.
Môžeme si všimnúť, že pri nízkych počtoch sa párnym počtom jednoducho vyhneme, a dôležitá tam bude nula. Ak napríklad Danko vytiahne 20 ponožiek, môže mať 5 modrých, žltých, bielych a zelených, a žiadne červené, čiže nemá istotu párneho počtu. Ak by Danko chcel vytiahnuť o jednu viac, môže sa mu stať to isté, ale vytiahne k tomu ešte jednu červenú. Ak by chcel vytiahnuť 22 ponožiek, môže sa mu stať to isté čo pri 12, ale namiesto modrej vytiahne o dve viac z nejakej inej farby. Pri 23 zase vytiahne jednu modrú, a tak ďalej...
Pri každom párnom počte je dôležité to, že z niektorej farby môže vytiahnuť 0 ponožiek. Ak by sme vedeli, že z každej vytiahol aspoň jednu, a chceme aby boli všetky počty nepárne, aj celkový výsledok bude nepárny. Súčet piatich (a ľubovoľného nepárneho počtu) nepárnych čísel je vždy nepárny.
Vyzerá to teda celkom beznádejne, kým vieme vytvoriť vyššie popísaný protipríklad. Kedy sa to už nebude dať spraviť? Jedine vtedy, keď bude Danko ťahať párny počet ponožiek, pri ktorom určite musí ťahať z každej kôpky. Aby nemal z ničoho párny počet, tak vie ťahať najviac 9 červených,
11 bielych 13 žltých 15 zelených a 17 modrých ponožiek. Potrebujeme teda, aby mu nestačilo ani vytiahnuť všetky ponožky zo štyroch najpočetnejších farieb. To sa stane, ak vytiahne viac ako 17+15+13+11=56 ponožiek. Chceme aby to bolo párne číslo, čiže 58. Pri tomto počte vieme, že ak by nevytiahol zo žiadnej farby párny počet, musí vytiahnuť aspoň jednu ponožku z každej farby. Potom ale môže dosiahnuť celkový párny počet ponožiek iba tak, že z niktorej farby ponožiek bude mať párny počet.
Pre 58 ponožiek má teda istotu, že bude mať z niektorej farby párny počet. Pre ľubovoľný menší počet existuje možnosť, že vytiahne 1 červenú ponožku a nejaké nepárne počty zvyšných (ak je celkový počet ponožiek nepárny), alebo vytiahne 0 červených ponožiek a nejaké nepárne počty zvyšných. Konkrétne spôsoby vieme vytvoriť napríklad postupom popísaným vyššie.
Odpoveď: Danko musí vytiahnuť aspoň 58 ponožiek.