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

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

Условие

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

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


Решение

  Лемма. Из любого множества, состоящего не менее чем из пяти трёхзначных чисел, взаимно простых в совокупности, можно удалить одно число так, что оставшиеся также будут взаимно просты в совокупности.
  Доказательство. Обозначим через  M = {a1, ..., ak}  множество исходных чисел, через Mi – множество M без ai, а через Ai – наибольший общий делитель чисел из Mi. Наибольший общий делитель любых чисел Ai и Aj,  i ≠ j,  равен наибольшему общему делителю всех чисел a1, ..., ak, то есть 1, следовательно, A1, ..., Ak попарно взаимно просты.
  Если все они не равны 1, обозначим через pi наибольший простой делитель Ai. В силу попарной взаимной простоты чисел Ai, числа pi попарно различны, и можно считать, что  p1 < ... < pk.  Тогда A1 ≥ 2,  A2 ≥ 3,  A3 ≥ 5,  A4 ≥ 7,  A5 ≥ 11.  Так как  a1M2M3M4M5,  то a1 делится на
A2A3A4A5 ≥ 3·5·7·11 = 3003,  что противоречит трёхзначности a1.
  Следовательно, одно из чисел Ai равно 1, и числа в соответствующем множестве Mi взаимно просты в совокупности.
  Применяя лемму, из исходного множества можно последовательно удалить все числа, кроме четырёх, взаимно простых в совокупности.

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

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

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

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