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
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.
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.
27.06.2015 17:19
27.06.2015 17:27
I don't get the official solution. How is there only one good set possible?
28.06.2015 11:27
I think we can use induction with $k \geq 2$
28.06.2015 15:30
This was hell.....it was starring at me like this.......
31.08.2015 14:58
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.
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.
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
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$.)
17.04.2019 01:49
I think the following non-probabilistic solution works.
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.