Задача 67591
|
|
 |
Условие
Таблица $n\times n$ заполнена целыми числами от 0 до $n$ так, что и в каждой строке, и в каждом столбце все числа различны. Назовём клетку таблицы удачной, если в объединении её строки и её столбца встречаются все числа от 0 до $n$.а) Каково наибольшее возможное количество удачных клеток?
б) Докажите, что количество удачных клеток чётно.
Решение
а) Оценка 1. Докажем, что в каждой строке есть неудачная клетка. Предположим, что в некоторой строке отсутствует какое-то число $a$ из набора $0,1,2\ldots,n$, а все клетки в ней удачные. Тогда в каждом столбце есть число $a$. Таким образом, в $n-1$ строках число $a$ встречается $n$ раз, а значит, в какой-то строке оно записано более одного раза, что противоречит условию. Следовательно, удачных клеток не больше $n^2 - n$.Оценка 2. Заметим, что в каждом ряду отсутствует ровно одно из разрешённых чисел, а остальные встречаются по одному разу. Очевидно, клетка неудачна тогда и только тогда, когда она лежит на пересечении строки и столбца, в которых отсутствует одно и то же число. Пусть число $i$ отсутствует ровно в $k_i$ строках. Тогда в таблице $n - k_i$ чисел $i$, поэтому оно отсутствует ровно в $k_i$ столбцах. Следовательно, количество неудачных клеток равно $k_0^2+k_1^2+\ldots+k_n^2$.
Заметим, что $k_0 + k_1 + \ldots + k_n = n$. Значит, $$k_0^2+k_1^2+\ldots+k_n^2 - n = k_0(k_0 - 1) + k_1(k_1 - 1) + \ldots + k_n(k_n - 1) \geqslant 0$$ (каждое слагаемое неотрицательно). Следовательно, удачных клеток не больше $n^2 - n$.
Пример. В таблице на рисунке неудачны только клетки главной диагонали.
Решение 1. Чётность числа $k_0^2+k_1^2+\ldots+k_n^2$, очевидно, равна чётности $k_0 + k_1 + \ldots + k_n = n$, то есть чётности $n^2$. Поэтому количество удачных клеток чётно.
Решение 2. Клетка удачная, если в её строке и столбце отсутствующие числа разные. В строках с отсутствующим нулём, например, таких клеток $k_0(k_1+\ldots+k_n)$, и аналогично для других чисел. Поэтому общее количество удачных клеток равно сумме произведений $k_ik_j$, где $i\ne j$. Но это удвоенная сумма произведений $k_ik_j$, где $i < j$, то есть чётное число.
Решение 3. Если удачных клеток 0, то задача решена (0 — чётное число). Иначе пусть $(x,y)$ — удачная клетка ($x$ — номер строки, $y$ — номер столбца). Посмотрим на её строку. В ней нет ровно одного какого-то числа из набора $0,1,2\ldots,n$, пусть это $a$. Значит, в столбце $y$ есть число $a$, пусть оно находится в клетке $(x_0,y)$. Тогда в строке $x_0$ нет какого-то другого числа, пусть $b$. Так как $b$ не равно $a$, то в изначальной строке $x$ есть число $b$. Пусть оно имеет координаты $(x, y_0)$. Тогда очевидно, что клетка $(x_0, y_0)$ — удачная. Её и сопоставим исходной удачной клетке $(x,y)$. Так мы разобьём удачные клетки на пары.
Для корректности надо проверить, что никакой клетке не сопоставится она же сама (это очевидно, так как сопоставление происходит между разными строками), и что клетке с координатами $(x_0, y_0)$ сопоставится клетка с координатами $(x,y)$. Это тоже понятно.
