Задача М19‍‍

Достаточно проследить, как распространяется возбуждение от одиночной клетки первые десять — пятнадцать тактов (рис. 5), чтобы подметить следующие закономерности.

1. В момент времени $t=2^k$‍,‍ где $k=0$‍,‍ 1, 2, $\ldots$‍‍ возбуждены только две клетки: $x=-2^k$‍‍ и $x=2^k$‍.‍
2. В момент времени $t=2^k-1$‍‍ возбуждены $2^k$‍‍ клеток от $x=-2^k+1$‍‍ до $x=2^k-1$‍‍ с нечётными $x$‍.‍
3. Пусть $0\le t\lt2^k$‍.‍ Тогда в момент времени $2^k+t$‍‍ возбуждено ровно вдвое больше клеток, чем в момент времени $t$‍.‍

Для доказательства этих закономерностей (индукцией по $k$‍)‍ можно воспользоваться тем, что «волны возбуждения», рождаемые каждой из двух клеток, активных в момент $2^k$‍,‍ не перекрываются вплоть до момента времени $t=2^{k+1}-1$‍‍ и поэтому каждая из них устроена точно так же, как волна возбуждения от одной клетки при $t\lt2^k$‍.‍

Теперь уже легко ответить на вопросы, поставленные в задаче. Через 15 мс, как это видно и по рисунку, будет 16 возбуждённых клеток. Через $64=2^6~\text{мс}$‍‍ их будет две, поэтому через 65 — четыре. Для произвольного конкретного $t$‍‍ можно подсчитать $f(t)$‍‍ — количество возбуждённых клеток в момент времени $t$‍,‍ — несколько раз последовательно применяя свойство 3: каждый раз от $t$‍‍ можно вычитать наибольшую возможную степень двойки; от этого $f(t)$‍‍ уменьшится вдвое. Например: $$ \begin{alignat*}{5} 1000{}-{}2^9{}={}&&1000{}-{}&&512{}={}&&488,\qquad&&f(1000){}={}\\ 488{}-{}2^8{}={}&& 488{}-{}&&256{}={}&&232,\qquad&{}={}&2f(488){}={}\\ 232{}-{}2^7{}={}&& 232{}-{}&&128{}={}&&104,\qquad&{}={}&4f(232){}={}\\ 104{}-{}2^6{}={}&& 104{}-{}&& 64{}={}&& 40,\qquad&{}={}&8f(104){}={}\\ 40{}-{}2^5{}={}&& 40{}-{}&& 32{}={}&& 8,\qquad&{}={}&16f(40){}={}\\ 8{}-{}2^3{}={}&& 8{}-{}&& 8{}={}&& 0,\qquad&{}={}&32f(8){}={}&64. \end{alignat*} $$

Легко сформулировать ответ в общем виде, пользуясь двоичной системой счисления‍.

Действительно, вычесть из числа наибольшую возможную степень двойки — это всё равно что в его двоичной записи выбросить первую цифру. Таким образом, для всех $t$‍‍ $$ f(t)=2^m, $$ где $m$‍‍ — количество единиц в записи числа $t$‍‍ по двоичной системе счисления. Это правило легко доказывается по индукции, а для первых $t$‍‍ вы можете его проверить — на рисунке 5 справа выписаны двоичные разложения чисел $t$‍.‍

Вероятно, читатели журнала, которые помнят статью Д. Б. Фукса и М. Б. Фукса «Арифметика биномиальных коэффициентов»‍, обратили внимание на то, что расположение возбуждённых клеток на рисунке 5 в точности совпадает с расположением единиц в треугольнике Паскаля по модулю два (изображённом на обложке «Кванта» № 6). Таким образом, мы одновременно решили такую задачу: сколько единиц в $t$‍‍-й строке треугольника Паскаля по модулю 2, другими словами, сколько среди биномиальных коэффициентов $C_t^k$‍‍ ($k=0$‍,‍ 1, $\ldots$‍,‍ $t$‍)‍ нечётных?

Ответ на второй вопрос, поставленный в условии задачи — что будет, если $N$‍‍ клеток расположить по окружности? — зависит, конечно, не только от $N$‍,‍ но, вообще говоря, и от «начального состояния» — от того, какие клетки возбуждены в начальный момент времени. В этой задаче существует общее простое правило, позволяющее для каждого начального состояния указать, перейдут ли когда-нибудь все клетки в состояние покоя. Попробуйте найти его самостоятельно.