Задача 110130

Темы:    [ НОД и НОК. Взаимная простота ] [ Десятичная система счисления ] [ Упорядочивание по возрастанию (убыванию) ] [ Основная теорема арифметики. Разложение на простые сомножители ]

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

Условие

Автор: Храмцов Д.

Докажите, что из произвольного множества трёхзначных чисел, включающего не менее четырёх чисел, взаимно простых в совокупности, можно выбрать четыре числа, также взаимно простых в совокупности.

Решение

  Лемма. Из любого множества, состоящего не менее чем из пяти трёхзначных чисел, взаимно простых в совокупности, можно удалить одно число так, что оставшиеся также будут взаимно просты в совокупности.
  Доказательство. Обозначим через  M = {a₁, ..., a_k}  множество исходных чисел, через M_i – множество M без a_i, а через A_i – наибольший общий делитель чисел из M_i. Наибольший общий делитель любых чисел A_i и A_j,  i ≠ j,  равен наибольшему общему делителю всех чисел a₁, ..., a_k, то есть 1, следовательно, A₁, ..., A_k попарно взаимно просты.
  Если все они не равны 1, обозначим через p_i наибольший простой делитель A_i. В силу попарной взаимной простоты чисел A_i, числа p_i попарно различны, и можно считать, что  p₁ < ... < p_k.  Тогда A₁ ≥ 2,  A₂ ≥ 3,  A₃ ≥ 5,  A₄ ≥ 7,  A₅ ≥ 11.  Так как  a₁ ∈ M₂ ∩ M₃ ∩ M₄ ∩ M₅,  то a₁ делится на
A₂A₃A₄A₅ ≥ 3·5·7·11 = 3003,  что противоречит трёхзначности a₁.
  Следовательно, одно из чисел A_i равно 1, и числа в соответствующем множестве M_i взаимно просты в совокупности.
  Применяя лемму, из исходного множества можно последовательно удалить все числа, кроме четырёх, взаимно простых в совокупности.

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2003
Этап
Вариант	4
Класс
Класс	10
задача
Номер	03.4.10.7