Each of $2k+1$ distinct 7-element subsets of the 20 element set intersects with exactly $k$ of them. Find the maximum possible value of $k$.
Problem
Source: IZHO 2020 P2
Tags: combinatorics
10.01.2020 21:37
The number of intersection pairs is $\frac{k(2k+1)}{2}$ so $k$ must be even. Any other ideas? (EDIT: Ok, thanks for adding that actually each set has $7$ elements, this is now a lot easier problem.)
12.01.2020 00:01
You forgot to say that these subsets are distinct and possess exactly $7$ elements each
12.01.2020 19:25
Indeed, the subsets are supposed to be of size $7$. We claim that $k$ must be two. It's easy to construct an example achieving $k = 2$, and so this would imply that the answer is $\boxed{2}.$ Construct a graph $G$ on $2k+1$ vertices where the vertices correspond to the $7-$subsets and we connect two vertices iff the corresponding subsets are disjoint. It's easy to see that $G$ is triangle-free. This leads to our preliminary lemma. Lemma 1. For any two vertices $a, b$ of $G$ which are connected, there is precisely one other vertex $c$ so that $ac, bc$ are both not edges. For each other vertex $d \neq c$, precisely one of $ad, bd$ is an edge. Proof. This is immediate upon using the previous results (triangle-free and regular of degree $k$). $\blacksquare$ Fix two arbitrary connected vertices $a, b \in G$. Let $A, B$ denote the set of neighbors of $a, b$ which don't include $b, a$ respectively. Let $c$ be the unique vertex of $G$ which is not in $\{a, b\} \cup A \cup B.$ Observe that the vertex-induced subgraph of $G$ on $\{a, b\} \cup A \cup B$ is bipartite with vertex sets $\{a\} \cup B$ and $\{b\} \cup A$. Furthermore, because $c$ has degree $k$, it must be connected to exactly $\frac{k}{2}$ vertices in $\{a\} \cup B$ and $\{b\} \cup A.$ The following is now clear. We can label the vertices of the graph $a_1, a_2, \cdots, a_k, b_1, b_2, \cdots, b_k, c$ so that the following hold. For each $(i, j) \in [k]^2$, $a_i$ and $b_j$ are connected unless $i = j \le \frac{k}{2}.$ Furthermore, $c$ is connected only to $a_1, a_2, \cdots, a_{\frac{k}{2}}, b_1, b_2, \cdots, b_{\frac{k}{2}}.$ We will now show that $k$ must be $2.$ Indeed, if $k > 2$, then $c, a_1,$ and $b_2$ form a triangle. This means that $k \le 2$, and since $k$ is even as others have observed, we must have $k = 2.$ In conclusion, the maximum possible value of $k$ is $\boxed{2}.$ $\square$
23.01.2025 22:43
Assassino9931 wrote: The number of intersection pairs is $\frac{k(2k+1)}{2}$ so $k$ must be even. This could come in handy, as disproving $k\geq 3$ is actually strengthened to $k\geq 4$, but I have not seen a solution in which this step gives serious advantage. An example with $k=2$ is $\{1, 2, 3, 4, 5, 6, 7\}$, $\{5, 6, 7, 8, 9, 10, 11\}$, $\{9, 10, 11, 12, 13, 14, 15\}$, $\{13, 14, 15, 16, 17, 18, 19\}$ and $\{17, 18, 19, 20, 1, 2, 3\}$. Indeed, each set in this collection intersects only with its two neighbours. For the bound, we rely on the extremely simple but crucial observation that among any three $7$-element subsets of $\{1,2,\ldots,20\}$ there are two which intersect each other, due to $3 \cdot 7 > 20$ and the Pigeonhole principle. Let $A$ be any of the $2k+1$ subsets. It intersects $k$ other subsets $B_1, \dots, B_k$. The remaining subsets $C_1, \dots, C_k$ do not intersect $A$ and are therefore pairwise intersecting. Since each $C_i$ intersects $k$ other subsets, it intersects exactly one $B_j$. This $B_j$ cannot be the same for all $C_i$ because $B_j$ cannot intersect $k+1$ subsets. Thus there are two different $C_i$ intersecting different $B_j$; let $C_1$ intersect $B_1$ and $C_2$ intersect $B_2$. All the subsets that do not intersect $C_1$ must intersect each other; there is $A$ among them, therefore they are $A$ and all $B_i$, $i \neq 1$. Hence every $B_j$ and $B_j$, $i \neq j, j \neq 1$, intersect. Applying the same argument to $C_2$, we see that any $B_i$ and $B_j$, $i \neq 2, j \neq 2$, intersect. We see that the family $A, B_1, \dots, B_k$ contains only one pair, $B_1$ and $B_2$, of non-intersecting subsets, while $B_1$ intersects $C_1$ and $B_2$ intersects $C_2$. For each $i$ this list contains $k$ subsets intersecting $B_i$. It follows that no $C_i$ with $i > 2$ intersects any $B_j$, that is, there are no such $C_i$, and $k \leq 2$.