МОШ 2025, 10 класс, задача 6
Около таверны стоят эльфов, гномов и орков. Сначала в неё заходят эльфов, гномов и орков. Затем каждую минуту из неё выходит одно существо и тут же заходит другое, причём всегда после выхода эльфа заходит гном, после выхода гнома — орк, а после выхода орка — эльф. Могло ли оказаться так, что к какому-то моменту в таверне побывали все возможные компании из существ ровно по одному разу? Все существ различны.
(М. Федотова)
Ответ
Ответ: нет, не могло.
Решение. Назовём типом компании остаток разности количества эльфов и количества гномов при делении на три. Заметим, что компаний типа и одинаковое количество, так как между ними можно построить взаимнооднозначное соответствие: пронумеруем эльфов и гномов от до и поменяем одних на других с теми же номерами. Далее заметим, что компании меняются по циклу , причём, так как компаний типов и поровну, мы не можем закончить на , то есть количество всех компаний не может давать остаток при делении на . Вычислим по модулю .
Противоречие, значит, так оказаться не могло.
Замечание. Есть другой способ посчитать остаток при делении на . Теорема Люка утверждает, что если — простое число, а числа и записываются в -ичной системе счисления как и , то . Запишем и в троичной системе счисления: и . Таким образом,
Другое решение. Как и в прошлом решении разделим все компании на три типа. Если описанное в задаче возможно, то количества компаний разных типов отличается не более чем на , так как типы компаний меняются по циклу. Пронумеруем представителей всех рас от до . Разобьем на тройки все компании, в которых множества номеров хотя бы каких-то двух рас различны, следующим образом. Возьмем некую компанию данного вида и рассмотрим максимальный номер, представленный хотя бы одной, но не всеми расами. Дважды «прокрутим» всех существ с этим номером, поменяв каждое существо на существо «следующей» расы с таким же номером. Легко видеть, что исходная и две полученные компании различных типов, причем с помощью данной операции они могут быть получены только друг из друга. При этом все компании не данного вида, коих всего , имеют тип , то есть компаний типа ровно на больше, чем других — противоречие.