|
|
 |
Условие
Василиса Премудрая расставляет все натуральные числа от 1 до n², где n > 1, в клетки таблицы размером n×n. Кандидат в женихи должен вычеркнуть строку и столбец так, чтобы сумма всех оставшихся чисел была чётной. Всегда ли выполнимо такое задание?
Решение
Заметим, что чётность суммы чисел в такой таблице n×n совпадает с чётностью числа n. Объединение строки и столбца, в которых находится число в таблице, будем называть его перекрестием. Если n чётно, то кандидат в женихи должен вычеркнуть перекрестие, в котором сумма чисел чётна, а если n нечётно, то он должен вычеркнуть перекрестие с нечётной суммой чисел.
Для каждого числа в таблице подсчитаем сумму чисел в его перекрестии и сложим все полученные суммы. Тогда каждое число из таблицы будет учтено
2n – 1 раз, поэтому получим S = (2n – 1)(1 + 2 + ... + n²). Следовательно, чётность числа S совпадает с чётностью числа n.
Пусть n чётно. Рассмотрим два случая.
1) В таблице есть строка или столбец с нечётной суммой чисел. Пусть, для определенности, это будет строка L, тогда среди чисел этой строчки найдётся такое, что сумма чисел его перекрестия чётна. Действительно, если такого перекрестия нет, то сумма чисел в каждом столбце без числа в строке L чётна (иначе данное перекрестие было бы искомым), а значит, сумма чисел во всех строках, кроме L, чётна. Но сумма чисел в самой строке L нечётна, а то это противоречит тому, что сумма всех чисел таблицы чётна.
2) Во всех строках и столбцах таблицы сумма чисел чётная. Тогда кандидату в женихи достаточно вычеркнуть перекрестие любого чётного числа.
Пусть n нечётно. Тогда, так как число S нечётно, в таблице найдётся перекрестие с нечётной суммой чисел.
Ответ
Всегда.
