На бесконечном клетчатом листе белой бумаги n клеток закрашены в чёрный цвет. В моменты времени t = 1, 2, 3,... происходит одновременное перекрашивание всех клеток листа по следующему правилу: каждая клетка k приобретает тот цвет, который имело в предыдущий момент большинство из трёх клеток: самой клетки k и её соседей справа и сверху (если две или три из этих клеток были белыми, то k становится белой, если две или три из них были чёрными,— то чёрной).

а) Докажите, что через конечное время на листе не останется ни одной чёрной клетки.

б) Докажите, что чёрные клетки исчезнут не позже, чем в момент времени t = n.

   Решение

Темы:    [ Суммы числовых последовательностей и ряды разностей ] [ Геометрическая прогрессия ] [ Индукция (прочее) ]

Сложность: 3+ Классы: 9,10,11

Прислать комментарий

Условие

Бессмертная блоха прыгает по целым точкам на числовой прямой, стартуя с точки 0. Длина первого прыжка равна 3, второго – 5, третьего – 9, и так далее (длина k-го прыжка равна  2^k + 1).  Направление прыжка (вправо или влево) блоха выбирает самостоятельно. Может ли так случиться, что блоха рано или поздно побывает в каждой натуральной точке (возможно, побывав в некоторых точках больше, чем по разу)?

Решение

  Покажем, как блоха может прыгать, попадая последовательно в точки 0, 1, 2, 3, ... (каждый раз – за несколько прыжков). Для этого достаточно показать, как, попав в точку n, за несколько прыжков попасть в точку  n + 1.
  Пусть до попадания в точку n блоха совершила  k – 1  прыжок (то есть длина следующего прыжок будет равна   2^k + 1).  Тогда она может сделать
l = 2^k  прыжков влево, а затем один прыжок вправо. В результате она сместится вправо на
(2^k+l + 1) – (2^k + 1) – (2^k+1 + 1) – ... – (2^k+l–1 + 1) = (2^k+l – 2^k – 2^k+1 – ... – 2^k+l–1) + 1 – 2^k = 2^k + 1 – 2^k = 1,  что и требовалось.

Ответ

Может.

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