Олимпиада имени Леонарда Эйлера2010-2011 учебный год, I тур дистанционного этапа

В ряд выложена 101 карточка. На каждой из 50 карточек, лежащих в этом ряду на чётных местах, нарисован значок «>» или «<». Докажите, что, как бы ни были нарисованы эти значки, можно заполнить остальные карточки числами 1, 2, $\dots$ 51 (использовав каждое по разу) так, чтобы все получившиеся неравенства оказались верными.

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Решение 1. Сначала напишем над всеми карточками, лежащими на нечётных местах, по числу. Над первой карточкой напишем число 0. Затем будем двигаться вправо и каждый раз после знака «>» писать число, на 1 меньшее предыдущего, а после знака «<» — число, на 1 большее предыдущего. Очевидно, при этом каждый из знаков неравенства будет направлен от карточки, отмеченной большим числом, к карточке, отмеченной меньшим. Теперь возьмём карточки, отмеченные самым маленьким числом. Пусть их оказалось $k_1$ штук. Напишем на них произвольным образом числа 1,$\dots$, $k_1$. На карточках, отмеченных следующим по величине числом — пусть их $k_2$ штук — напишем числа от $k_1+1$ до $k_1+ k_2$ и т.д., пока все числа от 1 до 51 не будут написаны. Из построения следует, что все написанные неравенства при этом будут верны.

Комментарии от администратора Комментарии от администратора №2.     Решение 2. Будем заполнять пустые карточки последовательно слева направо по такому алгоритму. Если сразу после текущей пустой карточки идет знак «<», то пишем в нее самое маленькое из оставшихся чисел; иначе пишем самое большое из оставшихся чисел. При таком алгоритме заполнения все неравенства будут верными. В самом деле, если на текущем шаге написано число $b$, а до этого было написано число $a$, то при знаке $a < b$ неравенство верно (так как $a$ по алгоритму $a$ меньше всех стоящих правее чисел, в частности, меньше $b$), и при $a > b$ неравенство верно (так как по построению $a$ больше всех стоящих правее чисел, в частности, больше $b$).