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

Проект МЦНМО
при участии
школы 57
Задача 78058
Темы:    [ Системы точек и отрезков. Примеры и контрпримеры ]
[ Задачи с ограничениями ]
Сложность: 4
Классы: 11
В корзину
Прислать комментарий

Условие

Имеется 1955 точек. Какое максимальное число троек можно из них выбрать так, чтобы каждые две тройки имели ровно одну общую точку?


Решение

  Выделим одну из троек  {A, B, C}.  Каждая из остальных троек содержит ровно одну из точек  A, B, C.  Рассмотрим два случая.
  1) Все остальные тройки содержат точку A. Тогда их не больше, чем непересекающихся пар, составленных из 1954 точек, то есть не больше 977. Такое число троек достигается, если разбить 1954 точки на 977 пар и к каждой из них присоединить точку A.
  2) Есть тройка  {A, D, E},  содержащая A, и тройка, содержащая B. Последняя тройка должна пересекаться с предыдущей – можно считать, что она имеет вид  {B, D, F}.  Рассмотрим любую тройку, отличную от трёх указанных. Если она содержит A, то она содержит и F (поскольку пересекается с  {B, D, F}),  поэтому есть не более одной такой тройки. Аналогично есть не более одной "дополнительной" тройки, содержащей B, (она должна содержать E) и не более одной, содержащей C. Итак, в этом случае троек не больше шести.


Ответ

977 троек.

Замечания

В книге "Алгебра и теория чисел" задача дана для 2000 точек.
В этом случае ответ: 999 троек.

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

книга
Автор Алфутова Н.Б., Устинов А.В.
Год издания 2002
Название Алгебра и теория чисел
Издательство МЦНМО
Издание 1
глава
Номер 2
Название Комбинаторика
Тема Комбинаторика
параграф
Номер 2
Название Принцип Дирихле
Тема Принцип Дирихле (прочее)
задача
Номер 02.027
олимпиада
Название Московская математическая олимпиада
год
Номер 18
Год 1955
вариант
Класс 10
Тур 2
задача
Номер 4

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

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