Теория чисел на ММО

Первое решение.

Назовём типом компании остаток разности количества эльфов и количества гномов при делении на три. Заметим, что компаний типа 1 и 2 одинаковое количество, так как между ними можно построить взаимооднозначное соответствие: пронумеруем эльфов и гномов от 1 до 100 и поменяем одних на других с теми же номерами. Далее заметим, что компании меняются по циклу причём, так как компаний типов 1 и 2 поровну, мы не можем закончить на 1, то есть количество всех компаний не может давать остаток 2 при делении на 3. Вычислим по модулю 3.

Противоречие, значит, так оказаться не могло.

Замечание. Есть другой способ посчитать остаток при делении на 3. Теорема Люка утверждает, что если — простое число, а числа и записываются в -ичной системе счисления как и то Запишем 300 и 30 в троичной системе счисления: и Таким образом,

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

Как и в прошлом решении разделим все компании на три типа. Если описанное в задаче возможно, то количества компаний разных типов отличается не более чем на 1, так как типы компаний меняются по циклу. Пронумеруем представителей всех рас от 1 до 100. Разобьем на тройки все компании, в которых множества номеров хотя бы каких-то двух рас различны, следующим образом. Возьмем некую компанию данного вида и рассмотрим максимальный номер, представленный хотя бы одной, но не всеми расами. Дважды прокрутим всех существ с этим номером, поменяв каждое существо на существо следующей расы с таким же номером. Легко видеть, что исходная и две полученные компании различных типов, причем с помощью данной операции они могут быть получены только друг из друга. При этом все компании не данного вида, коих всего имеют тип 0, то есть компаний типа 0 ровно на больше, чем других — противоречие.