|
|
 |
Условие
В таблице m строк, n столбцов. Горизонтальным ходом называется такая перестановка элементов таблицы, при которой каждый элемент остаётся в той строке, в которой он был и до перестановки; аналогично определяется вертикальный ход ("строка" в предыдущем определении заменяется на "столбец"). Укажите такое k, что за k ходов (любых) можно получить любую перестановку элементов таблицы, но существует такая перестановка, которую нельзя получить за меньшее число ходов.
Решение
Случай m = 1 или n = 1 тривиален.
Пусть m ≠ 1 и n ≠ 1. Покажем, что двух ходов недостаточно. Пусть в исходной таблице левый верхний квадрат 2×2 имеет вид . Предположим, что из неё за два хода можно получить таблицу с левым верхним квадратом
. За один ход d нельзя перевести в a, следовательно, d должно переместиться на первом же ходу, причём либо на место b, либо на место c. Ввиду симметрии, это всё равно; допустим, что d переместилось на место c. Тогда по тем же соображениям a переместилось на место b, то есть левый верхний квадрат принял вид
(* означает любой элемент). При этом c осталось во второй строке. Следующий, второй ход должен быть вертикальным, чтобы d и a заняли свои места, но c находится не в первом столбце, поэтому требуемая таблица получиться не может.
Для дальнейшего нам потребуется
Теорема о сватовстве. Пусть имеется n юношей, причём для каждого k ≤ n выполнено условие: для любой группы из k юношей имеется не менее k девушек, имеющих знакомых среди этих юношей. Тогда каждого юношу можно женить на девушке, с которой он знаком.
Лемма. Пусть в таблице m×n расставлены числа от 1 до m так, что каждое встречается n раз. Тогда в каждой строке можно выбрать по числу так, что все выбранные числа различны.
Доказательство. Будем считать, что в j-й строке стоят номера девушек, знакомых с j-м юношей (то, что один номер может встретиться несколько раз, не имеет значения). Условие теоремы о сватовстве выполнено: в любых k строках стоит не меньше k различных чисел. Действительно, в k строках имеется kn мест, а k – 1 различных чисел в таблице занимают (k – 1)n < kn мест.
Покажем теперь, что любую перестановку элементов таблицы из задачи можно получить за три хода.
По лемме в каждой строке можно выбрать по элементу, которые после перестановки должны оказаться в различных строках. Соберём их горизонтальным ходом в первом столбце. Применив лемму к таблице без первого столбца, соберём (тем же ходом) во втором столбце элементы, которые также должны попасть в разные строки, и т.д.
Вторым ходом переставим элементы каждого столбца так, чтобы все элементы таблицы оказались в тех строках, где они должны быть после перестановки (в каждом столбце собраны элементы, чьи интересы различны, значит, это возможно).
Третьим ходом расставим числа в каждой строке по местам.
Ответ
Если m = 1 или n = 1, то k = 1; в противном случае k = 3.
Замечания
1. 8 баллов.
2. Доказательство теоремы о сватовстве можно найти в статье М.И. Башмакова "Паросочетания и транспортные сети" или
в книге Р. Уилсона "Введение в теорию графов", Мир, 1977.
3. Решение без формальной ссылки на теорему о сватовстве см. в решениях Задачника "Кванта".
