ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 111851
Темы:    [ Числовые таблицы и их свойства ]
[ Разбиения на пары и группы; биекции ]
[ Делимость чисел. Общие свойства ]
[ Процессы и операции ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

В клетках таблицы 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  ходов таблица – искомая.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2007
Этап
Вариант 5
Класс
Класс 8
задача
Номер 07.5.8.2

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .