Find the maximum number of sets which simultaneously satisfy the following conditions: i) any of the sets consists of $4$ elements, ii) any two different sets have exactly $2$ common elements, iii) no two elements are common to all the sets.
Problem
Source:
Tags: combinatorics unsolved, combinatorics
Yunhao Fu
17.01.2011 10:14
The maximum number is 7. First we prove that the number is not greater than 7. Suppose two of the sets are {a,b,c,d} and {a,b,e,f}. If at least 4 sets contain both a and b, suppose they are {a,b,c,d},{a,b,e,f},{a,b,g,h} and {a,b,i,j}. From the problem we know at least one set doesn't contain both a and b, this set contains at least 5 elements, contradiction. If exactly 3 sets contain both a and b, saying {a,b,c,d},{a,b,e,f} and {a,b,g,h}. It is easily to seen that any other set must contain one of a,b ,one of c,d ,one of e,f ,and one of g,h. At most one set contains c,e,g or d,f,h; at most one set contains c,e,h or d,f,g; at most one set contains c,f,g or d,e,h; at most one set contains c,f,h or d,e,g. So there are at most 3+4=7 sets. If exactly 2 sets contain both a and b, then except the set {c,d,e,f}, other sets must contain one of a,b ,one of c,d ,one of e,f ,and one other element. At most one set contains a,c,e or b,d,f; at most one set contains a,c,f or b,d,e; at most one set contains a,d,e or b,c,f; at most one set contains a,d,f or b,c,e. So there are at most 2+1+4=7 sets. Finally, the sets {0,1,2,4},{0,2,3,5},{0,3,4,6},{0,4,5,7},{0,5,6,1},{0,6,7,2} and {0 7,1,3} satisfy the condition, so the maximum number of sets is 7.
mavropnevma
17.01.2011 10:36
A more symmetric model for $7$ sets is $abcd, abxy, cdxy, acxz, bdxz, adyz, bcyz$, with each of the $7$ elements $a,b,c,d,x,y,z$ belonging to exactly $4$ sets and each of the $21$ pairs of elements belonging to exactly $2$ sets. This is therefore a symmetric BIBD (balanced incomplete blocks design) of the type $(7,4,2)$. Notice that without condition iii) we could have infinitely many such sets (a common pair, adjoined to infinitely many disjoint pairs). It is interesting to note the similarity with http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=386835, where the conditions were that all intersections of two sets have exactly one element, and no ellement is common to all sets, with the answer $13$, given by the model symmetric BIBD of the type $(13,4,1)$, the finite projective plane of order $3$.
arshakus
27.02.2011 07:02
I solved this problem during the competition, and it is really not hard but very nice!
spanferkel
28.02.2011 13:08
it was also posted here: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=388271 - my solution is quite similar to Yunhao Fu's one.