Эту задачу в немного переработанном виде и, естественно, на английском, давали студентам Массачусетского Технологического Института — самого престижного технического ВУЗа мира. Но не надо бояться. Это только звучит страшно. На самом деле в СССР (да и сейчас иногда) такие задачки решали в 7 классе.
Итак, вольный пересказ условия задачи. У нас есть три сайта с вбитыми логинами. И есть три пароля. Но какой пароль от какого сайта никто не знает. Известно лишь, что пароли разные и каждый подходит только к одному из этих трех сайтов. Возможно ли за три попытки понять, какой пароль от какого сайта?
Несколько важных замечаний. У нас нет цели залогиниться на каждом из трех сайтов, надо лишь наверняка понять, какой пароль от какого сайта. И второе — у нас три попытки на всё про всё. Можно все попытки использовать на одном сайте, можно на каждом сайте совершить по одной попытке, а можно любым другим способом.
Попробуйте решить задачу сами. Никаких сложных формул тут нет, сугубо логика и алгоритмы. В СССР подобных задач было очень много. В основном про то, как узнать, какая монета фальшивая. Были целые сборники с вариациями таких задач. И у себя на канале я их разбирал (в МГУ на вступительных или на собеседованиях тоже подобное встречалось). Если хотите, то можете сначала ознакомиться с ними, а потом попробовать решить эту задачу. Вот хороший пример.
Решение
Давайте для простоты обозначим сайты цифрами 1, 2 и 3, а пароли буквами А, Б и В.
Первая попытка
Вводим пароль А на первый сайт. Тут два варианта. Либо пароль подошел и тогда мы за две других попытки (а если повезет, то за одну) однозначно определим какой пароль от какого сайта. Либо пароль не подошел и тогда мы пользуемся второй попыткой, а для себя в голове отмечаем, что пароль А подходит либо ко второму, либо к третьему сайту.
Вторая и третья попытки
Продолжаем работать с первым сайтом и вбиваем в него пароль Б. Тут снова два варианта: либо подошел, либо нет.
а)Если пароль подходит, то третью попытку мы используем для того, чтобы понять, подходит ли пароль А ко второму сайту или нет. Нас устроит любой результат, потому что при любом исходе мы точно будем понимать, какой пароль для какого сайта.
Если пароль А подходит ко второму сайту, тогда: 1—Б; 2—А; 3—В.
Если же пароль А не подходит ко второму сайту тогда: 1—Б; 2—В; 3—А.
б) Если же и пароль Б не подходит для первого сайта, то мы делаем вывод, что для него подойдет пароль В. А третьей попыткой проверяем, подходит ли пароль А ко второму сайту. И снова вне зависимости от результата мы однозначно понимаем что к чему.
Если пароль А подходит ко второму сайту, тогда: 1—В; 2—А; 3—Б.
Если же пароль А не подходит ко второму сайту тогда: 1—В; 2—Б; 3—А.
Набросал от руки алгоритм, если кому-то это будет удобнее.
Вот и вся задача. Как видите, в любом случае трех попыток будет достаточно, чтобы установить четкое соответствие сайтов с логинами и паролей к ним. При этом задача залогиниться на каждом сайте будет выполнена не всегда. Но этого и не требовалось по условию.
Что скажете? Удалось разобраться в хитросплетениях логики? Один из моих подписчиков Кирилл Дмитриевич, например, считает, что понять задачи такого олимпиадного уровня даже по готовому решению дано далеко не всем умам. Что думаете на этот счет?
И не устаю напоминать, что у меня есть каналы на Ютубе, в Инстаграме и ТикТоке. Стоит подписаться хотя бы на один из них как минимум для того, чтобы не потеряться в случае, если с этим каналом произойдет что-то неприятное.
Ещё интересно: "Бородатая" задачка, которая до сих пор ставит многих в тупик. 12 монет и 3 взвешивания
Где искать репетитора ребенку и как развить у него логику и нестандартное мышление
Тот самый случай, когда двоечник получает правильный ответ быстрее, но решение неверное
