Математикадан Эйлер олимпиадасы, 2010-2011 оқу жылы, Дистанциялық кезеңнің 1-ші туры

101 карта қатарынан тізіліп қойылсын. Әрбір жұп орында жатқан картаға «$ > $» не «$ < $» белгісі салынсын. Белгілердің кез-келген орналасуында, қалған карталарға, шыққан теңсіздік орындалатындай $1$, $2$, $\ldots$, $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$).