Областная олимпиада по математике, 2009 год, 11 класс

Два фокусника показывают трюк. Первый фокусник выходит из комнаты, а затем второй фокусник берёт колоду из 100 карт, пронумерованных числами от 1 до 100, и просит каждого из трех участников выбрать по очереди по одной карте, и при этом он видит какую карту взял каждый. Затем он сам добавляет еще одну карту к трем выбранным из оставшейся колоды. Участники вызывают первого фокусника, предварительно перемешав 4 карты произвольным образом, и дают ему их. Первый фокусник смотрит на эти 4 карты и «угадывает» какую карту выбирал каждый из участников. Докажите, что фокусники смогут исполнить этот трюк.

Комментарий/решение

Решение предложил Сапаргали Сейтенов.

Прежде чем обсуждать решение задачи, поговорим о перестановках 4-ой степени. Раз речь идет о четырех картах, речь будет идти о четырех числах. Перестановкой 4-ой степени называется расположение чисел 1, 2, 3, 4 в каком-то порядке. Существует $4! = 24$ перестановок 4-ой степени:

$\begin{array}{c|c}№&Перестановка\\\hline0&1234\\1&1243\\2&1324\\3&1342\\4&1423\\5&1432\end{array}$$\begin{array}{c|c}№&Перестановка\\\hline6&2134\\7&2143\\8&2314\\9&2341\\10&2413\\11&2431\end{array}$$\begin{array}{c|c}№&Перестановка\\\hline12&3124\\13&3142\\14&3214\\15&3241\\16&3412\\17&3421\end{array}$$\begin{array}{c|c}№&Перестановка\\\hline18&4123\\19&4132\\20&4213\\21&4231\\22&4312\\23&4321\end{array}$

Здесь перестановки перечислены в лексикографическом (словарном) порядке, т.е., сравниваются первые цифры. Если равны первые цифры, то сравниваются вторые цифры. Если $k$-я цифра у одной перестановки меньше, чем у другой, то первая перестановка считается меньшей. Фокусники могут выбрать и другую систему нумерации перестановок, но мы будем считать, что они придерживаются традиционной системы.

Вместо чисел 1, 2, 3, 4 можно выбирать и другие различные 4 числа, например: если даны числа 17, 23, 72, 99, то в этой таблице вместо чисел 1, 2, 3, 4 надо поставить соответственно числа 17, 23, 72, 99, расположенные в возрастающем порядке. В этом случае первые 6 перестановок получат следующие номера: 0–17, 23, 72, 99; 1–17, 23, 99, 72; 3–17, 72, 23, 99; 4–17, 72, 23, 99; 5–17, 72, 99, 23.

Пусть участники 1, 2, 3 выбрали карту с номерами $a_1$, $a_2$, $a_3$. Четвертая карта имеет номер $a_4$, причем он выбирает такой номер $a_4$, чтобы первый фокусник мог однозначно решить задачу.

Всегда найдутся 24 последовательных числа от 1 до 100, отличные от $a_1$, $a_2$, $a_3$. Среди этих 24 чисел найдутся все остатки при делении на 24. Из этих чисел второй фокусник выберает карту с наименьшим номером $a_4$ так, чтобы остаток от деления суммы $a_1 + a_2 + a_3 + a_4$ на 24 был равен номеру перестановки $a_1$, $a_2$, $a_3$, $a_4$.

Например, если $a_1 = 99$, $a_2 = 72$, $a_3 = 36$, то число $a_4$ можно выбрать в промежутках $[1, 24]$, $[37, 60]$. Если выбрать число $a_4$ в промежутке $[1, 24]$, то перестановка $a_1$, $a_2$, $a_3$, $a_4$ будет соответствовать перестановке 4, 3, 2, 1, которая имеет номер 23. Чтобы сумма $a_1 + a_2 + a_3 + a_4$ при делении на 24 давала остаток 23, нужно выбрать $a_4 = 8$.

Число $a_4$ можно выбрать и в промежутке $[37, 60]$. В этом случае перестановка $a_1$, $a_2$, $a_3$, $a_4$ будет соответствовать перестановке 4, 3, 1, 2, которая имеет номер 22. Тогда нужно выбрать в качестве $a_4$ число 55.

Пусть теперь $a_1 = 72$, $a_2 = 99$, $a_3 = 36$. Как и в предыдущем случае, число $a_4$ также можно выбрать в промежутках $[1, 24]$, $[37, 60]$. Если выбрать число $a_4$ в промежутке $[1, 24]$, то перестановка $a_1$, $a_2$, $a_3$, $a_4$ будет соответствовать перестановке 3, 4, 2, 1, которая имеет номер 17. Чтобы сумма $a_1 + a_2 + a_3 + a_4$ при делении на 24 давала остаток 17, нужно выбрать $a_4 = 2$.

Число $a_4$ можно выбрать и в промежутке $[37, 60]$. В этом случае перестановка $a_1$, $a_2$, $a_3$, $a_4$ будет соответствовать перестановке 3, 4, 1, 2, которая имеет номер 16. Тогда можно выбрать в качестве $a_4$ число 49.