Два программиста поспорили друг с другом про подбор паролей. Первый говорил, что невозможно всего за три попытки понять, какой из трёх паролей относится к какому из трёх сервисов. Второй программист утверждал, что за три попытки он легко это выяснит. Кто из них прав, если полные условия спора такие:
- Есть три логина от разных сервисов в интернете.
- Есть пароль от каждого сервиса, но непонятно, какой пароль от какого сервиса.
- Суммарно есть три попытки ввода логина и пароля. Можно выбирать любой сервис и любой пароль, но таких выборов всего можно сделать три.
- Хватит ли трёх таких попыток, чтобы понять, какой пароль к какому сервису относится?
Обозначим пароли буквами 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, и мы выиграли спор.
Получается, что второй программист был прав — трёх попыток будет достаточно.
