Задача 65254

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

Сложность: 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,  что и требовалось.

Ответ

Может.

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Вариант	2014/2015
этап
Вариант	5
класс
Класс	11
задача
Номер	11.5