4

Some children are arranged in two rows, so that each child in the front row is taller than the child behind him in the back row. The children are now rearranged in increasing order in each row. Show that in the new arrangement each child in the front row is taller than the child behind him.

Reformulation: consider two $n$-uples of (positive) numbers $(a_1, \ldots, a_n)$ and $(b_1, \ldots, b_n)$ such that $a_i \ge b_i$ for all $1\le i \le n$. If $(a'_1, \ldots, a'_n)$ and $(b'_1, \ldots, b'_n)$ are the increasing rearrangements of $(a_1, \ldots, a_n)$ respectively $(b_1, \ldots, b_n)$ then $a'_i \ge b'_i$ for all $1\le i\le n$.

I was told that the statement is obvious. Is it? It is fairly easy to see that $a'_1 \ge b'_1$, and also that $a'_n \ge b'_n$, but it does not seem obvious for other values of $i$.

orangeskid
  • 53,909

3 Answers3

2

Take the smallest child of the front row and the smallest child of the back row (which clearly is the smallest of all childs) both "out of competition". Is it possible to rearrange the rest of the children in such a way that each child stays in the same row and again each child in the (new) front row is taller than the child behind him in the (new) back row? If so then you are done with induction. If the two children mentioned were allready originally in the same column then the answer is clearly "yes": all children (except the two that were taken out) take their original positions. If not then the situation is even more favourable. The child in the front and originally in the same column as the smallest child in the back will be taller than the smallest child in the front hence will be taller than the child behind the smallest child in the front. So these two children are placed in a column. The other children just take their original places.

drhab
  • 151,093
1

Look at it inductively. The shortest kid in the front ($a'_1$) is clearly taller than the shortest kid in back ($b'_1$) . Why? Well, $a'_1$ was taller than some kid in back and that kid had to be at least as tall as $b'_1$.

Now, suppose (inductively) that we are done for the first $i-1$ kids. Look at the original configuration. If $a'_1, ...a'_{i-1}$ originally were in front of the list $b'_1, ...b'_{i-1}$ (in any order) then clearly the kid $a'_i$ was originally in front of someone no shorter than $b'_i$. Alternatively, suppose that at least one of $a'_1, ...a'_{i-1}$ was in front of some b other than one of $b'_1, ...b'_{i-1}$. But that would mean that there were more than $i-1$ kids in the back row shorter than $a'_{i-1}$ which means that $b'_i < a'_{i-1} < a'_i$ as desired.

lulu
  • 70,402
1

If ${\max\,}_l\> a_l=a_j$ and ${\max\,}_l\> b_l=b_j$ for the same $j$ then just make the pair $\left[\matrix{ a_j\cr b_j\cr}\right]$ the last pair of the line. If ${\max\,}_l\> a_l=a_j$ and ${\max\,}_l\> b_l=b_k$ with $j\ne k$ then we have the chain of inequalities $$a_j\geq a_k\geq b_k\geq b_j\ .$$ We then make $\left[\matrix{ a_j\cr b_k\cr}\right]$ the last pair and $\left[\matrix{ a_k\cr b_j\cr}\right]$ the (temporary) first pair of the line. In both cases the first $n-1$ resulting pairs form an admissible instance of the problem with $n$ replaced by $n-1$.

Christian Blatter
  • 226,825