Odporúčaný článok

Anketa - Ahoj Rieškar, stalo sa ti niekedy, že si nerozumel zadaniam? Chcel by si v lete prísť na denný tábor? Sú nejaké akcie, ktoré by si chcel, aby sme robili častejšie? … Prejsť na článok

×

5. príklad - Vzorové riešenie

Kategórie:
5
6
7
8
9

Zadanie

Dnešný diel kuchárskej súťaže Variešky má desať porotcov. Niektorí porotcovia sa navzájom poznajú a niektorí nie. Do štúdia dorazili po takých dvojiciach, že v každej dvojici sa porotcovia určite poznajú. V jednej takejto dvojici bol Mišo a Paľo. Keď porotcovia prišli, každý si podal ruku so všetkými porotcami, ktorých nepoznal. Mišo si všimol, že každý z ostatných deviatich porotcov si podal ruku s iným počtom ľudí. S koľkými ľuďmi si podal ruku Paľo?

Vzorové riešenie

Opravovali: JozefMican, Oliver, krtko, soso

Je 10 porotcov a každý pozná porotcu vo svojej dvojici. Porotca si sám so sebou ruku nepodáva a ani s porotcom vo dvojici, keďže ho pozná. Preto si porotca môže podať ruku s najviac 8 porotcami (keď nepozná nikoho okrem porotcu vo  dvojici). Najmenej si môže porotca podať ruku s 0 porotcami (keď pozná všetkých porotcov).

Mišo si všimol, že každý z ostatných 9 porotcov si podal ruku s iným počtom porotcov. Títo porotcovia majú zároveň 9 možností na to, s koľkými porotcami si môžu podať ruku, a to od 0 do 8. Jeden z porotcov si teda musel podať ruku s 0 porotcami, jeden z porotcov si musel podať ruku s 1 porotcom, a tak ďalej, až posledný porotca si musel podať ruku s 8 porotcami.

Označme si porotcu, ktorý si podal ruku s 0 porotcami P_0, porotcu, ktorý si podal ruku s 1 porotcom P_1, a tak ďalej, až porotcu, ktorý si podal ruku s 8 porotcami P_8 (jeden z týchto porotcov je Paľo, zatiaľ však nevieme ktorý).

Porotca P_8 si musel podať ruku so všetkými porotcami okrem svojej dvojice. Jediný porotca, ktorý si ešte nepodal ruku je porotca vo dvojici s P_8. Tento porotca musí byť preto P_0 (nikto iný to nemôže byť). Z toho vyplýva, že porotca P_8 musí byť vo dvojici s P_0.

Porotca P_7 si potom musel podať ruku so všetkými okrem P_0 (ten si s nikým nepodal ruku) a porotcu vo svojej dvojici. Všetci porotcovia, okrem P_0 a porotcu vo dvojici s P_7, si už podali ruku aspoň 2-krát. Jediný, kto môže byť P_1 je teda porotca vo dvojici s P_7. Porotcovia P_7 a P_1 sú teda vo dvojici.

Porotca P_6 si už nemôže podať ruku s P_0 ani s P_1, ani s porotcom, ktorý je s ním vo dvojici. Preto si musí podať ruku so všetkými ostatnými porotcami. Potom všetci porotcovia, okrem P_0, P_1 a porotcu vo dvojici s P_6, si podali ruku aspoň 3-krát. Porotca vo dvojici s P_6 teda musí byť P_2.

Porotcovia P_0, P_1, P_2 už majú vyčerpaný počet podaní rúk, preto si s nimi P_5 nemôže podať ruku. Porotca P_5 si preto musí podať ruku so všetkými okrem P_0, P_1, P_2 a svojej dvojice. Všetci porotcovia, okrem P_0, P_1, P_2 a porotcu vo dvojici s P_5 si podali ruku aspoň 4-krát. Tým pádom porotca vo dvojici s P_5 musí byť P_3.

Z toho vyplýva, že porotcovia prišli vo dvojiciach (P_0, P_8), (P_1, P_7), (P_2, P_6), (P_3, P_5). Zostávajú nám už iba porotcovia P_4 a Mišo. Títo dvaja musia teda byť spolu vo dvojici. Keďže vieme, že Mišo je vo dvojici s Paľom, tak P_4 musí byť Paľo. Tým pádom si Paľo podal ruku so \mathbf{4} ľuďmi.

Komentár

V tejto úlohe bolo dôležité nielen zistiť, v ktorých dvojiciach porotcovia prišli a kto si s kým podal ruku, ale aj to poriadne dokázať. Aj keď väčšina z vás sa dopracovala k správnemu výsledku, viacerí ste práve pri dokazovaní neukázali, že toto riešenie je jediné možné. Na toto si v budúcnosti treba dať pozor.