Problem

Source: ELMO 2015, Problem 5 (Shortlist C3)

Tags: Elmo, combinatorics



Let $m, n, k > 1$ be positive integers. For a set $S$ of positive integers, define $S(i,j)$ for $i<j$ to be the number of elements in $S$ strictly between $i$ and $j$. We say two sets $(X,Y)$ are a fat pair if \[ X(i,j)\equiv Y(i,j) \pmod{n} \] for every $i,j \in X \cap Y$. (In particular, if $\left\lvert X \cap Y \right\rvert < 2$ then $(X,Y)$ is fat.) If there are $m$ distinct sets of $k$ positive integers such that no two form a fat pair, show that $m<n^{k-1}$. Proposed by Allen Liu