|
|
 |
Условие
В клетках таблицы 10×10 произвольно расставлены натуральные числа от 1 до 100, каждое по одному разу. За один ход разрешается поменять местами любые два числа. Докажите, что за 35 ходов можно добиться того, чтобы сумма каждых двух чисел, стоящих в клетках с общей стороной, была составной.
Решение
Разделим таблицу вертикальной линией l пополам. В одной из половин, например в правой, окажется не более 25 чётных чисел. Такое же количество нечётных чисел окажется в левой половине. Меняя местами пары таких чисел разной чётности, не более чем за 25 ходов можно получить таблицу,
у которой в правой половине все числа – нечётны, а в левой – чётны. Сумма чисел в каждой паре соседних клеток в каждой из половин – чётное (и большее 2), а потому составное число.
Простыми могут оказаться только суммы чисел в соседних клетках mj и nj из разных половин, примыкающих к линии l. Будем теперь менять местами числа только из правой половины так, чтобы суммы чисел в парах клеток (mj, nj) (j = 1, 2, ..., 10) стали делиться на три. Это можно сделать, так как в правой половине не менее чем по 16 чисел дают остатки 0, 1 и 2 при делении на 3, а для требуемой перестановки может потребоваться не более чем по 10 чисел, дающих эти остатки. Полученная не более чем за 25 + 10 = 35 ходов таблица – искомая.
