BMO 2010 Shortlist

We will prove that a single measurement is sufficient to do the job. Let $a_1<a_2<\cdots <a_n$ and $b_1>b_2>\cdots >b_n$, $n\ge 2$ be arbitrary real numbers. For each permutation $\pi$ of the set $\{1,2,\dots ,n\}$ define $$Z(\pi )=a_1{b}_{\pi (1)}+a_2{b}_{\pi (2)}+\cdots +a_n{b}_{\pi (n)}.$$ The rearrangement inequality says that $Z(\pi )$ is the least possible if and only if $\pi$ is the identical permutation. The next lemma tells us where one should look for those permutations $\pi$ for which the value of $Z(\pi )$ is the second least.

Lemma. Denote by ${\pi }_i,1\le i\le n-1$, the permutation of the set $\{1,2,\dots ,n\}$ given by $${\pi }_i:\left(\begin{array}{ccccccccc}1& 2& \dots & i-1& i& i+1& i+2& \dots & n\\ 1& 2& \dots & i-1& i+1& i& i+2& \dots & n\end{array}\right).$$ For each permutation $\mu \notin \{\text{id},{\pi }_1,{\pi }_2,\dots ,{\pi }_{n-1}\}$ we have that $$Z(\mu )>\min \{Z({\pi }_1),Z({\pi }_2),\dots ,Z({\pi }_{n-1})\}.(1)$$ Proof. Let $\pi$ be a permutation such that the value $Z(\pi )$ is the least among all nonidentical permutations. Then there must be a positive integer that is not mapped to itself by $\pi$. Let $i$ be the least such integer. Clearly, we have $\pi (i)>i$. Hence there is a $j>i$ such that $\pi (j)=i$. Consider the permutation $\tau$ that coincides with $\pi$ everywhere except on the numbers $i$ and $j$ where $\tau (i)=i$ and $\tau (j)=\pi (i)$. Then $$\begin{array}{rl}Z(\pi )-Z(\tau )& =a_i{b}_{\pi (i)}+a_j{b}_{\pi (j)}-a_i{b}_{\tau (i)}-a_j{b}_{\tau (j)}=a_i{b}_{\pi (i)}+a_j{b}_i-a_i{b}_j-a_j{b}_{\pi (i)}=\\ & =(a_i-a_j)(b_{\pi (i)}-b_i)>0\end{array}$$ (because from $i<j$ and $\pi (i)>i$ it follows that $a_i-a_j<0$ and $b_{\pi (i)}-b_i<0$). Whereas $\pi$ is a permutation for which $Z$ takes its minimal value for all nonidentical permutations, it follows that $\tau =\text{id}$. This shows that $\pi$ has the form $$\pi :\left(\begin{array}{cccccccccccc}1& 2& \dots & i-1& i& i+1& \dots & j-1& j& j+1& \dots & n\\ 1& 2& \dots & i-1& j& i+1& \dots & j-1& i& j+1& \dots & n\end{array}\right).$$ Let us show that $j=i+1$. Suppose to the contrary, namely suppose that $j>i+1$. Consider the permutation $\sigma$ that coincides with $\pi$ everywhere except on the numbers $i$ and $i+1$ where $\sigma (i)=i+1$ and $\sigma (i+1)=j$. Then $\sigma$ is another nonidentical permutation and $$Z(\pi )-Z(\sigma )=a_i{b}_j+a_{i+1}{b}_{i+1}-a_i{b}_{i+1}-a_{i+1}{b}_j=(a_i-a_{i+1})(b_j-b_{i+1})>0.$$ Thus we have that $Z(\pi )>Z(\sigma )$. This contradicts the selection of $\pi$, which gives the minimal value of $Z$ among all nonidentical permutations. Thus the permutation $\pi$ is one of the following: ${\pi }_1,{\pi }_2,\dots ,{\pi }_{n-1}$, which implies (1). The Lemma is proved. $\square$

We shall prove that for arbitrary weights $m_1<m_2<\cdots <m_{n+1}$, $n\ge 2$, one measurement is sufficient to do the job. Let us note that this will follow immediately if we show that there are $k_1,k_2,\dots ,k_n,k_{n+1}$ $$k_1{m}_1+k_2{m}_2+\cdots +k_n{m}_n<k_{n+1}{m}_{n+1},(1)$$ $$\text{and such that}{k}_1{m}_{\pi (1)}+k_2{m}_{\pi (2)}+\cdots +k_n{m}_{\pi (n)}>k_{n+1}{m}_{\pi (n+1)}(2)$$ for any nonidentical permutation $\pi$ of the set $(1,2,\dots ,n+1)$.

Suppose there are such integers. In this case the controller takes $k_1$ coins from the wagon labelled $m_1$, $k_2$ coins from the wagon labelled $m_2$, ..., $k_n$ coins from the wagon labelled $m_n$ and puts all of them on the left plate of scales. He takes $k_{n+1}$ coins from the wagon labelled $m_{n+1}$ and puts them on the right plate. Then this measurement does the job. Indeed, if all wagons were labelled properly, the left hand side will weigh less than the right hand side, whereas otherwise it will be the right hand side that will weigh less. It is clear that we are forced to choose and fix the integers $k_1,k_2,...,k_n,k_{n+1}$ so that "the second least weight" on the left hand side exceeds the maximal weight of the right hand side, i.e. $k_{n+1}{m}_{n+1}$. It is clear that "the second least weight" of the left hand side does not contain weights $m_{n+1}$. To accomplish this let us choose $k_1,k_2,...,k_n$ such that $k_1>k_2>...>k_n$. If they are ordered in such a way, then by Lemma "the second least weight" of the left hand side is of the form $$k_1{m}_1+k_2{m}_2+\cdots +k_{i-1}{m}_{i-1}+k_i{m}_{i+1}+k_{i+1}{m}_i+k_{i+2}{m}_{i+2}+\cdots +k_n{m}_n,$$ for some $1\le i\le n-1$. Thus, for (1) and (2) to hold it suffices that $$k_{n+1}>\frac{k_1{m}_1+k_2{m}_2+\cdots +k_n{m}_n}{m_{n+1}},$$ as well as $$k_{n+1}<\frac{k_1{m}_1+k_2{m}_2+\cdots +k_{i-1}{m}_{i-1}+k_i{m}_{i+1}+k_{i+1}{m}_i+k_{i+2}{m}_{i+2}+\cdots +k_n{m}_n}{m_{n+1}}$$ for each $1\le i\le n-1$. Also we must make sure that $k_{n+1}$ is indeed a positive integer. The existence of such an integer would be guaranteed if $$\frac{k_1{m}_1+k_2{m}_2+\cdots +k_{i-1}{m}_{i-1}+k_i{m}_{i+1}+k_{i+1}{m}_i+k_{i+2}{m}_{i+2}+\cdots +k_n{m}_n}{m_{n+1}}>1+\frac{k_1{m}_1+k_2{m}_2+\cdots +k_n{m}_n}{m_{n+1}},$$ holds for each $1\le i\le n-1$. The last condition is equivalent to $(k_i-k_{i+1})(m_{i+1}-m_i)>m_{n+1}$, for each $1\le i\le n-1$. This is easily achieved if we take $$k_n=1,k_{n-1}=k_n+\left[\frac{m_{n+1}}{m_n-m_{n-1}}\right]+1,k_{n-2}=k_{n-1}+\left[\frac{m_{n+1}}{m_{n-1}-m_{n-2}}\right]+1,\dots ,k_2=k_3+\left[\frac{m_{n+1}}{m_2-m_1}\right]+1,k_1=k_2+\left[\frac{m_{n+1}}{m_1-m_2}\right]+1.$$ Finally we can set $$ k_{n+1} = 1 + \left[ \frac{k_1 m_1 + k_2 m_2 + \dots + k_n m_n}{m_{n+1}} \right]. \quad \square