Let $n \geq 2$ be an integer and let \[M=\bigg\{\frac{a_1 + a_2 + ... + a_k}{k}: 1 \le k \le n\text{ and }1 \le a_1 < \ldots < a_k \le n\bigg\}\]be the set of the arithmetic means of the elements of all non-empty subsets of $\{1, 2, ..., n\}$. Find \[\min\{|a - b| : a, b \in M\text{ with } a \neq b\}.\]
Problem
Source: BMO Shortlist 2021
Tags: Balkan, shortlist, 2021, number theory, arithmetic mean
08.05.2022 20:30
This was also P2 from the first Romanian TST from 2022, proposed by Cristi Săvescu. The answer is $(n-1)^{-1}\cdot(n-2)^{-1}.$
09.05.2022 20:11
We claim the answer is: $$ \boxed{\begin{cases} \frac{1}{2} & n=2 \\ \frac{1}{(n-1)(n-2)} & n \geq 3 \end{cases}} $$For $n=2,3$, this follows by direct check so we only consider $n \geq 4$. Firstly we show this is attained. For this let $S=\{1,\ldots,n\} \setminus \{a\}$ and $T=\{1,\ldots,n\} \setminus \{a,b\}$ then: $$ \overline{S}-\overline{T}=\frac{\frac{n(n+1)}{2}-a}{n-1}-\frac{\frac{n(n+1)}{2}-a-b}{n-2}=\frac{2(a-b)+2bn-n-n^2}{2(n-1)(n-2)} $$Setting: $$ \begin{cases} a=\frac{n-1}{2} \quad b=\frac{n+1}{2} & n \text{ odd} \\ a=n-1 \quad b=\frac{n}{2} & n \text{ even} \end{cases} $$we see that in either case $\left\lvert \overline{S}-\overline{T} \right\rvert=\frac{1}{(n-1)(n-2)}$ so in either case the bound is attained. To see we can't do any better, assume we can then we have $S,T \subset \{1,\ldots,n\}$ such that: $$ \frac{1}{(n-1)(n-2)}>\left\lvert \overline{S}-\overline{T} \right\rvert=\frac{\text{Non-zero integer}}{|S||T|} \geq \frac{1}{|S||T|} \Rightarrow |S||T|>(n-1)(n-2) $$This forces at least one of $|S|$ or $|T|$ to be $n$ so WLOG $S=\{1,\ldots,n\}$ but then observe: $$ \frac{1}{(n-1)(n-2)}>\left\lvert \overline{S}-\overline{T} \right\rvert=\left\lvert \frac{n+1}{2}-\overline{T} \right\rvert=\frac{\text{Non-zero integer}}{2|T|} \geq \frac{1}{2|T|} \geq \frac{1}{2(n-1)} $$$$ \Longrightarrow 2>n-2 \Rightarrow n \leq 3 $$But we're assuming $n \geq 4$ so this is a contradiction.
09.05.2022 22:06
@above you could have $|S| = |T| = n-1$ and still obey $|S||T| > (n-1)(n-2)$? (Anyway this case is easy to rule out.) Another way to eliminate $\{1,2,\ldots,n\}$ from the very beginning is to notice that its mean is the same as that of $\{1,n\}$ so we can restrict to $|S|, |T| \leq n-1$ even before guessing the answer.
10.05.2022 09:42
This easy one is my proposal
04.09.2022 00:57
Let $a=\frac{x}{p},b=\frac{y}{q}$ where $\gcd(x,p),\gcd(y,q)=1$. Then we have: \[|a-b|=|\frac{x}{p}-\frac{y}{q}|=\frac{|xq-yp|}{pq} \]since $|xq-yp| >0$, we have $|a-b| \ge \frac{1}{qp}$. We have to maximize $qp$. we know that $q,p \le n-1$ since if $q,p=n$, Arithmetic mean of $n$ consecutive numbers is $\frac{n-1}{2}$ meaning achieving $n$ is impossible. Obviously, $p \neq q$. Then we can conclude $p=n-1,q=n-2$ hence $$|a-b| \ge \frac{1}{(n-1)(n-2)}$$ One may show construction for $\frac{1}{(n-1)(n-2)}$ by choosing elements $x,y \in \{1,2,3,4,...,n \}$ with dividing to even/odd cases of $n \ \blacksquare$.