Олимпиада имени Леонарда Эйлера 2018-2019 учебный год, II тур заключительного этапа

Дано натуральное число $k$. В городе несколько детей, они ходят в несколько кружков. Известно, что в каждый кружок ходит не более $3k$ детей, любой ребёнок ходит ровно в три кружка, и для любых двух детей есть кружок, в которой оба они ходят. Какое наибольшее количество детей может быть в городе? ( И. Богданов, Г. Челноков )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.    
Ответ. $7k.$
Решение. Пример. Разобьём $7k$ детей на 7 групп (пронумерованных от 1 до 7) по $k$ детей в каждой и составим 7 кружков из детей групп $(1, 2, 3);$ $(1, 4, 5);$ $(1, 6, 7);$ $(2, 4, 6);$ $(2, 5, 7);$ $(3, 4, 7);$ $(3, 5, 6).$ Нетрудно проверить, что все условия выполнены. Оценка. Если все кружки состоят из не более, чем $3(k-1)$ детей, можно заменить $k$ на $k-1$ (и доказать, что число детей не превосходит $7(k-1)$). Таким образом, можно считать, что в одном кружке A есть хотя бы $3k-2$ ребёнка. Можно считать также, что есть ребёнок $s$ вне $A$, иначе число детей не больше $3k$. Три кружка, в которые ходит $s$, покрывают $A$ (так как у $s$ есть общий кружок с любым ребёнком из $A$). Значит, есть кружок, отличный от $A$ и пересекающийся с $A$ хотя бы по $k$ детям. Пусть $d$ — наибольшее количество детей в пересечении двух различных кружков; по доказанному выше, $d \ge k.$ Рассмотрим кружки $B$ и $C,$ пересекающиеся по $d$ детям. Пусть $X$ — пересечение кружков $B$ и $C$, а $Y$ — множество всех детей, не ходящих ни в $B$, ни в $C.$ Пусть $x$ — ребёнок из $X.$ Он ходит в $B,$ $C$ и в какой-то третий кружок $D_x$, в который по условию должны ходить все дети из $Y.$ Если для какого-то ребёнка $z$ из $X$ его третий кружок $D_z$ отличен от $D_x$, то $D_z$ и $D_x$ пересекаются хотя бы по $Y$, откуда $|Y| \le d;$ значит, общее число детей $|B|+|C|-|X|+|Y|$ не превосходит $3k+3k-d+d = 6k.$ Иначе кружок $D_x$ содержит всех детей из $X$ и $Y$, то есть $|X|+|Y| \le 3k,$ откуда общее число детей не больше $3k+3k-2|X|+(|X|+|Y|) \le 9k-2d \le 7k.$ Замечание. При ограничении на размер кружка $3k+1$ или $3k+2$ в задаче будут получаться ответы $7k+1$ и $7k+4,$ соответственно.