Задача 73554

Темы:    [ Процессы и операции ] [ Индукция (прочее) ] [ Двоичная система счисления ]

Сложность: 5- Классы: 7,8,9

Условие

Автор: Васильев Н.Б.

В бесконечной цепочке нервных клеток каждая может находиться в одном из двух состояний: «покой» и «возбуждение». Если в данный момент клетка возбудилась, то она посылает сигнал, который через единицу времени (скажем, через одну миллисекунду) доходит до обеих соседних с ней клеток. Каждая клетка возбуждается в том и только в том случае, если к ней приходит сигнал от одной из соседних клеток; если сигналы приходят одновременно с двух сторон, то они погашаются, и клетка не возбуждается. Например, если в начальной момент времени t = 0 возбудить три соседние клетки, а остальные оставить в покое, то возбуждение будет распространяться так, как показано на рисунке.

Пусть в начальный момент времени возбуждена только одна клетка. Сколько клеток будет находится в возбужденном состоянии через 15 мсек? через 65 мсек? через 1000 мсек? вообще через t мсек?

Что будет в том случае, если цепочка не бесконечная, а состоит из N клеток, соединённых в окружность,— будет ли возбуждение поддерживаться бесконечно долго или затухнет?

Решение

Решение. Достаточно проследить, как распространяется возбуждение от одиночной клетки первые десять-пятнадцать тактов (см.рис.), чтобы подметить следующие закономерности. 1. В момент времени t=2^k , где k=0, 1, 2, ... возбуждены только две клетки: x=-2^k и x=2^k . 2. В момент времени t=2^k-1 возбуждены 2^k клеток от x=-2^k+1 до x=2^k-1 с нечетными x . 3. Пусть 0 t<2^k . Тогда в момент времени 2^k+t возбуждено ровно вдвое больше клеток, чем в момент времени t . Для доказательства этих закономерностей (индукцией по k ) можно воспользоваться тем, что "волны возбуждения", рождаемые каждой из двух клеток, активных в момент 2^k , не перекрываются вплоть до момента времени t=2^k+1-1 и поэтому каждая из них устроена точно так же, как волна возбуждения от одной клетки при t<2^k . Теперь уже легко ответить на вопросы, поставленные в задаче. Через 15 мсек, как это видно и по рисунку, будет 16 возбужденных клеток. Через 64=2⁶ их будет две, поэтому через 65 – четыре. Для произвольного конкретного t можно подсчитать f(t) – количество возбужденных клеток в момент времени t ,– несколько раз последовательно применяя свойство3: каждый раз от t можно вычитать наибольшую возможную степень двойки; от этого f(t) уменьшится вдвое. Например:

Легко сформулировать ответ в общем виде, пользуясь двоичной системой счисления. Действительно, вычесть из числа наибольшую возможную степень двойки– это все равно что в его двоичной записи выбросить первую цифру. Таким образом, для всех t f(t) равно 2^m, где m - количество единиц в записи числа t по двоичной системе счисления.
Это правило легко доказывается по индукции, а для первых t вы можете его проверить– на рис.5 справа выписаны двоичные разложения чисел t . Обратите внимание на то, что расположение возбужденных клеток на рис.5 в точности совпадает с расположением единиц в треугольнике Паскаля по модулю два. Таким образом, мы одновременно решили такую задачу: сколько единиц в t -й строке треугольника Паскаля по модулю 2 , другими словами, сколько среди биномиальных коэффициентов C_t^k ( k=0, 1, ... t ) нечетных? Ответ на второй вопрос, поставленный в условии задачи– что будет, если N клеток расположить по окружности?– зависит, конечно, не только от N , но, вообще говоря, и от "начального состояния"– от того, какие клетки возбуждены в начальный момент времени. В этой задаче существует общее простое правило, позволяющее для каждого начального состояния указать, перейдут ли когда-нибудь все клетки в состояние покоя. Попробуйте найти его самостоятельно.

Источники и прецеденты использования

журнал
Название	"Квант"
год
Год	1970
выпуск
Номер	4
Задача
Номер	М19