РЕШУ ОЛИМП: задания, ответы, решения

Варианты заданий

Версия для печати и копирования в MS Word

Тип 0 № 512 Добавить в вариант

Хромой король может ходить вправо, вниз, вправо вниз и влево вниз на одну клетку. Сколько у него способов добраться из левой верхней клетки доски $3\times200$ в правую нижнюю?

Решение.

Запишем в каждую клетку таблищы количество способов туда добраться. Тогда в левом верхнем углу будет стоять число 1, а в каждой из остальных клеток будет сумма трёх соседних чисел сверху и числа слева.

1	1	1	1	1	...	1	1
2	5	8	11	14	...	596	598
7	22	46	79	121	...	?	?

В каждую клетку первой строки можно попасть только слева, поэтому первая строка заполнена единицами. Вторая строка начинается с двойки, а каждое следующее число, кроме последнего, на три больше предыдущего. Последнее число во втрой строке больше предыдущего только на два, потому что в эту клетку нельзя попасть слева сверху.

Числа в третьей строчке строятся по следуюшему закону:

$7=2 плюс 5,$

$22=7 плюс левая круглая скобка 2 плюс 5 плюс 8 правая круглая скобка = левая круглая скобка 2 плюс 5 правая круглая скобка плюс левая круглая скобка 2 плюс 5 плюс 8 правая круглая скобка ,$

$46=22 плюс левая круглая скобка 5 плюс 8 плюс 11 правая круглая скобка = левая круглая скобка 2 плюс 5 правая круглая скобка плюс левая круглая скобка 2 плюс 5 плюс 8 правая круглая скобка плюс левая круглая скобка 5 плюс 8 плюс 11 правая круглая скобка$

и так далее. Последнее число равно

$левая круглая скобка 2 плюс 5 правая круглая скобка плюс левая круглая скобка 2 плюс 5 плюс 8 правая круглая скобка плюс левая круглая скобка 5 плюс 8 плюс 11 правая круглая скобка плюс \ldots плюс левая круглая скобка 593 плюс 596 плюс 598 правая круглая скобка плюс левая круглая скобка 596 плюс 598 правая круглая скобка .$ $левая круглая скобка 2 плюс 5 правая круглая скобка плюс левая круглая скобка 2 плюс 5 плюс 8 правая круглая скобка плюс левая круглая скобка 5 плюс 8 плюс 11 правая круглая скобка плюс$
$плюс \ldots плюс левая круглая скобка 593 плюс 596 плюс 598 правая круглая скобка плюс левая круглая скобка 596 плюс 598 правая круглая скобка .$

В этой сумме 2 и 598 учитываются два раза, а все остальные числа по три раза. Значит, искомое число составляет

$2 левая круглая скобка 2 плюс 598 правая круглая скобка плюс 3 левая круглая скобка 5 плюс 8 плюс \ldots плюс 596 правая круглая скобка =1200 плюс 3 умножить на 601 умножить на 99=179 697.$

Альтернативный способо решения заключается в том, чтобы заметить, что хромой король делает всего два хода вниз. После этого можно посчитать, сколько способо выбрать момент, в который делаются эти ходы это количество способов зависит от того, какие именно из возможных ходов делаются. Это решение требует большого разбора случаев.

Ответ: 179 697.

Аналоги к заданию № 494: 512 Все

Решение · Критерии · Помощь