Задания
Версия для печати и копирования в MS Word
Задания Д19 C7 № 508651

Лягушка прыгает по вершинам шестиугольника ABCDEF, каждый раз перемещаясь в одну из соседних вершин.

а) Сколькими способами она может попасть из A в C за n прыжков?

б) Сколько таких способов при условии, что вершиной D пользоваться нельзя?

Спрятать решение

Решение.

а) Ясно, что после четного числа прыжков, лягушка может находиться только в вершинах A, C или E. Обозначим через a_k, c_k, e_k число путей длины 2k, ведущих из A в A, C и E соответственно. В силу симметрии c_k = e_k. Легко видеть, что выполняются равенства c_k плюс 1 = a_k плюс 3c_k (можно за два шага перейти из A в C, или за два шага перейти из Е, или сходить С-B-C или С-D-C), a_k плюс 1 = 2a_k плюс 2c_k (аналогично). Отсюда c_k плюс 2 = a_k плюс 1 плюс 3c_k плюс 1 = 2a_k плюс 2c_k плюс 3c_k плюс 1 = 2 левая круглая скобка c_k плюс 1 – 3c_k правая круглая скобка плюс 2c_k плюс 3c_k плюс 1 = 5c_k плюс 1 – 4c_k. Из начальных условий c_0 = 0, c_1 = 1. По индукции легко показать, что c_k= дробь: числитель: 4 в степени k минус 1, знаменатель: 3 конец дроби .

 

б) Сохраним обозначение ck из пункта а). Обозначим через bk число путей длины 2k – 1, ведущих из A в B. Тогда b_k плюс 1 = 3b_k (за два прыжка можно двумя способами вернуться из B в B и одним способом попасть из B в F). Но c_k = b_k, значит, c_k плюс 1 = 3c_k при k больше 0.

По-прежнему, c_1 = 1, следовательно, c_k = 3 в степени левая круглая скобка k–1 правая круглая скобка .

 

Ответ: а)  дробь: числитель: 2 в степени левая круглая скобка n правая круглая скобка минус 1, знаменатель: 3 конец дроби (n обязательно четное); б) 3 в степени левая круглая скобка дробь: числитель: n, знаменатель: 2 конец дроби минус 1 правая круглая скобка (n обязательно четное).

Спрятать критерии
Критерии проверки:

Критерии оценивания выполнения заданияБаллы
Верно получены все перечисленные (см. критерий на 1 балл) результаты.4
Верно получены три из перечисленных (см. критерий на 1 балл) результатов.3
Верно получены два из перечисленных (см. критерий на 1 балл) результатов.2
Верно получен один из следующих результатов:

— пример в п. а;

— обоснованное решение п. б;

— обоснование в п. в того, что S может принимать все целые значения (отличные от −1 и 1);

— обоснование в п. в того, что равенства S = −1 и S = 1 невозможны.

1
Решение не соответствует ни одному из критериев, перечисленных выше.0
Максимальный балл4
Источник: А. Ларин: Тренировочный вариант № 85.
Классификатор алгебры: Числа и их свойства