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