Deadline: 2021-11-07 23:59 (423 days ago)
Martin Koutecký — 2021-10-29 17:12 (433 days ago) — reply
Kolika způsoby lze projít čtvercovou mřížku obdélníkového tvaru z levého dolního rohu do pravého horního rohu, pokud má $m$ čtverečků ve vodorovném směru, $n$ čtverečků ve svislém směru a můžeme se pohybovat jen směrem vpravo a nahoru po hranách mřížky?
Santa Claus — modified 2021-10-30 12:16 (432 days ago) — edit — reply
Celkově uděláme $m+n$ pohybů, $m$ v jednom směru, $n$ v druhém. Zaleží jenom na pořadí, v jakém je provedeme, to můžeme spočítat tak, že ze všech očíslovaných pohybů vybereme ty, které budou v jednom směru:
$\binom{m+n}{m} = \binom{m+n}{n}$
Denys Boyko — 2021-11-06 01:55 (425 days ago) — reply
Ahoj! Je to spravne ale mohol by si prosim odstranit malu nejasnost v tej logike? - ako myslis, ze zo vsetkych ocislovanych pohybou vyberies tie co budu v jednom smere? Skus dat priklad alebo to rozpisat podrobnejsie
Points: 3.00
Santa Claus — 2021-11-06 11:04 (425 days ago) — edit — reply
Vybereme všechny ve směru nahoru, tedy n. A nevybrané pohyby pak budou ty doprava. Nebo vybereme všechny ve směru doprava, tedy m.
Denys Boyko — 2021-11-06 12:06 (425 days ago) — reply
> Vybereme všechny ve směru nahoru, tedy n. A nevybrané pohyby pak budou ty doprava. > > Nebo vybereme všechny ve směru doprava, tedy m. To som pochopil ale stale nechapem jak to myslis, skus dat priklad alebo obrazok, lebo my tie pohyby medzi sebou nerozlisujeme tak mi nedava zmysel preco by sme ich vyberali.
Santa Claus — 2021-11-06 13:00 (425 days ago) — edit — reply
Rozlišujeme mezi očíslovanými pohyby: Nejdříve uděláme první pohyb, pak druhý, pak třetí, ... až do $m+n$-tého pohybu. Z těchto očíslovaných pohybů budeme vybírat.
Denys Boyko — 2021-11-07 22:04 (423 days ago) — reply
Ahoj! prepac ale stale mi z tvojej logiky nesedi preco vyberame m-tice alebo n-tice, skus detalnejsie to popisat alebo dat priklad(realnu aplikaciu tvojho sposobu)
Points: 2.00
Santa Claus — 2021-11-07 22:19 (423 days ago) — edit — reply
Zkusím ještě takto: Každý pohyb popišme řetězcem ve tvaru NDNDNDDN..., kde N znamená nahoru a P znamená doprava, index znaku značí index pohybu, tj. první pohyb v uvedeném přikladě by byl nahoru druhý doprava, další nahoru, atd.... Je jasné, že každý různý řetězec kodifikuje unikátní pohyb. Taky vidíme, že řetězec bude obsahovat m-krát D, abychom překonali všechny čtverečky ve vodorovném směru, a n-krát N, abychom došli až nahoru. Celková délka řetězce pak musí být velmi triviálně m+n, protože celkem použijeme m+n znaků, a to m-krát D a n-krát N. Takovýto řetězec můžeme vytvořit například tak, že vybereme všechny pozice v řetězci o délce m+n, na které dáme D, a na zbylé pozice dáme N. Kolik takovýchto výběrů existuje spočítáme pomocí kombinačního čísla, protože jsme si ho definovali také tak, jako vyber z n prvků (pozic v řetězci) k prvků (pozic v řetězci). Protože existuje takový počet řetězců, existuje takový počet způsobů jak projít mřížku.