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 последовательным прыжкам по диагонали,которве кстати говоря являются самым коротким путем от лягушки к цапле. Сочетания сами Посчитайте по формуле.