ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 116381
Темы:    [ Примеры и контрпримеры. Конструкции ]
[ Числовые таблицы и их свойства ]
Сложность: 3
Классы: 8,9
В корзину
Прислать комментарий

Условие

В каждой клетке секретной таблицы n×n записана одна из цифр от 1 до 9. Из них получаются n-значные числа, записанные в строках слева направо и в столбцах сверху вниз. Петя хочет написать такое n-значное число без нулей в записи, чтобы ни это число, ни оно же, записанное задом наперед, не совпадало ни с одним из 2n чисел в строках и столбцах таблицы. В каком наименьшем количестве клеток Петя должен для этого узнать цифры?


Решение

   Если проверено менее n клеток, то в какой-то из строк проверенных клеток нет, а там могут оказаться любые числа.
   Пусть Петя проверил n клеток по диагонали, на пересечении строк и столбцов с одинаковыми номерами. Тогда Пете достаточно предъявить число-палиндром, у которого на i-м и (ni)-м местах стоит одна и та же цифра, отличающаяся от цифр в проверенных клетках i-й и (ni)-й строк. Такое число будет отличаться от числа в k-й строке или столбце как раз k-й цифрой.


Ответ

В n клетках.

Замечания

баллы: 4

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 2011/2012
Номер 33
вариант
Вариант осенний тур, базовый вариант, 10-11 класс
Задача
Номер 2

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .