Deltoid

Drogi w kratach i kino

Joanna Jaszuńska

Delta, styczeń 2014

o artykule ...

Publikacja w Delcie: styczeń 2014
Publikacja elektroniczna: 01-01-2014

Narzędzia
Obiekty
Słowa kluczowe
Kategoria: Kombinatoryka

Drogi w kratach i kino»Zadanie 1

o zadaniu...

Zadanie pochodzi z artykułu Drogi w kratach i kino
Publikacja w Delcie: styczeń 2014
Publikacja elektroniczna: 01-01-2014

Dwie z najkrótszych dróg z $\text{[math]}$ do $\text{[math]}$ : $\text{[math]}$ i $\text{[math]}$

W Kratkowie ulice prowadzą tylko z północy na południe lub z zachodu na wschód, a odstępy pomiędzy kolejnymi przecznicami są równe jednej kratce. Szukamy najkrótszej możliwej drogi ulicami z punktu $\text{[math]}$ do punktu $\text{[math]}$ Którędy należy iść i ile jest różnych dróg do wyboru?

Rozwiązanie

Najkrótsze drogi prowadzą na północ lub na wschód. Wszystkie są długości $\text{[math]}$ gdyż każda ma łącznie $\text{[math]}$ kratek na wschód i $\text{[math]}$ na północ.

Każdą taką drogę można utożsamić z jej opisem – ciągiem zawierającym $\text{[math]}$ znaków $\text{[math]}$ oraz $\text{[math]}$ znaków $\text{[math]}$ kodującym, czy na kolejnym skrzyżowaniu należy iść na północ $\text{[math]}$ czy na wschód $\text{[math]}$ Najkrótszych dróg jest więc tyle, ile takich ciągów, czyli $\text{[math]}$ bo na tyle sposobów można wybrać, na których $\text{[math]}$ spośród wszystkich $\text{[math]}$ miejsc ciągu ma być znak $\text{[math]}$

Narzędzia
Obiekty
Słowa kluczowe
Kategoria: Kombinatoryka

Drogi w kratach i kino»Zadanie 2

o zadaniu...

Zadanie pochodzi z artykułu Drogi w kratach i kino
Publikacja w Delcie: styczeń 2014
Publikacja elektroniczna: 01-01-2014

Wykaż, że

display-math

Rozwiązanie

Z zadania 1 wiemy, że liczba najkrótszych dróg „po kratkach” z lewego dolnego do prawego górnego rogu kwadratu $\text{[math]}$ równa jest $\text{[math]}$

Wyznaczmy tę samą liczbę inaczej. Każda z takich dróg musi przejść przez dokładnie jeden z $\text{[math]}$ kolorowych punktów $\text{[math]}$ z rysunku. Liczba najkrótszych dróg z $\text{[math]}$ do $\text{[math]}$ przechodzących przez $\text{[math]}$ jest iloczynem liczby najkrótszych dróg z $\text{[math]}$ do $\text{[math]}$ i liczby najkrótszych dróg z $\text{[math]}$ do $\text{[math]}$ czyli – z zadania 1 – równa jest

display-math

Stąd liczba wszystkich najkrótszych dróg z $\text{[math]}$ do $\text{[math]}$ równa jest

display-math

co kończy dowód na mocy początkowej obserwacji, że dróg tych jest $\text{[math]}$

Uwaga. $\text{[math]}$ bo wybór $\text{[math]}$ elementów z $\text{[math]}$ równoważny jest odrzuceniu pozostałych $\text{[math]}$ elementów.

Narzędzia
Obiekty
Słowa kluczowe
Kategoria: Kombinatoryka

Drogi w kratach i kino»Zadanie 3

o zadaniu...

Zadanie pochodzi z artykułu Drogi w kratach i kino
Publikacja w Delcie: styczeń 2014
Publikacja elektroniczna: 01-01-2014

Bilet do kina kosztuje 10 zł, w kasie jest dużo biletów i nie ma pieniędzy. W kolejce stoi, w przypadkowej kolejności, $\text{[math]}$ osób z banknotami 10 zł oraz $\text{[math]}$ osób posiadających jedynie banknot 20 zł, przy czym $\text{[math]}$ Jakie jest prawdopodobieństwo, że kasjerowi w trakcie obsługi nie zabraknie reszty do wydawania?

Rozwiązanie

Zilustrujmy kolejkę jako pewną drogę o $\text{[math]}$ krokach: w danym kroku idziemy w prawo, jeśli klient ma 10 zł, lub w górę, jeśli ma 20 zł. Aby kasjerowi nie zabrakło reszty, liczba wręczonych mu banknotów 20 zł nigdy nie może przekroczyć liczby banknotów 10 zł, które do tego momentu dostał. Innymi słowy, droga jest dobra, jeśli nie dotyka kolorowej prostej $\text{[math]}$ z rysunku obok. Policzmy, ile jest złych dróg.

Niech dana zła droga pierwszy raz dotyka prostej $\text{[math]}$ w punkcie $\text{[math]}$ Jej część od punktu $\text{[math]}$ do punktu $\text{[math]}$ odbijmy symetrycznie względem prostej $\text{[math]}$ uzyskując półodbicie złej drogi – nową drogę prowadzącą tylko w prawo lub w górę od punktu $\text{[math]}$ do punktu $\text{[math]}$ Każda zła droga ma inne półodbicie. Ponadto każda najkrótsza droga z $\text{[math]}$ do $\text{[math]}$ przecina prostą $\text{[math]}$ więc jest półodbiciem pewnej złej drogi. Stąd złych dróg jest tyle, ile ich półodbić, czyli najkrótszych dróg z $\text{[math]}$ do $\text{[math]}$ a więc, na mocy zadania 1,