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

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

  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, и мы выиг­ра­ли спор.

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