Между двумя программистами завязался спор, касающийся подбора паролей к сервисам. Один из разработчиков утверждал, что за 3 попытки невозможно определить, какой из 3-х паролей к какому из 3-х сайтов относится. А второй говорил, что легко это сделает.
Вот все условия спора:
- Даны 3 логина от 3-х разных интернет-сервисов.
- Есть и пароли от них, но неизвестно, какой куда подходит.
- Можно сделать не больше 3 попыток авторизации: заходите на любые из 3 сайтов и пробуйте вводить любой пароль, главное, чтобы таких действий было только три.
Вопрос: хватит ли вам 3 попыток, чтобы правильно соотнести пароли с сервисами?
Решение
Давайте для удобства введем такие обозначения: пароли назовем буквами А, Б, и В, а сервисам дадим имена Сайт1, Сайт2 и Сайт3.
Первая попытка
Заходим на Сайт1 и вводим пароль А. Если он подошел, у нас остается два сайта, два пароля и две попытки, которых будет достаточно, чтобы определить, какой пароль от какого сервиса.
Если же первая попытка оказалась неудачной, мы делаем вывод, что пароль А подходит либо к Сайту2, либо к Сайту3. Запоминаем его и движемся дальше.
Вторая попытка
Работаем с тем же Сайтом1 и пытаемся авторизоваться с помощью пароля Б. Если получилось, значит третьей попыткой мы заходим на Сайт2 и вводим пароль А (напомните себе вывод, сделанный после первой попытки). Если он подошел, значит, пароль В от Сайта3. В другом случае пароль В подходит Сайту2, а А – Сайту3.
В условиях спора не сказано, что мы должны обязательно зайти на каждый сайт. От нас просто требуется определить, какой пароль от какого сервиса. Так что даже если третья попытка окажется неудачной (пароль не подойдет), мы все равно поймем, какое соотношение правильное, и выиграем спор.
Если же вторая попытка показала, что пароль Б не подходит к Сайту1, мы делаем следующий вывод: пароль от Сайта1 – это точно В (так как А и Б мы исключили).
Третья попытка
Мы уже установили, что на Сайте1 точно можно авторизоваться с помощью пароля В. Значит, пароли А и Б относятся к двум другим сервисам.
Заходим на Сайт2 с паролем А:
- если получилось, то к Сайту3 подходит пароль Б (мы победили в споре);
- если не получилось, то к Сайту3 подходит пароль А, а к Сайту 2 – пароль Б (мы победили в споре).
Вывод
Второй программист оказался прав – чтобы соотнести три пароля с тремя сервисами, хватит и 3-х попыток.