Задача 116381
|
|
 |
Условие
В каждой клетке секретной таблицы n×n записана одна из цифр от 1 до 9. Из них получаются n-значные числа, записанные в строках слева направо и в столбцах сверху вниз. Петя хочет написать такое n-значное число без нулей в записи, чтобы ни это число, ни оно же, записанное задом наперед, не совпадало ни с одним из 2n чисел в строках и столбцах таблицы. В каком наименьшем количестве клеток Петя должен для этого узнать цифры?
Решение
Если проверено менее n клеток, то в какой-то из строк проверенных клеток нет, а там могут оказаться любые числа.Пусть Петя проверил n клеток по диагонали, на пересечении строк и столбцов с одинаковыми номерами. Тогда Пете достаточно предъявить число-палиндром, у которого на i-м и (n–i)-м местах стоит одна и та же цифра, отличающаяся от цифр в проверенных клетках i-й и (n–i)-й строк. Такое число будет отличаться от чисел в k-й строке и k-м столбце как раз k-й цифрой.
Ответ
В n клетках.
