Дано:
25 школьников стоят в ряд. Самый левый школьник выше самого правого. Обозначим рост школьников как a_1, a_2, ..., a_25, где a_i — рост i-го школьника. Тогда a_1 > a_25.
Найти:
Показать, что существует школьник, у которого левый сосед выше правого.
Решение:
Рассмотрим последовательность ростов школьников. Обозначим разности между ростом соседей для каждого школьника. Пусть i-й школьник имеет рост a_i. Тогда разность между ростами соседей можно записать как (a_{i-1} - a_i) для школьника i, где i от 2 до 24, и (a_i - a_{i+1}) для школьника i, где i от 1 до 23.
Так как a_1 > a_25, разность между самым левым и самым правым школьником равна a_1 - a_25. Разделим этих 25 школьников на 24 интервала между ними. Если представить разности между соседями, то каждое изменение от a_i - a_{i+1} даст в совокупности изменение от самого первого к самому последнему школьнику.
Если бы все разности между соседями были неотрицательными (a_{i-1} ≤ a_i ≤ a_{i+1}), тогда все разности от первого до последнего школьника были бы не отрицательными, что противоречит условию, так как a_1 > a_25.
Таким образом, должны существовать хотя бы два школьника i и j такие, что a_i > a_{i+1} (то есть левый сосед выше правого). Проверим это. Поскольку у нас есть 25 школьников и их рост меняется, мы обязательно найдем школьника, у которого левый сосед выше правого.
Ответ:
Существует школьник, у которого левый сосед выше правого.