Задача 79599

Тема:    [ Теория алгоритмов (прочее) ]

Сложность: 4 Классы: 8,9,10,11

Условие

Автор: Скопенков А.Б.

Колоду из 54 карт фокусник разложил на несколько кучек, а зритель на всех картах каждой кучки написал число, равное количеству карт в этой кучке. Затем фокусник специальным образом перемешал карты и ещё раз разложил их на кучки, а зритель написал на каждой карте ещё одно число, равное количеству карт в новой кучке, и т.д. При каком наименьшем количестве раскладок фокусник мог добиться того, чтобы на разных картах оказались разные множества чисел (как бы ни располагал их зритель на карте)?

Подсказка

Воспользуйтесь решением пункта б) задачи для 9 класса.

Решение

Покажем, что фокусник мог добиться нужного результата за три раскладки. Пусть первые две раскладки таковы, что среди упорядоченных пар чисел, написанных после этого на картах, нет одинаковых, но для каждой пары $(m,n)$ можно найти пару $(n,m)$. Возможный способ такой пары раскладок приведён в решении пункта б) задачи для 9 класса и проиллюстрирован следующей таблицей.

Поскольку номера после первой и второй раскладок зритель мог расположить на карте в разном порядке, при $m \ne n$ множество чисел $\{ m, n\}$ будет соответствовать двум картам. При третьей раскладке фокусник может разложить все карты на две кучки так, чтобы такие карты попали в разные кучки, а затем в одну из кучек добавить оставшиеся карты, на которых написаны пары чисел $(n,n)$, $n=9$, $8$, $7$, $6$, $2$, $1$ (например, в одну кучку сложить карты, находящиеся в таблице над диагональю и на ней, а в другую – стоящие под диагональю). Тогда в одной кучке окажется $24$ карты, а в другой $30$, так что ранее неразличимые пары $(m, n)$ и $(n, m)$, где $m < n \le 9$, станут различными тройками $\{ m, n, 30\}$ и $\{ m, n, 24\}$.

Докажем теперь, что двух раскладок недостаточно. Действительно, предположим, что существуют такие две раскладки, после которых на всех картах оказались написаны разные множества чисел. Проиллюстрируем эти раскладки таблицей размера $k \times k$, где $k$ – число карт в наибольшей из всех кучек, образованных при этих раскладках, $k > 1$. Пусть натуральные числа $m$ и $n$ пробегают все значения от $1$ до $k$. Если найдётся такая карта, на которой при первой раскладке написали число $m$, а при второй – $n$, то отметим общую ячейку $m$-й строки и $n$-го столбца крестиком, иначе оставим эту ячейку пустой (см. рисунок).

Поскольку при этих раскладках была образована кучка из $k$ карт, либо в $k$-й строке, либо в $k$-м столбце найдётся отмеченная крестиком ячейка. По предположению на всех $k$ картах из этой кучки написаны разные множества чисел, поэтому отмечены крестиками и все другие ячейки этой строки или этого столбца. Значит, отмечена крестиком и ячейка на пересечении $k$-й строки и $k$-го столбца. Аналогичные рассуждения показывают, что тогда отмечены крестиками все ячейки как $k$-й строки, так и $k$-го столбца. Следовательно, найдутся две разные карты, на которых написано множество чисел $\{ 1, k\}$. Пришли к противоречию.

Ответ

3.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	54
Год	1991
вариант
Класс	10
задача
Номер	5