Odporúčaný článok

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

×
Kategórie:
5
6
7
8
9

Zadanie

Stanica má tvar rovnostranného trojuholníka so stranou dĺžky n metrov a je rozdelená na sieť rovnostranných trojuholníčkov s dĺžkou strany 1 meter. Skupina vedúcich sa nachádza v najvyššom trojuholníčku a potrebuje sa dostať na nástupište, ktoré sa nachádza na strednom trojuholníčku v najspodnejšom riadku. Môže sa pohybovať len cez stredy hrán trojuholníčkov dole, doprava alebo doľava, pričom sa nesmie vrátiť do trojuholníčka, v ktorom už bola. (Vyjsť z veľkého trojuholníka tiež nemôže.) Určte, koľkými spôsobmi môže skupina vedúcich prejsť stanicou na nástupište. Na obrázku je znázornená stanica pre n=4 a jedna možná cesta na nástupište.

Obr. 3: Stanica

Vzorové riešenie

Opravovali: lámač

Zhruba jednej polovici riešiteľov sa podarilo príklad správne vyriešiť. Druhá polovica si už tak dobre nepočínala, čo bolo najčastejšie spôsobené neodpovedaním na zadanú úlohu, alebo nepostačujúcim vysvetlením postupu. Preto si najskôr pripomenieme, čo bolo našou úlohou a následne si ukážeme ako postupovať pri riešení.
Zadaný rovnostranný trojuholník, ktorý predstavuje stanicu, má n poschodí zložených z menších trojuholníčkov s dĺžkou strany 1 meter. Našou úlohou je určiť, koľkými spôsobmi môže skupina vedúcich prejsť stanicou na nástupište, teda z vrchného poschodia trojuholníka so stranou dlhou n do stredu spodného ( n -tého) poschodia.

Kľúčové je uvedomiť si, že náš trojuholník má vo všeobecnosti n poschodí, pričom n môže mať hodnotu ľubovoľného prirodzeného čísla (napríklad n = 4 , ale kľudne aj n = 567 poschodí). V zadaní je pre ilustráciu náčrt trojuholníka pre n = 4 . To však neznamená, že ak nájdeme riešenie pre ilustračný obrázok, tak sme vyriešili príklad.
Z toho môžeme intuitívne usúdiť, že naše riešenie bude nejako závisieť od hodnoty n . Ak by sa nám podarilo nájsť vzorec, ktorý by nám po dosadení doň konkrétnej hodnoty n povedal, koľko je pre dané n možných spôsobov, mali by sme v rukách všeobecné riešenie. Presne toto chceme my!

Keď sa nachádzame na určitom poschodí, existuje práve jedna možnosť ako sa na ňom dostať do ľubovoľného trojuholníčka na danom poschodí. Kedže sa nevieme pohnúť na vyššie poschodie, môžeme sa po poschodí posunúť buď doprava alebo doľava. Nemôžeme sa však už vrátiť do trojuholníčka, v ktorom sme boli. Preto pohyb po poschodí je iba jednosmerný, určujúci práve jeden spôsob ako prejsť medzi danými dvoma trojuholníčkami na tom istom poschodí.

Z každého poschodia sa vieme dostať na to nižšie tak, že prejdeme cez jednu zo strán malých trojuholníčkov vedúcu nadol. V k -tom poschodí je takýchto trojuholníčkov práve k . Čiže exisuje k spôsobov ako sa dostať z k -tého poschodia o jedno poschodie nižšie.
Kedže prechody cez jednotlivé poschodie sú nezávislé od prechodov vo vyšších poschodiach, počty spôsobov ako sa dostať na dané poschodie z vrchného poschodia trojuholníka budú súčinom spôsobov prechodov vo vyšších poschodiach.

Z vrchného poschodia vedie k = 1 spôsob prechodu o poschodie nižšie. Preto k -té poschodie má dokopy k! rôznych spôsobov ako prejsť z vrchu trojuholníka na poschodie pod k -tým poschodím.
Na n-té poschodie sa dostaneme z (n - 1) -vého poschodia, preto je (n - 1)! spôsobov ako sa dostať na n -té poschodie. Ako sme si už vysvetlili, na určitom poschodí je len jedna možnosť ako sa dostať do stredného trojuholníčka z ľubovoľného trojuhoľníčka na danom poschodí. Takže zo stanice na nástupište sa vieme dostať 1 \cdot (n - 1)! spôsobmi. Vidíme, že skutočne počet spôsobov závisí od n . Práve sme vyriešili príklad pre všeobecnú hodnotu n .

Odpoveď: Skupina vedúcich môže prejsť stanicou na nástupište (n - 1)! spôsobmi.