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
Problem
Source: ELMO 2015, Problem 5 (Shortlist C3)
Tags: Elmo, combinatorics
AdithyaBhaskar
27.06.2015 12:43
This was the toughest problem on this year's ELMO. I remember how disgusted I felt on not even being able to budge this problem!! I'm still waiting for a solution.
shinichiman
27.06.2015 12:46
I prove that there are no $m$ distinct sets of $k$ positive integers such that no two form a fat pair and $m \ge n^{k-1}$. I'm not sure about my solution. I'll post mine once I get the result.
v_Enhance
27.06.2015 17:19
Random color all the integers with one of $n$ colors $1, 2, \dots, n \pmod n$. Call a set GOOD if the color of its elements (when sorted) is of the form $a, a+1, \dots$. Two good sets form a fat pair.
somepersonoverhere
27.06.2015 17:27
I don't get the official solution. How is there only one good set possible?
BuiBaAnh
28.06.2015 11:27
I think we can use induction with $k \geq 2$
Viswanath
28.06.2015 15:30
This was hell.....it was starring at me like this.......
dgrozev
31.08.2015 14:58
Let the union of the sets be T = $\{a_1, a_2,\dots, a_{\ell}\}$, where the elements of
T are arranged in increasing order. For each element of T, color it randomly with
one of $n$ colors $(1, 2,\dots, n)$. We say a set is good if its elements when arranged in
increasing order have colors $a, a + 1, \dots, a + k-1$ taken $\mod n$ where $a$ can be any
color. Now the fact that there is no fat pair means that only one good set can exist
in each coloring. The probability that a good set exists is $\frac{1}{n^{k-1}}$ so we are done.
Very nice, thou, I think, not very well ended. For any fixed subset $S$ of $T$ with $k$ elements, the probability that $S$ is good colored is indeed $\frac{1}{n^{k-1}}$. Let amongst all colorings $\Omega$ of $T$, $\Omega(S)$ be the family of good ones with respect to $S$. Thus, $|\Omega(S)|= \frac{1}{n^{k-1}}\cdot |\Omega|$ . Suppose we take more than $n^{k-1}$ subsets $S_1,S_2,\dots,S_m$ of $T$ (with $k$ elements each). Then for some two of them $S_i,S_j$, $\Omega(S_i)$ and $\Omega(S_j)$ will meet, meaning there exists a coloring of $T$, which is good simultaneously for $S_i$ and $S_j$. Therefore $S_i,S_j$ are a fat pair. All the difficulty of this problem is a matter of interpretation, I mean there exists a pretty simple non probabilistic solution, if the problem is properly interpreted.
anantmudgal09
19.04.2016 15:31
Ok, not much new, but still feel like posting. We randomly and independently assign to each natural number a residue class modulo $n$. Now, we call a set nice if the residue classes in it when written in ascending order are $a,a+1,...,a+n-1$ Clearly, two nice sets form a fat pair. Now the probability of a set being nice is $\frac{1}{n^{k-1}}$ and we have $m$ sets. Thus, the expected number of sets that form a fat pair is $\frac{m}{n^{k-1}}<1$ for otherwise we have a colouring which gives the contradiction.
Stranger8
25.05.2016 16:56
Maybe a silly question but I really do not understand why two nice or good sets form a fat pair...could any one help me please
McTeague
07.07.2016 17:07
@Stranger8 $\text{ }$ For good sets $X$ and $Y$, consider their elements in increasing order. If $|X \cap Y| < 2$, then the sets automatically form a fat pair, as given. If $|X \cap Y| \ge 2$, then consider distinct $u,v \in X \cap Y$ with $u < v$. Let the set of elements strictly between $u$ and $v$ in $X$ be $x_1 < \cdots < x_r$ and between $u$ and $v$ in $Y$ be $y_1 < \cdots < y_s$ (so $X(u,v) = r$ and $Y(u,v) = s$). Denote the color of an element $t$ by $c(t)$. Let $c(u) = a$ and $c(v) = b$. Since $X$ and $Y$ are good: \[c(x_1) \equiv a+1 \pmod n, \ldots, c(x_r) \equiv a+r \pmod n, c(v) = b \equiv a+r+1 \pmod n\]Likewise: \[c(y_1) \equiv a+1 \pmod n, \ldots, c(y_s) \equiv a+s \pmod n, c(v) = b \equiv a+s+1 \pmod n\]So $a+r+1 \equiv c(v) \equiv a+s+1 \pmod n \Rightarrow r \equiv s \pmod n$, the original condition. (If there do not exist any elements in $X$ between $u$ and $v$, then take $r = 0$ and similarly in the case for $Y$.)
Pathological
17.04.2019 01:49
I think the following non-probabilistic solution works.
Equivalently, we will show that among any $n^{k-1}$ sets all of size $k$ there must exist a $fat$ pair. Let $S_1, S_2, \cdots, S_{n^{k-1}}$ be some sets of size $k$. Let $T = S_1 \cup S_2 \cup \cdots \cup S_{n^{k-1}}$ and $t = |T|.$ Consider the set $F$ of functions $f: T \rightarrow \{1, 2, \cdots, n\}.$ We'll construct a function from the set $X = \{S_1, S_2, \cdots, S_{n^{k-1}}\}$ to $F$ so that each element in $X$ is mapped to exactly $n^{t-k+1}$ things and not all things in $T$ are mapped to. We'll do this as follows. Let $S \in X$ be one of the subsets. Firstly, sort it in increasing order, so that $S = \{a_1 < a_2 < \cdots < a_k\}$. Then, we will map $S$ to all functions $f \in F$ where $f(a_i) -i$ is constant modulo $n$ over the $a_i$'s. There are $n \cdot n^{t - k} = n^{t-k+1}$ that $S$ is mapped to. Furthermore, it's clear that the function $f \in F$ which is identically $1$ is never mapped to, and so therefore there are two sets $S_i, S_j$ which map to a common $f \in F.$ This is easily seen to imply the desired conclusion.
$\square$
WolfusA
11.06.2019 17:34
You map one object into many objects. How is that possible? It ain't a function. Pathological wrote: We'll construct a function from the set $X = \{S_1, S_2, \cdots, S_{n^{k-1}}\}$ to $F$ so that each element in $X$ is mapped to exactly $n^{t-k+1}$ things and not all things in $T$ are mapped to.