IMO 2019 Shortlisted Problems

We first construct a set $\mathcal{F}$ with $2^k$ members, each member having at most $k$ different scales in $\mathcal{F}$. Take $\mathcal{F}=\{0,1,2,\dots ,2^k-1\}$. The scale between any two members of $\mathcal{F}$ is in the set $\{0,1,\dots ,k-1\}$.

We now show that $2^k$ is an upper bound on the size of $\mathcal{F}$. For every finite set $\mathcal{S}$ of real numbers, and every real $x$, let $r_{\mathcal{S}}(x)$ denote the number of different scales of $x$ in $\mathcal{S}$. That is, $r_{\mathcal{S}}(x)=|\{D(x,y):x\ne y\in \mathcal{S}\}|$. Thus, for every element $x$ of the set $\mathcal{F}$ in the problem statement, we have $r_{\mathcal{F}}(x)⩽k$. The condition $|\mathcal{F}|⩽2^k$ is an immediate consequence of the following lemma.

Lemma. Let $\mathcal{S}$ be a finite set of real numbers, and define $$w(\mathcal{S})=\sum _{x\in \mathcal{S}}{2}^{-r_{\mathcal{S}}(x)}$$ Then $w(\mathcal{S})⩽1$.

Proof. Induction on $n=|\mathcal{S}|$. If $\mathcal{S}=\{x\}$, then $r_{\mathcal{S}}(x)=0$, so $w(\mathcal{S})=1$.

Assume now $n⩾2$, and let $x_1<\cdots <x_n$ list the members of $\mathcal{S}$. Let $d$ be the minimal scale between two distinct elements of $\mathcal{S}$; then there exist neighbours $x_t$ and $x_{t+1}$ with $D(x_t,x_{t+1})=d$. Notice that for any two indices $i$ and $j$ with $j-i>1$ we have $D(x_i,x_j)>d$, since $$|x_i-x_j|=|x_{i+1}-x_i|+|x_j-x_{i+1}|⩾2^d+2^d=2^{d+1}$$ Now choose the minimal $i⩽t$ and the maximal $j⩾t+1$ such that $D(x_i,x_{i+1})=D(x_{i+1},x_{i+2})=\cdots =D(x_{j-1},x_j)=d$.

Let $E$ be the set of all the $x_s$ with even indices $i⩽s⩽j$, $O$ be the set of those with odd indices $i⩽s⩽j$, and $R$ be the rest of the elements (so that $\mathcal{S}$ is the disjoint union of $E$, $O$ and $R$). Set ${\mathcal{S}}_O=R\cup O$ and ${\mathcal{S}}_E=R\cup E$; we have $|{\mathcal{S}}_O|<|\mathcal{S}|$ and $|{\mathcal{S}}_E|<|\mathcal{S}|$, so $w({\mathcal{S}}_O),w({\mathcal{S}}_E)⩽1$ by the inductive hypothesis.

Clearly, $r_{{\mathcal{S}}_O}(x)⩽r_{\mathcal{S}}(x)$ and $r_{{\mathcal{S}}_E}(x)⩽r_{\mathcal{S}}(x)$ for any $x\in R$, and thus $$\begin{array}{rl}\sum _{x\in R}{2}^{-r_{\mathcal{S}}(x)}& =\frac{1}{2}\sum _{x\in R}\left(2^{-r_{\mathcal{S}}(x)}+2^{-r_{\mathcal{S}}(x)}\right)\\ & ⩽\frac{1}{2}\sum _{x\in R}\left(2^{-r_{{\mathcal{S}}_O}(x)}+2^{-r_{{\mathcal{S}}_E}(x)}\right)\end{array}$$ On the other hand, for every $x\in O$, there is no $y\in {\mathcal{S}}_O$ such that $D_{{\mathcal{S}}_O}(x,y)=d$ (as all candidates from $\mathcal{S}$ were in $E$). Hence, we have $r_{{\mathcal{S}}_O}(x)⩽r_{\mathcal{S}}(x)-1$, and thus $$\sum _{x\in O}{2}^{-r_{\mathcal{S}}(x)}⩽\frac{1}{2}\sum _{x\in O}{2}^{-r_{S_O}(x)}$$ Similarly, for every $x\in E$, we have $$\sum _{x\in E}{2}^{-r_{\mathcal{S}}(x)}⩽\frac{1}{2}\sum _{x\in E}{2}^{-r_{{\mathcal{S}}_E}(x)}$$ We can then combine these to give $$\begin{array}{rl}w(S)& =\sum _{x\in R}{2}^{-r_{\mathcal{S}}(x)}+\sum _{x\in O}{2}^{-r_{\mathcal{S}}(x)}+\sum _{x\in E}{2}^{-r_{\mathcal{S}}(x)}\\ & ⩽\frac{1}{2}\sum _{x\in R}\left(2^{-r_{{\mathcal{S}}_O}(x)}+2^{-r_{{\mathcal{S}}_E}(x)}\right)+\frac{1}{2}\sum _{x\in O}{2}^{-r_{{\mathcal{S}}_O}(x)}+\frac{1}{2}\sum _{x\in E}{2}^{-r_{{\mathcal{S}}_E}(x)}\\ & =\frac{1}{2}\left(\sum _{x\in {\mathcal{S}}_O}{2}^{-r_{{\mathcal{S}}_O}(x)}+\sum _{x\in {\mathcal{S}}_E}{2}^{-r_{{\mathcal{S}}_E}(x)}\right)(\text{since }{\mathcal{S}}_O=O\cup R\text{ and }{\mathcal{S}}_E=E\cup R)\\ & =\frac{1}{2}\left(w({\mathcal{S}}_O)+w({\mathcal{S}}_E)\right)\text{(by definition of }w(\cdot ))\\ & ⩽1(\text{by the inductive hypothesis})\end{array}$$ which completes the induction.