For a given integer n≥3, let S1,S2,…,Sm be distinct three-element subsets of the set {1,2,…,n} such that for each 1≤i,j≤m;i≠j the sets Si∩Sj contain exactly one element. Determine the maximal possible value of m for each n.
Problem
Source: Turkey EGMO TST 2014 P6
Tags: combinatorics
07.10.2016 00:09
Wrong...
07.10.2016 21:29
So, is the bound i got the best?
07.10.2016 22:59
Answer: m=1 if n=3 or n=4. m=2 if n=5 m=4 if n=6 m=7 if 7≤n≤16 m=⌊n−12⌋ if n≥17 n=3,4 are easy cases. When n=5, after two set we can't proceed anymore. Example for 2 is easy. When n=6, we see that an element cannot be in three distinct sets. For all 1≤i≤n, let ai be the number of sets in S1,S2,…,Sm which include i. Hence 3m=∑6i=1ai≤2∗6=12, so m≤4. Example for m=4: {1,2,3},{3,4,5},{1,5,6},{2,4,6}. Now let n≥7. Claim: If an element is in at least 4 sets, then it is in all sets. Proof: Assume, in contrary, that there exists an element p in at least 4 sets among S1,S2,…,Sm, but not in all of them. WLOG p∈S1,S2,S3,S4 and p∉S5. Therefore S5 should coincide with S1,S2,S3,S4, but not with p. Hence S5 contains at least 4 elements, contradiction.◻ Now take an element q which is in a maximal number of sets. Case 1: q is in at least 4 sets. Therefore, by our claim, q is in all sets. Then Si∖{q} are all distinct for 1≤i≤m. Then 2m=|S1∖{p}∪...∪Sm∖{p}|≤n−1, so m≤n−12, and since m is an integer m≤⌊n−12⌋. Case 2: q is in exactly 3 sets. WLOG q∈S1,S2,S3. Then any other set S must coincide with S1,S2,S3, but not with q. Therefore S should have one element from each Si∖{q}. So S is cointained in T={(S1∪S2∪S3)∖{q}}, which contains 6 elements. Hence, as we showed for n=6, at most 4 sets can be included in T. So m≤3+4=7. Case 3: q is in exactly two sets. Let {q,a,b},{q,c,d} be sets in {Si}. By the maximality of sets including q, any other set must include exactly one element among a and b, and one element among c and d. WLOG it includes a and d. Call this set {a,d,e}. Now take a set A that hasn't been used. Since any element is in at most two sets, and A coincides {q,a,b},{q,c,d},{a,d,e}, A must be {b,c,e}. Now any element in {q,a,b,c,d,e} belongs to two sets, so we can't add more sets. Hence m≤4. Case 4: q is in exactly one set. Well, it is a very degenerate case. We can't add more sets, since any element is in at most one set. Hence m≤1. In total, we got that m≤max, which is exactly the bound in the answer. Example for m=7, when 7\leq n\leq 16: \{1,2,3\},\{1,4,5\},\{1,6,7\},\{2,4,6\},\{2,5,7\},\{3,4,7\},\{3,5,6\}. In order to achieve m=\lfloor\frac{n-1}{2}\rfloor for n\geq 17, take the element 1 and partition \{2,\dots,n\} into pairs (maybe except of a single number). Make triples with 1 and the pairs.
13.01.2017 20:38
A good way to get intuition on this problem is Schliesser's Chicken Foot Method. After that, the proof can be written up as an amalgamation of combinatorial observations, and with the above construction: We write the extremal family given n as \mathcal{A}; what we desire is |\mathcal{A}|. I claim that |\mathcal{A}|=\left\lfloor\tfrac{n-1}{2}\right\rfloor. Surely it can be no less; the construction given by math90 guarantees this. Consider WLOG A=\{1,2,3\}\in\mathcal{A}. By the condition, we may partition \mathcal{A}\setminus\{A\} into C_1,C_2,C_3 where A_i\cap A=\{i\}\iff A\neq A_i\in C_i, which must always be one of \{1\},\{2\},\{3\}. Also note that A_x,A_y\in C_i\implies A_x\cap A_y=\{i\}. Suppose |\mathcal{A}|\geq 8 (indeed by the construction this can only not occur when n\leq 15). Then by PHP it follows that WLOG |C_1|\geq 3. Again WLOG suppose I=\{1,4,5\},\ J=\{1,6,7\},\ K=\{1,8,9\}\in C_1. Then for A_z\in C_2 to hold we must have 2, one of \{4,5\}, one of \{6,7\}, and one of \{8,9\} in A_z, which is clearly impossible. Hence C_2,\ C_3 (the latter by similar argument) are empty. The construction follows, along with some amount of workup for n\leq 15\ \Box
14.01.2017 07:03
If anyone is curious, attached is a (rather simple) Chickenfoot Diagram for the Problem. Apologies for the poor scan quality :/
Attachments:
