Задача про программистов и подбор пароля

Как за три попытки определить пароль.

Задача про программистов и подбор пароля

Два программиста поспорили друг с другом про подбор паролей. Первый говорил, что невозможно всего за три попытки понять, какой из трёх паролей относится к какому из трёх сервисов. Второй программист утверждал, что за три попытки он легко это выяснит. Кто из них прав, если полные условия спора такие:

  1. Есть три логина от разных сервисов в интернете.
  2. Есть пароль от каждого сервиса, но непонятно, какой пароль от какого сервиса.
  3. Суммарно есть три попытки ввода логина и пароля. Можно выбирать любой сервис и любой пароль, но таких выборов всего можно сделать три.
  4. Хватит ли трёх таких попыток, чтобы понять, какой пароль к какому сервису относится?

Обозначим пароли буквами X, Y и Z, а сервисы — Сервис1, Сервис2 и Сервис3. Это поможет нам не запутаться при решении, что к чему будет относиться.

Первая попытка: берём Сервис1 и пробуем к нему пароль X. Если мы угадали с первой попытки, то у нас остаётся 2 попытки на 2 оставшихся сервиса — этого достаточно, чтобы выяснить, какой пароль откуда.

Если мы не угадали и пароль X не подходит к Сервису1,  значит, этот пароль точно подходит к Сервисам 2 или 3. Запомним эту мысль и пойдём дальше.

Вторая попытка: берём всё тот же Сервис1 и пробуем к нему пароль Y. Если подходит, то третьей попыткой берём Сервис2 и пробуем к нему пароль X (вспомните вывод из первой попытки). Если тоже подходит, то пароль Z относится к Сервису3, а если нет, то, наоборот, пароль Z относится к Сервису2, а X — к Сервису3. 

👉 По условиям спора нам нужно не зайти в каждый сервис, а просто понять, какой пароль откуда. Поэтому даже если на третьей попытке мы не угадаем с паролем, это поможет нам выяснить, какой пароль к чему относится, и выиграть спор.

Если мы не угадали на второй попытке и пароль Y не подходит к Сервису1, то можно сделать такие выводы:

  • к Сервису1 точно подходит пароль Z;
  • пароль Y подходит к Сервисам 2 или 3.

Эти выводы нам пригодятся на последней попытке.

Третья попытка. Мы уже знаем, что к Сервису1 точно подходит пароль Z. Это значит, что два других пароля X и Y относятся к Сервисам 2 и 3. Попробуем зайти в Сервис2 с паролем X:

  • если сработает, то к Сервису3 подходит пароль Y и мы выиграли спор;
  • если не сработает, то к Сервису3 подходит пароль X, а к Сервису2 — пароль Y, и мы выиграли спор.

Получается, что второй программист был прав — трёх попыток будет достаточно.

Обложка:

Даня Берковский

Корректор:

Ирина Михеева

Вёрстка:

Маша Климентьева

Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
А вы читали это?
Задача Эйнштейна
Задача Эйнштейна

Учёный утверждал, что только 2% людей могут решить в уме эту задачу (так говорят в Википедии).

hard
Коктейльная задача про доли и крепость
Коктейльная задача про доли и крепость

Ну, будем!

easy
Задача про полторы белки
Задача про полторы белки

Не спрашивайте, просто попробуйте решить.

easy
Задача про семейный быт
Задача про семейный быт

Что будет, если спрятать ужин.

medium
Один футболист против законов математики
Один футболист против законов математики

Самое простое и понятное объяснение теории вероятностей, которое вы встретите.

medium
Хитрая головоломка про мандарины, секрет которой поймут только те, кто умеет логически мыслить
Хитрая головоломка про мандарины, секрет которой поймут только те, кто умеет логически мыслить

Секрет прост, но его нужно сформулировать

easy
Крутейшие задачи на комбинаторику
Крутейшие задачи на комбинаторику

Комбинаторика и поиск наилучшего решения для всех.

medium
9 простых задач на математику
9 простых задач на математику

Всё настолько просто, что половину можно решить в уме.

easy
Хитрая задача про реку от русского преподавателя в американском колледже
Хитрая задача про реку от русского преподавателя в американском колледже

И большинство студентов не смогли её решить с первой попытки

easy
easy