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