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
×3. príklad - Vzorové riešenie
Zadanie
Mapa vyzerala takto:
Nachádza sa tam 11 domov rôznych farieb. Každý dom je označený nejakým celým číslom. Zároveň v každom dome býva jeden kamarát. Medzi týmito domami existujú cesty, čiže čiary. Jedna cesta vždy spája práve dva domy, ako vidíte na obrázku.
Kamaráti sa chcú spolu stretávať. Lenže sú leniví a nechce sa im chodiť dlhšie ako jednu cestu. Takže dvaja kamaráti sa budú schopní stretnúť v dome, ktorý je od každého najďalej jednu cestu. To znamená, že napríklad kamarát, ktorý býva vo svetlomodrom dome sa vie stretávať s kamarátmi u seba doma, alebo vie ísť do žltého domu, alebo vie ísť do svetlozeleného domu.
Pre každú dvojicu kamarátov platí, že súčet všetkých čísel domov, kde sa vedia stretnúť, je 0. Vašou úlohou je dokázať, že ak chceme aby také niečo platilo, musia byť čísla na všetkých domoch práve 0.
Vzorové riešenie
Táto úloha môže pôsobiť pomerne náročne. Našou úlohou je dokázať, že na každom dome sa nachádza číslo 0. Ak by sa na každom dome naozaj nachádzalo číslo 0 všetky podmienky zo zadania by určite fungovali. Súčet núl bude vždy nula. Avšak ako súčasť dôkazu musíme ukázať aj to, že to inak byť nemôže. Toto sa dá robiť viacerými spôsobmi. V tomto prípade je najjednoduchšie postupne domček za domčekom ukázať, že na každom domčeku sa musí nachádzať číslo 0.
Pri tomto postupe musíme začať so správnou dvojicou kamarátov. Zadanie hovorí, že súčet čísel na domoch, kde sa vie stretnúť dvojica kamarátov je 0. Teda, ak sa vedia stretnúť iba v jednom domčeku, tak na tomto domčeku musí byť číslo 0. Keď sa podrobne pozrieme na mapu, tak napríklad kamaráti z domčekov a sa vedia stretnúť iba v . Teda musí na sebe mať číslo 0. Dokonca takýchto dvojíc kamarátov je viac:
- a sa vedia stretnúť iba v .
- a sa vedia stretnúť iba v .
- a sa vedia stretnúť iba v .
To stále nie sú všetky dvojice. Existujú aj ďalšie, napríklad a sa tiež vedia stretnúť iba v . Ale z ďalších takýchto dvojíc už nezískame ďalšie domčeky, ktoré vieme jasne označiť číslom 0. Teda týmto postupom sa vieme dostať iba k nasledovnej mape.
Teraz skúsme vymyslieť ako ukázať, že aj na musí byť číslo 0. Kamarát z tohto domčeku sa vie s ostatnými kamarátmi stretnúť buď u seba doma, alebo u suseda doma. Povedzme, že sa chce stretnúť práve so svojím susedom z . Avšak na domčeku už vieme, že sa nachádza 0. Aby teda súčet a bol 0. Čo sú jediné možnosti, kde sa vedia stretnúť. Tak aj na musí byť 0.
Rovnakú úvahu vieme použiť pre ďalšie domčeky, ktoré ešte nie sú označené číslom 0. Tak ako a sa vedia stretnúť iba v a .
- a sa vedia stretnúť iba v a .
- a sa vedia stretnúť iba v a .
A keďže a už na sebe majú čísla 0, tak aj na a musia byť 0.
Podobne sa môžeme pozrieť na nasledovné dvojice:
- a sa vedia stretnúť iba v a .
- a sa vedia stretnúť iba v a .
A keďže a už na sebe majú čísla 0, tak aj a musia byť 0.
Nakoniec použijeme opäť podobnú úvahu. Tentoraz pre nasledovné dvojice kamarátov:
- a sa vedia stretnúť iba v , a . Keďže a majú na sebe čísla 0, tak aj musí byť 0.
- a sa vedia stretnúť iba v , a . Keďže a majú na sebe čísla 0, tak aj musí byť 0.
Týmto spôsobom sme ukázali, že na každom domčeku sa musí nachádzať číslo 0. V tejto úlohe existovalo naozaj veľké množstvo iných postupov ako sa dostať ku rovnakým záverom, my sme ukázali iba jeden z nich.