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

Шляхи з малим числом поворотів

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

Шлях від $(0, 0)$ до $(6, 4)$ складається з одиничних кроків на схід або на північ. Поворот — це крок, напрямок якого відрізняється від попереднього кроку. Скільки шляхів мають рівно $3$ повороти?

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

Підказка

Точна кількість поворотів визначає, скільки прямих відрізків має шлях.

Розв’язок

Рівно $3$ повороти означають, що шлях складається з $4$ прямих відрізків, які чергуються між сходом і північчю.
Якщо шлях починається на схід, є $2$ відрізки на схід із сумою $6$ і $2$ відрізки на північ із сумою $4$ .
Розбити $6$ на $2$ додатні частини можна $5$ способами, а $4$ — $3$ способами, тож на схід починаються $5 \times 3 = 15$ шляхів.
Той самий аргумент дає $15$ шляхів, що починаються на північ, тому разом $15 + 15 = 30$ .

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

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