7-я Международная Жаутыковская олимпиада, 2011 год

Найдите наибольшее возможное число множеств, удовлетворяющих одновременно следующим условиям:
i) каждое множество состоит из 4 элементов;
ii) любые два различных множества имеют ровно два общих элемента;
iii) никакие два элемента не принадлежат одновременно всем множествам.

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

Максимальное количество — 7.

Сначала докажем, что это число не больше 7. Предположим, что два множества — это {a,b,c,d} и {a,b,e,f}.

Если хотя бы 4 набора содержат и a, и b, предположим, что это {a,b,c,d},{a,b,e,f},{a,b,g,h} и {a,b,i ,j}. Из задачи мы знаем, что хотя бы один набор не содержит ни a, ни b, этот набор содержит как минимум 5 элементов, противоречие.

Если ровно 3 набора содержат и a, и b, то говорят {a,b,c,d},{a,b,e,f} и {a,b,g,h}. Легко увидеть, что любой другой набор должен содержать один из a, b, один из c, d, один из e, f и один из g, h. Не более одного набора содержит c,e,g или d,f,h; не более одного набора содержит c,e,h или d,f,g; не более одного набора содержит c,f,g или d,e,h; не более одного набора содержит c,f,h или d,e,g. Таким образом, существует не более 3+4=7 наборов.

Если ровно 2 набора содержат и a, и b, то, кроме набора {c,d,e,f}, другие наборы должны содержать один из a,b, один из c,d, один из e,f и еще один элемент. . Не более одного набора содержит a,c,e или b,d,f; не более одного набора содержит a,c,f или b,d,e; не более одного набора содержит a,d,e или b,c,f; не более одного набора содержит a,d,f или b,c,e. Таким образом, существует не более 2+1+4=7 наборов.

Наконец, множества {0,1,2,4},{0,2,3,5},{0,3,4,6},{0,4,5,7},{0,5,6 ,1},{0,6,7,2} и {0 7,1,3} удовлетворяют условию, поэтому максимальное количество наборов равно 7