Kvant Math Problem 867

Let the boys' heights be $b_1,\dots,b_{17}$ and the girls' heights be $g_1,\dots,g_{17}$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m22s
Source on kvant.digital

Problem

In a dance class, 17 boys and 17 girls formed two parallel rows, creating 17 pairs. In each pair, the boy’s height differs from the girl’s height by no more than ten centimeters. Prove that if the boys and girls in each row are rearranged by height, then in each pair the boy and the girl will still differ in height by no more than ten centimeters.

A. G. Pechkovsky

City Tournament (Spring, 1984)

Exploration

Let the boys' heights be $b_1,\dots,b_{17}$ and the girls' heights be $g_1,\dots,g_{17}$. The original pairing satisfies

$$|b_{\sigma(i)}-g_i|\le 10$$

for some matching $\sigma$.

After rearranging each row by height, we must show that if

$$b_{(1)}\le b_{(2)}\le\cdots\le b_{(17)},\qquad g_{(1)}\le g_{(2)}\le\cdots\le g_{(17)},$$

then

$$|b_{(i)}-g_{(i)}|\le 10$$

for every $i$.

A natural idea is to look at the intervals

$$I_i=[g_i-10,g_i+10].$$

Each boy is matched to a girl whose interval contains his height. The statement resembles a property of matchings in ordered sets.

Trying a small example with three pairs helps. Suppose the sorted girls are $150,160,170$. Then their intervals are

$$[140,160],\ [150,170],\ [160,180].$$

Any three boys admitting a perfect matching with these intervals seem also to satisfy that the $k$th smallest boy belongs to the $k$th interval. The reason appears to be a counting argument.

To prove $b_{(k)}\le g_{(k)}+10$, consider all girls of height at most $g_{(k)}$. There are $k$ of them. Any boy matched to one of these girls must have height at most $g_{(k)}+10$. Hence at least $k$ boys have height at most $g_{(k)}+10$. Therefore the $k$th smallest boy is at most $g_{(k)}+10$.

Similarly, among the girls of height at least $g_{(k)}$ there are $17-k+1$ girls. Any boy matched to one of them has height at least $g_{(k)}-10$. Hence at least $17-k+1$ boys have height at least $g_{(k)}-10$. Therefore fewer than $k$ boys are below $g_{(k)}-10$, so $b_{(k)}\ge g_{(k)}-10$.

Combining these inequalities gives the result.

The step most likely to hide an error is the conversion from information about matched boys to a statement about the $k$th order statistic. That counting argument must be written carefully.

Problem Understanding

We are given $17$ boys and $17$ girls. Initially they form $17$ boy-girl pairs, and in every pair the difference of heights does not exceed $10$ centimeters.

Then the boys are arranged in increasing order of height in one row, and independently the girls are arranged in increasing order of height in another row. The new pairs are formed by matching the first boy with the first girl, the second boy with the second girl, and so on.

We must prove that in every new pair the difference of heights is still at most $10$ centimeters.

This is a Type B problem. The main difficulty is to extract information about the ordered heights from the existence of some arbitrary matching whose height differences are bounded by $10$.

Proof Architecture

Lemma 1. For every $k$, at least $k$ boys have height at most $g_{(k)}+10$; this follows because the first $k$ girls in increasing order can only be matched with boys whose heights do not exceed $g_{(k)}+10$.

Lemma 2. For every $k$, at least $17-k+1$ boys have height at least $g_{(k)}-10$; this follows because the last $17-k+1$ girls can only be matched with boys whose heights are at least $g_{(k)}-10$.

Lemma 3. For every $k$,

$$g_{(k)}-10\le b_{(k)}\le g_{(k)}+10.$$

The upper bound comes from Lemma 1 and the definition of the $k$th smallest boy; the lower bound comes from Lemma 2.

The hardest part is Lemma 3, specifically translating the counting statements of Lemmas 1 and 2 into inequalities for the $k$th order statistic.

Solution

Let

$$b_{(1)}\le b_{(2)}\le\cdots\le b_{(17)}$$

be the boys' heights arranged in increasing order, and let

$$g_{(1)}\le g_{(2)}\le\cdots\le g_{(17)}$$

be the girls' heights arranged in increasing order.

We shall prove that for every $k=1,\dots,17$,

$$g_{(k)}-10\le b_{(k)}\le g_{(k)}+10.$$

This immediately yields

$$|b_{(k)}-g_{(k)}|\le 10,$$

which is exactly the required statement.

Fix $k$.

Consider the girls whose heights do not exceed $g_{(k)}$. There are exactly $k$ such girls, namely

$$g_{(1)},g_{(2)},\dots,g_{(k)}.$$

In the original pairing, each of these girls was paired with a boy whose height differs from hers by at most $10$ centimeters. Since each of these girls has height at most $g_{(k)}$, every corresponding boy has height at most

$$g_{(k)}+10.$$

The $k$ girls are matched with $k$ distinct boys. Hence at least $k$ boys have height at most $g_{(k)}+10$.

By definition of the ordered sequence of boys' heights, the $k$th smallest boy therefore satisfies

$$b_{(k)}\le g_{(k)}+10.$$

Now consider the girls whose heights are at least $g_{(k)}$. There are exactly $17-k+1$ such girls, namely

$$g_{(k)},g_{(k+1)},\dots,g_{(17)}.$$

Each of these girls was originally paired with a boy whose height differs from hers by at most $10$ centimeters. Since each of these girls has height at least $g_{(k)}$, every corresponding boy has height at least

$$g_{(k)}-10.$$

These $17-k+1$ girls are matched with $17-k+1$ distinct boys. Hence at least $17-k+1$ boys have height at least $g_{(k)}-10$.

Consequently at most $k-1$ boys have height less than $g_{(k)}-10$. The $k$th smallest boy cannot be less than $g_{(k)}-10$, so

$$b_{(k)}\ge g_{(k)}-10.$$

Combining the two inequalities gives

$$g_{(k)}-10\le b_{(k)}\le g_{(k)}+10.$$

Hence

$$|b_{(k)}-g_{(k)}|\le 10$$

for every $k=1,\dots,17$.

Thus after both rows are rearranged by height, each new boy-girl pair still differs in height by no more than ten centimeters.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the deduction that $b_{(k)}\le g_{(k)}+10$. From the first $k$ girls we obtain $k$ distinct matched boys, each of height at most $g_{(k)}+10$. Therefore there exist at least $k$ boys below or at that level. The definition of $b_{(k)}$ is precisely that at least $k$ boys are not greater than $b_{(k)}$. If at least $k$ boys are already not greater than $g_{(k)}+10$, then the $k$th smallest boy cannot exceed $g_{(k)}+10$.

The second delicate step is the deduction that $b_{(k)}\ge g_{(k)}-10$. From the last $17-k+1$ girls we obtain $17-k+1$ distinct boys whose heights are at least $g_{(k)}-10$. Hence at most $k-1$ boys lie below $g_{(k)}-10$. If $b_{(k)}$ were smaller than $g_{(k)}-10$, then at least $k$ boys would be below $g_{(k)}-10$, contradicting the count.

A careless argument might say that the first $k$ girls must be matched to the first $k$ boys. That is false. The proof uses only counting and does not assume any relation between the original matching and the sorted order.

Alternative Approaches

Associate to each girl of height $g$ the interval $[g-10,g+10]$. The original condition says that the boys' heights admit a perfect matching into these intervals. Hall's theorem for intervals implies that for every threshold $x$, the number of boys not exceeding $x$ is bounded above by the number of intervals whose right endpoint is at most $x$, and similarly for lower thresholds. Translating these inequalities to order statistics yields

$$g_{(k)}-10\le b_{(k)}\le g_{(k)}+10.$$

This approach is conceptually related to matching theory, but it introduces machinery that is unnecessary for a problem of this size.

The counting proof given above extracts exactly the two inequalities needed for each order statistic and avoids any appeal to general matching theorems. It is shorter and more elementary.