Итак, четвертая задача. Там довольно длинное условие, поэтому я буду сразу рисовать картинку. Значит, нам дан шестиугольник A, B, C, D, E, F, и по нему прыгает лягушка. Значит, она каждый раз прыгает в одну из соседних вершин. И через An обозначено количество способов попасть из вершины A в вершину A за n прыжков. Требуется найти рекуррентное соотношение для An. Ну и формулу для нахождения последовательности An. Ну прежде всего заметим, что если мы будем двигаться из вершины A, то, двигаясь нечетное количество шагов, мы окажемся в вершинах либо B, либо D, либо F. А за четное количество шагов мы можем попасть в вершины A, C и E. Поэтому за нечетное количество шагов мы в вершину A мы попасть не можем. И A при нечетных индексах оно всегда равно нулю. Поэтому нам нужно найти только A с четными индексами. Давайте подумаем, какие мы можем написать рекуррентные соотношения. Допустим, у меня An – четное число, и мы хотим выразить An через предыдущие Ai-тые. Как мы это сделаем? Заметим, что количество способов попасть в A оно сильно коррелирует с тем, сколькими способами можно попасть из A в C и из A в E. Давайте введем две вспомогательные последовательности Cn и En. Это будет количество способов попасть из A в C (или из A в E) за n прыжков. Ну вот давайте посчитаем. Пусть я хочу посчитать количество способов попасть из A и A за n прыжков. Посмотрим, где я был на два прыжка назад. Значит, если я был в вершине A через (n − 2) прыжка, то мне осталось 2 прыжка, и я могу сделать, вернуться в A двумя способами: либо прыгнуть в B и вернуться обратно, либо прыгнуть в F и вернуться обратно. То есть у меня есть 2 способа попасть из A в A за 2 прыжка. Но если я 2 прыжка назад был в C, то мне нужно прыгнуть в B, потом в A. Если я был в E, то мне нужно прыгнуть в F, потом в A. Заметим, что из симметрической картинки очевидно, что Cn = En, потому что они симметрично находятся относительно A, поэтому это равенство можно переписать как: 2An − 2 + 2Cn − 2. Теперь запишем аналогичное соотношение для Cn. Допустим, мы хотим попасть в C за n прыжков и отойдем снова на 2 прыжка назад. Значит, если мы были в A 2 прыжка назад, то мы должны просто прыгнуть в B и в C. И никаким другим способом попасть за 2 прыжка из A в C не получится, поэтому у нас тут стоит коэффициент 1. Теперь посчитаем количество способов попасть из C в C за 2 прыжка. Ну это ровно 2, мы уже это считали. Нужно либо прыгнуть либо из C в B и потом обратно, либо из C в D и потом обратно. То есть будет 2Cn − 2. Ну еще двумя способами можно попасть из E за 2 прыжка. Таким образом, будет вот такое соотношение. Пользуясь равенством Cn = En, мы получаем, что Cn = (An − 2) + (3Cn − 2). Ну смотрите, мы получили 2 уравнения. Сейчас мы из них выведем рекуррентное соотношение на An. А именно можно выразить Cn из этого верхнего равенства и поставить его в нижнее. Ну давайте это сделаем. Значит, (2Cn − 2) = An − (2An − 2). И вот это мы поставим в нижнее равенство. Ну для удобства можно его умножить на 2. Тогда у меня будет такое равенство: (An + 2) − 2An = 2Cn. 2Cn – это у меня будет 2An − 2 + 3 × (2Cn − 2), то есть подставляем вот это соотношение, получаем здесь 3(An − (2An − 2)). Ну смотрите, таким образом, мы получили соотношение, в которое включаются только элементы последовательности An, и значит мы сейчас можем вывести рекуррентное соотношение на An и потом найти формулу для нахождения этой последовательности. Так, давайте я перейду к преподаванию на следующую доску. Значит чему это у нас равносильно? Давайте я здесь приведу подобные. Значит, An + 2 у нас будет коэффициент 1. Тут будет (− 2An) и тут стоит (+ 3An), то есть это будет (− 5An). И тут будет (2An −2) − (6An − 2), то есть (− 4An − 2). Таким образом, у меня здесь получается следующее рекуррентное соотношение: (An + 2) − 5An + (4An − 2) = 0. Ну видно, что у нас An + 2 выражается через предыдущие 2 члена, то есть если мы записываем это как четную последовательность, то у нас будет все равно квадратное уравнение. Фактический многочлен будет выглядет как: λ² – 5λ + 4 = 0. У него есть 2 корня: λ1,2. Ну тут можно просто по формуле это посчитать, что это будет 1 и 4. Таким образом, последовательность... Ну давайте я ее обозначу A', чтобы не путать. Значит, у меня A'n = A2n. Тогда A'n записывается как: (C1 × λ1 в степени n) + (C2 × λ2 в степени n) = (C1 × 1 в степени n) + (C2 × 4 в степени n). Ну теперь нужно подставить начальные значения и найти коэффициенты C1 и C2. Давайте подставим. Ну подставляем сначала A2. Значит, чтобы попасть из вершины A в вершину A за 2 шага, это можно сделать двумя способами: прыгнуть из A в B и вернуться и прыгнуть из A в F и вернуться. Значит, A2 у меня равно 2, и это будет равно A'1, то есть равно C1 + 4C2. Ну посчитаем A4. Так, давайте тут тоже мы картинку нарисуем небольшую, чтобы было понятно, что тут происходит. [ШУМ] Вот, ну можно, конечно, воспользоваться рекуррентным соотношением. Ну давайте так найдем: значит, мы хотим попасть из A в A за 4 хода. Значит, мы сделаем следующее: либо мы бежим в C, а потом бежим обратно, либо бежим в E, а потом бежим обратно. Это 2 способа. Либо мы через 2 шага были все еще в A. Тогда мы из A в A попали двумя способами и потом еще раз двумя способами. То есть всего будет 4 способа. Таким образом, A4 у меня равно 6. И это будет A'2, то есть C1 + C2 × 4², значит 16C2. Ну окей, но у нас есть система из двух уравнений с двумя неизвестными, давайте ее решим. Вычтем из второго уравнений первое, получим 12C2 = 6 – 2 = 4. Таким образом, C2 у меня равно 1/3. Ну отсюда можно легко получить C1. Из первого уравнения C1 = 2 – 4 × 1/3 = 2/3. Таким образом, последовательность A2n, которая равна A'n, находится по следующей формуле: это будет 2/3 + 1/3 × 4 в степени n. Ну или можно привести к общему знаменателю и написать: (2 + 4 в степени n)/3. [ШУМ] Вот мы нашли последовательность A2n. Задача решена.