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 должны были быть в паре с теми, кто с ними в одной колонне, что противоречит условию.