Question

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

Answer 1

Что за крышевышибательная задача?? ; )

Answer 2

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

Допустим, у нас есть L досок на заборе. Первый воробей садится на первую доску, и остаются L-1 свободных досок. Второй воробей садится на вторую доску (через одну от первой), и остается L-2 свободных досок. Третий воробей садится на четвертую доску (через две от второй), и остается L-4 свободных досок. Каждый следующий воробей будет садиться на доску, которая находится вдвое дальше от предыдущей занятой доски.

Для того чтобы все воробьи сели без свободных досок между соседями, нам необходимо, чтобы число свободных досок стало равным нулю, и воробьи заняли все доски в обратном порядке. Пусть k - количество воробьев, тогда число свободных досок можно выразить как:

L - (1 + 2 + 4 + 8 + ... + 2^(k-1))

Это представляет собой сумму первых k-1 степеней двойки. Известно, что сумма первых n степеней двойки равна 2^n - 1:

1 + 2 + 4 + 8 + ... + 2^(k-1) = 2^k - 1

Теперь, чтобы число свободных досок стало равным нулю, нужно решить уравнение:

L - (2^k - 1) = 0

2^k = L + 1

k = log2(L + 1)

Округлим k до наименьшего целого числа (поскольку нам нужно наименьшее L) и подставим обратно в уравнение:

L = 2^(log2(L + 1)) - 1 L = L + 1 - 1 L = L

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