|
|
 |
Условие
В таблице
0 1 2 3 ... 9
9 0 1 2 ... 8
8 9 0 1 ... 7
...
1 2 3 4 ... 0
отмечено 10 элементов так, что в каждой строке и каждом столбце отмечен один
элемент.
Докажите, что среди отмеченных элементов есть хотя бы два равных.
Решение 1
Пусть в i-й строке отмечено число с номером ki. Тогда сумма этих чисел по модулю 10 равна (k1 – 1) + (k2 – 2) + ... + (k10 – 10) = 55 – 55 = 0 ≠ 45 (mod 10). Поэтому она не может быть суммой чисел от 0 до 9.
Решение 2
Раскрасим таблицу в шахматном порядке так, чтобы клетка в левом верхнем углу была чёрной. Тогда в чёрных клетках стоят чётные числа, а в белых – нечётные.
Просуммируем все номера строк и столбцов выделенных отмеченных чисел. Получится чётное число 2(1 + 2 + ... + 10) (в каждой строке и в каждом столбце выделено ровно одно число). С другой стороны, каждая чёрная клетка дает в этой сумме чётный вклад, а каждый белая – нечётный. Значит, отмечено чётное количество нечётных чисел. Если же все отмеченные числа были разными, то нечётных чисел было бы пять.
Замечания
4 балла
