|
|
 |
Условие
В таблицу 10×10 нужно записать в каком-то порядке цифры 0, 1, 2, 3, ..., 9 так, что каждая цифра встречалась бы 10 раз.
а) Можно ли это сделать так, чтобы в каждой строке и в каждом
столбце встречалось не более четырёх различных цифр?
б) Докажите, что найдётся строка или столбец, в которой (в котором) встречается не меньше четырёх различных чисел.
Решение
а) См. рис. (цифры заменены цветами)
б) Пусть в каждом ряду встречается не более трёх различных цифр, причём цифра n встречается в an строках и bn столбцах. Сумма a0 + ... + a9 равна количеству "вхождений" всех цифр во все строки, то есть не превосходит 30. Аналогично b0 + ... + b9 ≤ 30.
С другой стороны, anbn ≥ 10, поэтому an + bn ≥ 7. Значит, a0 + ... + b9 ≥ 70. Противоречие.
Ответ
а) Можно.
Замечания
баллы: 6 + 16
