Question

На занятии по баскетболу 20 мальчиков и 25 девочек построили двумя параллельными колоннами Так что образовалось 20 пар. В каждой паре измерили разница роста мальчика и девочки (разницы берётся по абсолютной величине то есть из большего вычитают меньше). Максимальная разность оказалась 10 см. В другой раз перед образованием пар каждую колонну предварительно построили по росту. Докажите что максимальная разность будет не больше 10 см.

Answer 1

Рассмотрим две колонны построенные по росту. Первое место в каждой из колонн отдается самому высокому из этой колонны. Значит, самый высокий будет стоять на первом месте в колонне, а второй по росту первым в другой колонне. Аналогично, в каждой паре будет стоять i и i+1 по росту. Предположим противное - нашлась пара с разностью больше 10 см. Пусть это пара (i, i+1). Значит, изначально они не могли быть в одной паре. Рассмотрим i-ого. Поскольку все 1, 2,..., i-1 выше его, то они не могли быть в паре с i+1. Рассмотрим i+1. Поскольку i+2, i+3,...,,40 ниже него, то они не могли быть в паре с i. Значит, и i, и i+1 должны были быть в паре с теми, кто с ними в одной колонне, что противоречит условию.

Answer 2

Давайте представим каждую пару, образованную мальчиком и девочкой, в виде разности их роста. Обозначим разницу роста для каждой пары через $d_1, d_2, d_3, ..., d_{20}$, где $d_i$ - это разность роста для $i$-й пары.

В первом случае, когда пары формировались случайным образом, нам известно, что максимальная разность роста составляет 10 см. Пусть это достигается для пары с индексами $i$ и $j$, где $d_i$ и $d_j$ - наибольшие значения среди всех разностей.

Теперь рассмотрим второй случай, когда колонны были предварительно отсортированы по росту. После сортировки, давайте обозначим новые разности роста как $d'_1, d'_2, d'_3, ..., d'_{20}$, где $d'_i$ - это разность роста для $i$-й пары после сортировки.

Предположим, что максимальная разность роста во втором случае превышает 10 см. То есть, существуют пара с индексами $i'$ и $j'$, где $d'_{i'}$ и $d'_{j'}$ - наибольшие значения среди всех разностей после сортировки, и $d'_{j'} - d'_{i'} > 10$.

Однако, мы знаем, что до сортировки $d_i$ и $d_j$ были максимальными значениями разностей, и $d_j - d_i$ не превышает 10 см. После сортировки, пара с индексом $i$ может быть перемещена в место с индексом $i'$, а пара с индексом $j$ может быть перемещена в место с индексом $j'$. Таким образом, разность роста для пары с индексом $j'$ после сортировки, $d'_{j'}$, должна быть больше или равна $d_j$, а разность роста для пары с индексом $i'$ после сортировки, $d'_{i'}$, должна быть меньше или равна $d_i$.

Таким образом, $d'_{j'} - d'_{i'} \geq d_j - d_i > 10$, что противоречит предположению, что максимальная разность роста после сортировки составляет более 10 см.

Следовательно, мы доказали, что максимальная разность роста после сортировки не может превышать 10 см.