Od startu do mety
Zagadka
Ile jest ścieżek pomiędzy lewym, górnym rogiem siatki 5x5, a prawym dolnym jeśli z aktualnego pola można przejść o 1 pole w prawo lub 1 pole w dół. Jak obliczyć ile jest ścieżek na siatce o innych rozmiarach?
Rozwiązanie
Odpowiedź
Jest dokładnie 70 sposobów na dotarcie z startu do mety dla siatki 5x5. Dla większej siatki 7x7 istnieje 924 ścieżek. Poniższa tabelka podsumowuje ilość ścieżek dla różnych rozmiarów siatki:
| Rozmiar | Ścieżek |
|---|---|
| 2x2 | 2 |
| 3x3 | 6 |
| 4x4 | 20 |
| 5x5 | 70 |
| 6x6 | 252 |
| 7x7 | 924 |
| 8x8 | 3432 |
Wyjaśnienie
Na dowolne pole (x, y) prowadzi tyle ścieżek ile jest możliwości dojścia z pól (x - 1, y) oraz (x, y - 1). Oczywiście dla pól, które nie istnieją należy przyjąć, że prowadzi do niej 0 ścieżek. Warunkiem startowym jest ustawienie w polu (0, 0) wartości 1. Inaczej cała tablica będzie wyzerowana. Oto tablica z wyliczonymi wartościami dla tablicy 5x5:
| 1 | 1 | 1 | 1 | 1 |
|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 |
| 1 | 3 | 6 | 10 | 15 |
| 1 | 4 | 10 | 20 | 35 |
| 1 | 5 | 15 | 35 | 70 |