Условие
Имеется 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 троек.
Источники и прецеденты использования
