Задача 64346

Темы:    [ НОД и НОК. Взаимная простота ] [ Числовые неравенства. Сравнения чисел. ] [ Принцип крайнего (прочее) ] [ Примеры и контрпримеры. Конструкции ]

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

Условие

Автор: Берлов С.Л.

На доске написали 100 попарно различных натуральных чисел a₁, a₂, ..., a₁₀₀. Затем под каждым числом a_i написали число b_i, полученное прибавлением к a_i наибольшего общего делителя остальных 99 исходных чисел. Какое наименьшее количество попарно различных чисел может быть среди b₁, b₂, ..., b₁₀₀?

Решение

  Если  a₁₀₀ = 1  и  a_i = 2i  при  i = 1, 2, ..., 99,  то  b₁ = b₁₀₀ = 3,  так что среди чисел b_i будет не больше 99 различных.
  Докажем, что среди чисел b_i всегда найдутся 99 различных. Можно считать, что  a₁ < a₂ < ... < a₁₀₀.

  Первый способ. Пусть d_k – наибольшее из чисел d₁, ..., d₁₀₀. Тогда при  i ≠ k  числа a_i делятся на d_k. Следовательно, при  i < j  и  i ≠ k ≠ j  разность  a_j – a_i  также делится на d_k. Поскольку она положительна,  a_j – a_i ≥ d_k ≥ d_i.  Поэтому  b_j > a_j ≥ a_i + d_i = b_i,  откуда  b_i ≠ b_j.  Итак, все 99 чисел b_i  (i ≠ k)  различны.

  Второй способ. Обозначим  c_i = a_i+1 – a_i.  Пусть c_m – минимальное из чисел c₁, c₂, ..., c₉₉. Докажем, что  b_i < b_j,  если  i < j  и  i ≠ m + 1 ≠ j.  Разберём два случая.
  1)  i < j – 1.  Тогда  i ≤ 98,  и числа a_i+1 и a_i+2 делятся на d_i. Значит,  d_i ≤ a_i+2 –  a_i+1 < a_j – a_i,  откуда  b_i = a_i + d_i < a_i + (a_j – a_i) = a_j < b_j.
  2)  j = i + 1.  Тогда  i ≠ m + 1  и  i ≠ m.  Значит, числа a_m и a_m+1 делятся на d_i. Отсюда  d_i ≤ a_m+1 – a_m = c_m ≤ c_i,  следовательно,
b_i = a_i + d_i ≤ a_i + c_i = a_i+1 = a_j < b_j.

Ответ

99.

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2012-2013
этап
Вариант	5
класс
Класс	9
задача
Номер	9.3