Příklad 357

Nechť $m,$ $n$ jsou celá nezáporná čísla. Najděte počet cest délky $m + n,$ vedoucích z počátku souřadnicové soustavy do bodu $[m, n]$ skládajících se z úseček rovnoběžných se souřadnicovými osami, které mají koncové body v bodech s celočíselnými souřadnicemi.

Příklad 358

Král se má dostat z levého horního rohu šachovnice na obrázku (S) do pravého dolního rohu (F) nejkratší cestou. Kolik takových cest existuje?

Příklad 359

Na šachovnici $8 \times 8$ můžu dělat následující tahy: buď 1 krok vpravo, nebo 2 kroky nahoru. Kolika způsoby se můžu dostat z levého dolního rohu do pravého horního rohu?

Příklad 360

Kolik existuje nejkratších cest v celočíselné mřížce z počátku do bodu $[8;8],$ jestliže ve směru $y$ se můžeme posunovat jen o sudý počet jednotek?

Příklad 361

Kolik existuje nejkratších cest v celočíselné mřížce z počátku do bodu $[10;5],$ jestliže ve směru $y$ nesmíme udělat dva kroky bezprostředně za sebou?

Příklad 362

Kolik existuje (ne nutně nejkratších) cest z bodu $\mathsf A$ do bodu $\mathsf B$ po úsečkách mřížky sestavené z $n$ čtverců (viz obr.), jestliže každou úsečku procházíme nejvýše jednou?

Příklad 363

Baník porazil Barcelonu 7:3.
(a) Kolik různých průběhů mohl mít tento zápas?
(a) Kolik různých průběhů mohl mít tento zápas, jestliže poločas skončil 2:1 ve prospěch Baníku?

Příklad 364

Hokejový zápas skončil výsledkem 5:2. Kolik existuje průběhů zápasu, pokud jednotlivé třetiny skončili: 2:1, 2:1, 1:0.

Příklad 365

Kolik existuje nejkratších cest v celočíselné mřížce z počátku do bodu $[10;10],$ jestliže nejdeme bodem $[2;3]$?

Příklad 366

Kolik existuje nejkratších cest v celočíselné mřížce z počátku do bodu $[10;10],$ jestliže nejdeme body $[2;3],$$[8;8]?$

Příklad 367

Kolik existuje nejkratších cest v celočíselné mřížce z počátku do bodu $[10;10],$ jestliže nejdeme úsečkou $[5;5]-[5;6]$?

Příklad 368

Na obrázku vidíte plánek města, políčka jsou bloky domů. Kolika způsoby se můžeme dostat z bodu $\mathsf C$ do $\mathsf D$ pokud jdeme jen východním nebo severním směrem?

Příklad 369

Na obrázku vidíte plánek parku, vyšrafovaná políčka jsou záhony. Kolika způsoby můžeme projít parkem z bodu $\mathsf A$ do bodu $\mathsf B,$ když půjdeme pouze na jih nebo na západ?

Příklad 370

Kolika způsoby se můžeme dostat z bodu $\mathsf A$ do bodu $\mathsf B,$ když se můžeme pohybovat jen ve směru šipek?

Řešení	Ukázat

Příklad 371

Po hrací desce, kterou vidíte na obrázku, se pohybuje figurka. V každém kroku se může posunout, jen na sousední tmavší políčko. Kolika způsoby se může dostat z bílého políčka na černé?

Řešení	Ukázat

Příklad 372

Na obrázku vidíte plánek města, vyšrafovaná políčka jsou bloky domů. Zjistěte, kolika způsoby se můžeme dostat z místa $\mathsf A$ do místa $\mathsf B,$ jestliže:
(a) v každém úseku cesty smíme jít pouze východním nebo jižním směrem.
(b) v každém úseku cesty smíme jít pouze východním nebo jižním směrem a musíme projít přes křižovatku označenou černým křížkem.

Příklad 373

Pavouk se pohybuje po drátěném modelu krychle, kterou vidíte na obrázku. Nyní se chce dostat nejkratší cestou z vrcholu $\mathsf A$ do vrcholu $\mathsf G.$ Kolik různých cest má na výběr? (Smí lézt jen po naznačených úsečkách.)

Příklad 374

Fotbalový zápas skončil výsledkem 5:4 pro domácí tým. Domácí se hned v úvodu ujali vedení a udrželi si ho až do konce zápasu. Kolika různými způsoby se mohlo vyvíjet skóre?

Řešení

Ukázat

1. možnost: postupné počítání. Na vodorobné ose jsou domácí, na svislé hosté. 2. možnost: kombinatorická úvaha. Všech nejkratších cest z bodu $[0;0]$ do bodu $[5;4]$ je ${9\choose5}$ (příklad 357). Najdeme počet "špatných" cest. Špatná cesta (na obrázku černě) se někde dotkne (nebo protne) čárkovanou čáru (přímku $y=x$). Vytvoříme novou cestu tak, že část cesty od počátku do prvního bodu dotyku symetricky zobrazíme podle čárkované osy (červeně) a zbytek necháme stejný. Nových cest je stejně jako původních cest. Ale nové cesty musí jít přes bod $\mathsf A$ a do tohoto bodu se mohou dostat jediným způsobem.  To znamená, že musíme spočítat cesty z  $\mathsf A$ do $\mathsf B.$ Těch je  ${8\choose5}.$ Takto jsme ovšem spočítali jen "špatné" cesty, které začínají krokem $[0;0]\rightarrow[1;0].$ Musíme přidat cesty, které začínají krokem $[0;0]\rightarrow[0;1].$ I ony musí jít přes bod $\mathsf A$ a i ony se do tohoto bodu se mohou dostat jediným způsobem. Celkový počet vhodných cest je ${9\choose5}-2\cdot{8\choose5}.$ Obecně: skončí-li skóre $d:h$, $d>h$, pak počet průběhů zápasů za daných podmínek je ${d+h\choose d}-2{d+h-1\choose d}.$

Příklad 375

Zápas skončil nerozhodně 3:3.
(a) Kolika způsoby se mohlo vyvíjet skóre?
(b) Kolika způsoby se mohlo vyvijet skóre, jestliže domácí nikdy neprohrávali?

Příklad 376

Určete počet způsobů, kterými na přiloženém obrázku můžeme vytvořit slovo "ABRACADABRA". Postupovat můžeme vždy jen od jednoho písmene k sousednímu.

Řešení	Ukázat
Když schéma přerovnáme do tvaru, vidíme, že se jedná o cestu v síti. Je ${10\choose5}$ možností.