Навчання / Бібліотека / Комбінаторика

Маршрути повз яму

КомбінаторикаСереднє

Робот рухається сіткою від $(0, 0)$ до $(5, 5)$ , і кожен хід — на $1$ одиницю на схід або на $1$ одиницю на північ. Точка $(2, 2)$ є ямою, і робот ніколи не має на неї ступати. Скільки існує маршрутів, що оминають яму?

Для перевірки відповіді потрібен JavaScript. Підказка й розв’язок відкриваються і без нього.

Підказка

Порахуй усі маршрути, а потім відніми ті, що проходять через погану точку.

Розв’язок

Без обмежень існує $(5 10) = 252$ маршрутів.
Маршрут, що ступає на яму, розпадається на частину від $(0, 0)$ до $(2, 2)$ і частину від $(2, 2)$ до $(5, 5)$ .
Перша частина має $(2 4) = 6$ маршрутів, а друга — $(3 6) = 20$ маршрутів, тож яму використовують $6 \times 20 = 120$ маршрутів.
Маршрут відвідує яму щонайбільше раз, тому нічого не пораховано двічі, і відповідь дорівнює $252 - 120 = 132$ .

Відповідь: $132$

Наступна задача Назад до бібліотеки