ELMO 2015 Problem 5

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