Question

Решите.
Лягушка собралась к подружке Цапле на другой край болота, причем решила, что будет прыгать на кочки, либо на одну вверх, либо на одну кочку вправо, либо на одну кочку по диагонали - вправо и вверх. Сколькими разными путями Лягушка может допрыгать до своей подружки?

Answer 1

Задачка не из простых.
Чтобы понять как отыскать число возможных вариантов,начнем с простого. Рассмотрим сначало варианты когда лягушка не прыгает по диагонали. Эти варианты тоже входят в общее число всех возможных вариантов. Итак ,из рисунка видно ,чтобы добраться к цапле,независимо от того в каком порядке совершены прыжки,лягушка должна сделать ровно 10 прыжков. Из которых ровно 5 вправо и 5 вверх соответственно!(Тк кочки расположены квадратом 6*6) Тогда чтобы посчитать общее число таких вариантов нужно выбрать из 10 номеров прыжков те номера когда она прыгает вверх (вправо ),что неважно в силу симметрии задачи. То общее число таких вариантов: C(10;5) -число сочетаний 5 номеров из 10 возможных. Теперь перейдем от простого к более сложному. Из этих номеров можно выбрать те ,когда лягушка будет прыгать по диагонали. (лягушка может прыгнуть по диагонали не более 5 раз). Выберем случай ,когда лягушка прыгнула по диагонали n раз. В этом случае лягушка останеться прыгнуть вверх и право по 5-n раза,тк прыжок по диагонали равносилен прыжку вправо и вверх. Лягушка может прыгнуть по диагонали n раз ,заняв C(10-n,n) разных способов занятия 10-n номеров прыжков. Тк общее число прыжков ,которая сделает лягушка в этом случае равно:2*(5-n)+n=10-n.(Это очень тонкий момент)Тогда общее число вариантов для случая когда лягушка прыгает n раз: C(10-n;n)*C(10-2*n;5-n). Тогда общее число вариантов будет: N=C(10,5)+C(9,1)*C(8,4)+C(6,2)*C(8,3)+C(7,3)*C(4,2) +C(6;4)*C(2;1)+ C(5;5)*C(0;0) таких способов. Заметим что последний равный единице случай,соответствует 5 последовательным прыжкам по диагонали,которве кстати говоря являются самым коротким путем от лягушки к цапле. Сочетания сами Посчитайте по формуле.

Answer 2

Ну это решение еще нужно проверять. Так что еще может все поменяться.

Answer 3

С(0;0)=1

Answer 4

Я сейчас проверю это для случая когда 4*4 кочек. И там посчитаю. Проверю работает ли принцип там. Но должно все работать.

Answer 5

Да все работает. Я проверил на рисунке. Гарантирую верность решения.

Answer 6

Поясню почему там 10-2n. Тк мы выяснили что у нас 10-n прыжков. Но при этом n из них занимают диагонали. Поэтому остается 10-2n. Это самый труднопонимаемый момент в этом задании. Даже я сначало подумал что там тоже 10-n.