Назад
Задача

Имеется 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 троек.

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет