Олимпиадная задача о 100 эльфах, гномах и орках у таверны

Решение 1:Назовёмтипомкомпании остаток разности количества эльфов и количества гномов при делении на три. Заметим, что компаний типа 1 и 2 одинаковое количество, так как между ними можно построить взаимно однозначное соответствие: пронумеруем эльфов и гномов от 1 до 100 и поменяем одних на других с теми же номерами. Далее заметим, что компании меняются по циклу $0 \to 1 \to 2 \to 0 \ldots$, причём, так как компаний типов 1 и 2 поровну, мы не можем закончить на 1, то есть количество всех компаний не может давать остаток 2 при делении на 3. Вычислим $C_{300}^{30}$ по модулю 3. \begin{align*} C_{300}^{30} &= \frac{300\cdot299\cdot298\cdot\ldots\cdot273\cdot272\cdot271}{30\cdot29\cdot28\cdot\ldots\cdot3\cdot2\cdot1} =\ &= \frac{299\cdot298\cdot296\cdot\ldots\cdot274\cdot272\cdot271}{29\cdot28\cdot26\cdot\ldots\cdot4\cdot2\cdot1}\cdot\frac{100\cdot99\cdot\ldots\cdot92\cdot91}{10\cdot9\cdot\ldots\cdot2\cdot1}\equiv\ &\equiv \frac{100\cdot99\cdot\ldots\cdot92\cdot91}{10\cdot9\cdot\ldots\cdot2\cdot1} = \frac{100\cdot98\cdot\ldots\cdot94\cdot92\cdot91}{10\cdot8\cdot\ldots\cdot4\cdot2\cdot1}\cdot\frac{33\cdot32\cdot31}{3\cdot2\cdot1}\equiv \ &\equiv\frac{33\cdot32\cdot31}{3\cdot2\cdot1}=11\cdot16\cdot31\equiv2\pmod3. \end{align*} Противоречие, значит, так оказаться не могло. Комментарий.Есть другой способ посчитать остаток $C_{300}^{30}$ при делении на 3. Теорема Люка утверждает, что если $p$ – простое число, а числа $n$ и $k$ записываются в $p$-ичной системе счисления как $n= \sum n_ip^i$ и $k = \sum k_ip^i$, то $C_n^k\equiv\prod C_{n_i}^{k_i}\pmod p$. Запишем $300$ и $30$ в троичной системе счисления: $300 = (102010)_3$ и $30 = (1010)3$. Таким образом, $C{300}^{30}\equiv C_1^0C_0^0C_2^1C_0^0C_1^1C_0^0=2\pmod3$.

Решение 2:Разделим все компании на три типа, как в прошлом решении, по остатку разности количества эльфов и количества гномов при делении на $3$. Если описанное в задаче возможно, то количество компаний разных типов отличается не более чем на $1$, так как типы компаний меняются по циклу. Пронумеруем представителей всех рас от $1$ до $100$. Разобьем на тройки все компании, в которых множества номеров хотя бы каких-то двух рас различны, следующим образом. Возьмем некую компанию данного вида и рассмотрим максимальный номер, представленный хотя бы одной, но не всеми расами. Дважды «прокрутим» всех существ с этим номером, поменяв каждое существо на существо «следующей» расы с таким же номером. Легко видеть, что исходная и две полученные компании различных типов, причем с помощью данной операции они могут быть получены только друг из друга. При этом все компании не данного вида, коих всего $C_{100}^{10}$, имеют тип $0$, то есть компаний типа $0$ ровно на $\smash{C_{100}^{10}}$ больше, чем других, – противоречие.

Не могло.