Слова языка роботов планеты Шелезяка — последовательности стрелочек «вверх», «вниз», «влево» и «вправо», причём две противонаправленные стрелочки не могут стоять рядом. Учитель написал на доске 1000000 слов этого языка. Четыре ученика переписывают слова к себе в тетрадь, делая следующие изменения: ученик U приписывает перед словом стрелочку вверх, а если это запрещено (слово начинается с «вниз»), то убирает это первое «вниз», ученики D, L, R делают всё то же самое, только приписывают соответственно стрелку вниз, влево или вправо, и вычёркивают первый символ, если он оказался «вверх», «вправо», «влево». Докажите, что в одной из четырёх тетрадей минимум половина (500 000) слов не будет встречаться среди слов на доске.
Разобьём слова, написанные на доске на 4 класса U, D, L, R согласно первой букве (будем маленькими буквами u, d, l, r обозначать число элементов в них, u + d + l + r = 1 000 000). Тогда в тетради ученика U будет написано u + l + r слов, начинающихся на вверх (ибо к любому слову не из класса D он припишет "вверх"). Значит, если у него в тетради содержится Nu новых слов, то 
Написав три аналогичных неравенства и сложив их вместе, получим, что
то есть 
не меньше 2 000 000.
Комментарий.
Речь, конечно, идёт о несократимых словах в свободной группе с двумя образующими. Тогда утверждается, что какое бы (конечное) подмножество в этой группе мы не взяли, при его умножении на a, b, a − 1, b − 1 хотя бы раз мы получим сильно другое множество.