Задача 3.
Стоит шеренга из 10 эльфов, а перед ней — шеренга из 10 гномов. Перед каждым эльфом стоит гном ростом ниже. Докажите, что если шеренгу эльфов построить по росту (слева направо), и шеренгу гномов построить по росту (слева направо), то снова перед каждым эльфом будет гном ростом ниже.
Ответ на Задачу 3.
Решение:
Пусть это не так. Перестроим эльфов и гномов по возрастанию роста слева направо. Тогда есть хотя бы один эльф, перед которым стоит гном выше ростом. Рассмотрим самого правого из таких эльфов (самого высокого), пусть это будет эльф A, а перед ним стоит гном B. Все гномы, которые стоят справа от B, не ниже гнома B, а значит, выше эльфа A. Значит в исходной шеренге гном B и гномы справа от него могли стоять только перед эльфами, которые выше эльфа A. Но поскольку A и B стоят на одинаковых позициях, то таких эльфов на 1 меньше. Получено противоречие.
