For a given integer $n\ge3$, let $S_1, S_2,\ldots,S_m$ be distinct three-element subsets of the set $\{1,2,\ldots,n\}$ such that for each $1\le i,j\le m; i\neq j$ the sets $S_i\cap S_j$ 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\leq n\leq 16$ $m=\lfloor\frac{n-1}{2}\rfloor$ if $n\geq 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\leq i\leq n$, let $a_i$ be the number of sets in $S_1, S_2,\ldots,S_m$ which include $i$. Hence $3m=\sum_{i=1}^6 a_i\leq 2*6=12$, so $m\leq 4$. Example for $m=4$: $\{1,2,3\},\{3,4,5\},\{1,5,6\},\{2,4,6\}$. Now let $n\geq 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 $S_1, S_2,\ldots,S_m$, but not in all of them. WLOG $p\in S_1,S_2,S_3,S_4$ and $p\notin S_5$. Therefore $S_5$ should coincide with $S_1,S_2,S_3,S_4$, but not with $p$. Hence $S_5$ contains at least $4$ elements, contradiction.$\square$ 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 $S_i\setminus\{q\}$ are all distinct for $1\leq i\leq m$. Then $2m=|S_1 \setminus \{p \} \cup ... \cup S_m \setminus \{p \}| \le n-1$, so $m\leq\frac{n-1}{2}$, and since $m$ is an integer $m\leq\lfloor\frac{n-1}{2}\rfloor$. Case 2: $q$ is in exactly $3$ sets. WLOG $q\in S_1,S_2,S_3$. Then any other set $S$ must coincide with $S_1,S_2,S_3$, but not with $q$. Therefore $S$ should have one element from each $S_i\setminus\{q\}$. So $S$ is cointained in $T=\{(S_1\cup S_2\cup S_3)\setminus\{q\}\}$, which contains $6$ elements. Hence, as we showed for $n=6$, at most $4$ sets can be included in $T$. So $m\leq 3+4=7$. Case 3: $q$ is in exactly two sets. Let $\{q,a,b\},\{q,c,d\}$ be sets in $\{S_i\}$. 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\leq 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\leq 1$. In total, we got that $m\leq\max\{7,\lfloor\frac{n-1}{2}\rfloor\}$, 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:
