Есть три ключа, три замка и один пессимист, который точно знает, что ничего с первого и даже со второго раза у него не получится. Каждый ключ открывает только одну дверь. Ключи перемешаны и не подписаны — никто не знает, какой ключ от какой двери.
Сколько минимально попыток при наихудшем сценарии потребуется пессимисту, чтобы гарантированно точно подобрать все ключи к дверям?
Теоретически пессимист может сделать так:
взять три ключа и каждым попробовать по очереди открыть каждую дверь. 3 ключа × 3 двери = 9 попыток.
Девять попыток — это очень долго (не забываем, что у нас привычный ко всему пессимист и его этим не испугать), но в решении нас просят найти минимальное количество попыток при плохих раскладах, а девять — слишком много.
Есть вариант побыстрее.
Помним о том, что ничего точно не подойдёт ни с первого, ни со второго раза:
- Взять первый ключ и попробовать им открыть первую дверь.
- Если не открывается — взять второй ключ и открыть им первую дверь.
Если и так не открывается — значит от неё третий ключ. Отлично, прошло 2 попытки, а мы уже нашли один ключ.
Идём дальше, сейчас будет самое интересное.
- Берём второй ключ и пробуем им открыть вторую дверь.
Так как у пессимиста ничего не срабатывает с первого раза, то по закону подлости второй ключ не подойдёт ко второй двери. А это значит, что второй ключ открывает третью дверь.
И у нас остался один непроверенный ключ — третий, а к первой и третьей двери мы ключи уже подобрали. Получается, что третий ключ открывает вторую дверь.
Итого — три попытки. Не так уж плохо для пессимиста.
Бонус для читателей
Если вам интересно погрузиться в мир ИТ и при этом немного сэкономить, держите наш промокод на курсы Практикума. Он даст вам скидку при оплате, поможет с льготной ипотекой и даст безлимит на маркетплейсах. Ладно, окей, это просто скидка, без остального, но хорошая.
Вам слово
Приходите к нам в соцсети поделиться своим мнением о статье и почитать, что пишут другие. А ещё там выходит дополнительный контент, которого нет на сайте — шпаргалки, опросы и разная дурка. В общем, вот тележка, вот ВК — велком!
