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

Проект МЦНМО
при участии
школы 57
Задача 116722
Темы:    [ Теория алгоритмов (прочее) ]
[ Принцип Дирихле (прочее) ]
Сложность: 4+
Классы: 10,11
В корзину
Прислать комментарий

Условие

Автор: Жуков Г.

Банк обслуживает миллион клиентов, список которых известен Остапу Бендеру. У каждого есть свой PIN-код из шести цифр, у разных клиентов коды разные. Остап Бендер за один ход может выбрать любого клиента, которого он еще не выбирал, и подсмотреть у него цифры кода на любых N позициях (у разных клиентов он может выбирать разные позиции). Остап хочет узнать код миллионера Корейко. При каком наименьшем N он гарантированно сможет это сделать?


Решение

  Это нетрудно сделать при  N = 3.  Так как любая комбинация из первых трёх цифр встречается ровно по 1000 раз, то посмотрев эти цифры у всех, кроме Корейко, Бендер будет знать их и у Корейко. Далее достаточно посмотреть три последние цифры у Корейко.
  Докажем, что при  N < 3  нельзя гарантированно узнать код Корейко К. Для каждой из 6 позиций выберем код, который от К отличается только в этой позиции. Соответствующую цифру в выбранном коде назовём плохой. Пусть Бендеру не повезло, и при первой же проверке не Корейко ему попался выбранный код, причём плохую цифру он не проверил (есть четыре непроверенные позиции, мог попасться код с плохой цифрой на одной из этих позиций). Пусть то же случилось при второй и третьей проверках не Корейко (есть четыре непроверенных позиции, из четырёх выбранных кодов с плохой цифрой на этих местах ранее проверено не более двух, значит, такой код мог попасться). Когда все коды проверены, посмотрим, какие  N < 3  позиций проверены в коде К. Из четырёх непроверенных позиций хотя бы одна совпадает с позицией плохой цифры в однм из трёх проверенных выбранных кодов – кода L. Но если поменять местами L и К, то результаты всех проверок не изменятся. Значит, Бендер не сможет отличить L от К.


Ответ

При  N = 3.

Замечания

8 баллов

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

олимпиада
Название Турнир городов
Турнир
Дата 2011/2012
Номер 33
вариант
Вариант весенний тур, сложный вариант, 8-9 класс
Задача
Номер 6

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

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