ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 73660
Темы:    [ Делимость чисел. Общие свойства ]
[ Последовательности (прочее) ]
[ Перебор случаев ]
Сложность: 5-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Автор: Ионин Ю.И.

а) Существует ли бесконечная последовательность натуральных чисел, обладающая следующим свойством: ни одно из этих чисел не делится на другое, но среди каждых трёх чисел можно выбрать два, сумма которых делится на третье?

б) Если нет, то как много чисел может быть в наборе, обладающем таким свойством?

в) Решите ту же задачу при дополнительном условии: в набор разрешено включать только нечётные числа.

Вот пример такого набора из четырёх чисел: 3, 5, 7, 107. Здесь среди трёх чисел 3, 5, 7 сумма  5 + 7  делится на 3; в тройке 5, 7, 107 сумма  107 + 5  делится на 7; в тройке 3, 7, 107 сумма  7 + 107  делится на 3; наконец, в тройке 3, 5, 107 сумма  3 + 107  делится на 5.


Решение

  в) К приведённой в условии последовательности из четырёх чисел 3, 5, 7, 107 можно добавить пятое число 10693:  10693 + 5  делится на 3,  10693 + 3  делится на 7,  10693 + 7  делится на 5,  10693 + 107  делится на 3 и на 5,  10693 + 7  делится на 107.
  Покажем, что из шести нечётных чисел нельзя образовать последовательности, удовлетворяющей условию задачи. Пусть a1, a2, a3, a4, a5, a6 – такие числа. Сделаем несколько предварительных замечаний.
  1) Если a, b, c – три члена нашей последовательности,  a > b > c,  то  b + c  не делится на a.
  Действительно,  b + c < 2a  и  b + c ≠ a,  так как a – нечётное число.
  2) Если a, b – два члена нашей последовательности,  a > b,  то  a + b  делится на все члены последовательности, меньшие b, кроме, может быть, одного.
  Действительно, если  a + b  не делится на два числа c и d, меньшие b, то  a + c  и  a + d  делятся на b, но тогда и  c – d  делится на b, что невозможно.
  3) Если a, b, c, d – четыре члена нашей последовательности,  a + b  и  a + c  делятся на d, то  b + c  не делится на d.
  Действительно, так как  a + b  и  a + c  делятся на d, то  2a + (b + c)  делится на d, в то время как 2a не делится на d (d – нечётное число и a не делится на d).
  Пусть  a1 > a2 > a3  – три наибольших из шести чисел a1, a2, ..., a6.
  Каждое из чисел  a1 + a2a1 + a3a2 + a3  согласно 2) делится не менее, чем на два из чисел a4, a5, a6 . В то же время 3) показывает, что у этих чисел нет среди чисел a4, a5, a6 общего делителя. Следовательно, каждое из чисел  a1 + a2a1 + a3a2 + a3  делится на два из чисел a4, a5, a6 и не делится на третье.
  Пусть  a1 + a2  делится на a4 и a5 и не делится на a6;  a1 + a3  делится на a4 и a6 и не делится на a5;  a2 + a3  делится на a5 и a6 и не делится на a4. Тогда числа  a1 + a5  и  a2 + a4  делятся на a3. Следовательно, на a3 делится и число  (a1 + a2) + (a4 + a5).
  В то же время  a1 + a2  делится на три из чисел a3, a4, a5, a6, a так как  a1 + a2  не делится на a6, то  a1 + a2  делится на a3, откуда следует, что
a4 + a5  делится на a3. Противоречие с 1).
  Таким образом, последовательность нечётных чисел с интересующим нас свойством может состоять самое большое из пяти чисел.

  б) Если последовательность состоит только из чётных чисел, то, не нарушая условия, можно их все разделить на 2. Будем поэтому считать, что в последовательности есть нечётные числа. В силу задачи в) их не более пяти.
  Замечания 1) – 3) справедливы теперь при некоторых дополнительных предположениях.
  В 1) нужно потребовать, чтобы a не равнялось  b + c;  2) справедливо, если число a не равно сумме никаких двух членов последовательности, а 3) справедливо, если d – нечётное число.
  Если члены последовательности a, b, c чётны, a d нечётно, то числа  a + d,  b + d  и  c + d  не делятся ни на a, ни на b, ни на c. Следовательно, числа  a + b,  a + c  и  b + c  делятся на d, что противоречит 3).
  Таким образом, в нашей последовательности не более двух чётных чисел. Пусть их два: a и b  (a > b).  Тогда число  a + b  делится на все нечётные члены последовательности и, следовательно, число a – наибольшее в последовательности.
  Если число a не равно сумме никаких двух членов последовательности, то, отбрасывая число b, мы получим последовательность, для которой без всяких ограничений справедливы замечания 1), 2), 3). Решение задачи в) показывает, что в такой последовательности не более пяти членов, то есть в исходной последовательности не более шести чисел.
  Предположим теперь, что число a равно сумме каких-либо двух нечётных членов последовательности. Если c – большее из этих нечётных чисел, то a < 2c.
  Выше уже говорилось, что число  a + b  делится на все нечётные члены последовательности.
  Следовательно,  a + b ≥ 2n,  где через n обозначено наименьшее общее кратное всех нечётных членов последовательности. c – делитель числа n, и так как  c ≠ n,  то  3c ≤ n  (c и n – нечётные числа). С другой стороны, так как  2c > a,  то  3c > 3/2 a > 3/4 (a + b) ≥ 3/2 n > n. Противоречие.
  Таким образом, в любом случае в нашей последовательности не более шести чисел.
  Вот пример шестичленной последовательности: 2, 3, 5, 7, 107, 10693.

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .