На недавней математической олимпиаде командам-участницам были предложены девять задач. В итоге получилось, что каждая команда решила ровно три задачи, каждые две команды решили разные наборы задач и для любых трех команд можно найти задачу, которую не решила ни одна из них. Какое наибольшее количество команд могло участвовать в этой олимпиаде?
Подсказка
Назовём две непересекающиеся тройки задач запрещённой парой, если задачи, не входящие ни в одну из этих двух троек, образуют выбранную тройку.
Решение
Ответ: 56.
Решение: Пример на 56 команд получаем, выбрав 8 задач и рассмотрев все 56 составленных из них троек: они удовлетворяют всем условиям задачи. Допустим, мы выбрали больше 56 троек задач. Назовём две непересекающиеся тройки задач запрещённой парой, если задачи, не входящие ни в одну из этих двух троек, образуют выбранную тройку. Понятно, что хотя бы одна из двух троек, образующих запрещённую пару, не должна быть выбранной. Поскольку из шести задач можно выбрать три 
способами, каждая выбранная тройка порождает 10 запрещённых пар, причём, очевидно, разные тройки порождают разные запрещённые пары. При этом для каждой тройки задач существует 20 не пересекающихся с ней, то есть каждая тройка входит не больше, чем в 20 запрещённых пар. Если мы выбрали хотя бы 57 троек, у нас не меньше 570 запрещённых пар, в которые входит не менее 
различных троек задач. Но из 9 задач можно образовать лишь 
тройки, поэтому невыбранными останутся максимум 27 троек. Значит, какие-то две выбранные задачи образуют запрещённую тройку. Противоречие.