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

Проект МЦНМО
при участии
школы 57
Задача 35558
Темы:    [ Комбинаторика (прочее) ]
[ Принцип крайнего ]
[ Мощность множества. Взаимно-однозначные отображения ]
[ Упорядочивание по возрастанию (убыванию) ]
[ Оценка + пример ]
Сложность: 3
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Пусть M – конечное множество чисел. Известно, что среди любых трёх его элементов найдутся два, сумма которых принадлежит M.
Какое наибольшее число элементов может быть в M?


Подсказка

Рассмотрите либо четыре самых больших, либо четыре самых меньших числа.


Решение

  Пример множества из 7 элементов:  {–3, –2, –1, 0, 1, 2, 3}.
  Докажем, что множество  M = {a1, a1, ..., an}  из  n > 7  чисел требуемым свойством не обладает. Можно считать, что   a1 > a2 > a3 > ... > an   и  a4 > 0  (смена знаков всех элементов наше свойство не меняет). Тогда   a1 + a2 > a1 + a3 > a1 + a4 > a1,   то есть ни одна из сумм  a1 + a2a1 + a3  и  a1 + a4  множеству M не принадлежит. Кроме того, суммы  a2 + a3  и  a2 + a4  не могут одновременно принадлежать M, поскольку  a2 + a3 > a2 + a4 > a2.  Получается, что по крайней мере для одной из троек  (a1, a2, a3)  и  (a1, a2, a4)  сумма любых двух её элементов множеству M не принадлежит.


Ответ

7 элементов.

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

web-сайт
задача
олимпиада
Название Всероссийская олимпиада по математике
год
Год 2000
Этап
Вариант 5
Класс
Класс 10
задача
Номер 00.5.10.5

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

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