Задача 65130

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

Сложность: 4- Классы: 10,11

Условие

По кругу расставлено 300 положительных чисел. Могло ли случиться так, что каждое из этих чисел, кроме одного, равно разности своих соседей?

Решение

  Предположим, что требуемая расстановка существует. Ясно, что наибольшее из чисел не может равняться разности соседей; значит, каждое из остальных чисел равно разности соседей. В частности, наибольшее число встречается ровно один раз; обозначим его через m.
  Пусть d – одно из наименьших чисел в круге. Рассмотрим любую из двух дуг между d и m; пусть на ней стоят подряд числа  d = a₀, a₁, ..., a_k = m.  Докажем индукцией по i, что  a_i+1 ≥ a_i. В базовом случае  i = 0  утверждение верно, ибо d – наименьшее число.
  Шаг индукции. Пусть  i > k  и  a_i–1 ≤ a_i. Тогда равенство a_i = a_i–1 – a_i+1  невозможно, ибо  a_i+1 > 0,  и поэтому  a_i = a_i+1 – a_i–1.  Значит,  a_i+1 > a_i.
  Мы заодно показали, что  a_i+1 = a_i + a_{i – 1}  при всех  i = 1, .., k – 1.
  Аналогично, если на другой дуге между d и m стоят подряд числа  d = b₀, b₁, ..., b_l = m,  то  b₀ ≤ b₁ ≤ ... ≤ b_l  и  b_i+1 = b_i + b_i–1  при всех
i = 1, 2, ..., l – 1.  Наконец, для числа  a₀ = b₀ = d  условие задачи также должно выполняться; без ограничения общности можно считать, что
d = a₁ – b₁;  тогда  a₂ = a₀ + a₁ = b₁ > a₁.
  Продолжим теперь последовательности a₀, a₁, ... и b₀, b₁, ... согласно формулам  a_i+1 = a_i + a_i–1  и  b_i+1 = b_i + b_i–1.  Докажем индукцией по i, что
a_i < b_i ≤ a_i+1.  Для  i = 1  это уже доказано выше. При  i = 2  из соотношений  b₀ = a₀ ≤ a₁ < b₁ = a₂  получаем  a₂ = a₁ + a₀ < b₁ + b₀ = b₂ ≤ a₂ + a₁ = a₃.
  Шаг индукции. Пусть  i ≥ 3.  По предположению индукции  a_i–2 < b_i–2 < b_i–1 ≤ a_i,  откуда  a_i = a_i–1 + a_i–2 < b_i–1 + b_i–2 = b_i ≤ a_i + a_i–1 = a_i+1.
  Итак,  a₀ = b₀ ≤ a₁ < b₁ ≤ a₂ < b₂ ≤ ... .  Значит, равенство  b_l = a_k  возможно лишь при  k = l + 1;  но тогда общее количество чисел в круге равно
k + l = 2l + 1,  что не может равняться 300. Противоречие.

Ответ

Не могло.

Замечания

Если число 300 заменить на любое нечётное число, то требуемая конфигурация будет существовать (в ней два равных минимальных числа будут стоять рядом). Условие положительности чисел также важно, иначе бы подошёл пример 0, 0, 0, ... или 0, 1, 1, 0, 1, 1, ..., 0, 1, 1.

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

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