Let $1\le k\le n$ be integers. At most how many $k$-element subsets can we select from $\{1,2,\dots,n\}$ such that for any two selected subsets, one of the subsets consists of the $k$ smallest elements of their union?
Problem
Source: Kürschák 2016, problem 1
Tags: combinatorics, Subsets
07.10.2016 20:56
07.10.2016 21:51
First note that the set $\{ \{ 1,2,...,k-1,i\} \mid i=k,k+1,\dotsc ,n\}$ consists of $n-k+1$ $k$-element subsets that satisfy the condition. We will show that there not exist more than $n-k+1$ such subsets; suppose to the contrary that we can select $t>n-k+1$ ones. Let these $t$ subsets be $S_i=\{ a_{i,1},a_{i,2},\dotsc ,a_{i,k}\}$ where $i=1,2,\dotsc ,t$ such that $a_{i,1}<a_{i,2}<\cdots <a_{i,k}$ and $\sum_{j=1}^{k}{a_{p,j}} \leqslant \sum_{j=1}^{k}{a_{q,j}}$ when $p<q\in \{ 1,2,\dotsc ,t\}$ We can easily see that the equality not occurs. This mean that $S_p$ contains $k$ smallest element of $S_p\cup S_q$ for all $p<q\in \{ 1,2,\dotsc ,t\}$. Note that for any $p<q\in \{ 1,2,\dotsc ,t\}$, $a_{p,k}\neq a_{q,k}$ (otherwise $\{ a_{p,1},a_{p,2},\dotsc ,a_{p,k}\}=\{ a_{q,1},a_{q,2},\dotsc ,a_{q,k}\}$). Also we have $a_{p,k}\geqslant a_{q,k}$ (otherwise $a_{p,k}$ is not in the $k$ smallest elements of $S_p\cup S_q$). So, $a_{1,k}<a_{2,k}<\cdots <a_{t,k}\implies a_{t,k}\geqslant t-1+a_{1,k}$. Combining with $a_{1,1}<a_{1,2}<\cdots <a_{1,k}$, we get $a_{1,k}\geqslant a_{1,1}+k-1\geqslant 1+k-1=k$ So, $a_{t,k}\geqslant t-1+k>(n-k+1)-1+k=n.\quad \perp$