Слова языка роботов планеты Шелезяка — последовательности стрелочек «вверх», «вниз», «влево» и «вправо», причём две противонаправленные стрелочки не могут стоять рядом. Учитель написал на доске 1000000 слов этого языка. Четыре ученика переписывают слова к себе в тетрадь, делая следующие изменения: ученик U приписывает перед словом стрелочку вверх, а если это запрещено (слово начинается с «вниз»), то убирает это первое «вниз», ученики D, L, R делают всё то же самое, только приписывают соответственно стрелку вниз, влево или вправо, и вычёркивают первый символ, если он оказался «вверх», «вправо», «влево». Докажите, что в одной из четырёх тетрадей минимум половина (500 000) слов не будет встречаться среди слов на доске.
Версия для копирования в MS Word
PDF-версии: горизонтальная · вертикальная · крупный шрифт · с большим полем
Написав три аналогичных неравенства и сложив их вместе, получим, что
не меньше 2 000 000.