Question

К пяти разным замкам есть пять ключей,причём неизвестно,какой ключ к какому замку подходит.Барон Мюнхаузен утверждает,что можно не более чем за десять попыток подобрать ключ к каждому замку.Прав ли барон Мюнхаузен и почему?

Answer 1

Он не прав!!!
Отметим замки цифрами 1) 2) 3) 4) 5)
   Ключи: 1 2 3 4 5
Будет с первым ключом 5 попыток 1) 2) 3) 4) 5)
с вторым ключом уже 4 попытки т.к. 1 замок занят первый ключом
1) 2) 3) 4)
и так до 1 ключа
Вот начнём с первого ключа
1) 2) 3) 4) 5) - ключ 1
1) 2) 3) 4) - ключ 2
1) 2) 3) - ключ 3
1) 2) - ключ 2
1) - ключ 1

Answer 2

Барон Мюнхаузен неправильно рассуждает, и это невозможно. Поясним, почему это так.

Если бы вы попробовали открыть первый замок первым ключом, второй замок вторым ключом, и т.д., то вам бы потребовалось 5 попыток, чтобы опробовать все ключи на первом замке, и еще 5 попыток, чтобы опробовать все ключи на втором замке, и так далее, всего 25 попыток на все замки.

Однако, существует более эффективный способ, чтобы использовать меньшее количество попыток. Предположим, что мы используем первый ключ для открытия первого замка. Затем мы используем этот же ключ, чтобы открыть второй замок, третий замок и т.д., пока ключ не сработает и мы не откроем замок. Это потребует наихудшем случае 4 попыток: одну попытку, чтобы найти работающий ключ для первого замка, и затем 3 попытки, чтобы использовать этот ключ на оставшихся замках.

Однако этот метод не гарантирует, что мы найдем правильный ключ для каждого замка за 10 попыток, потому что нам может понадобиться использовать разные ключи для каждого замка. Например, если мы используем первый ключ для открытия первого замка, но он не работает для второго замка, то мы потратили одну попытку, но нам все еще нужно попробовать оставшиеся 4 ключа на втором замке. Поэтому, в худшем случае, нам могут понадобиться до 20 попыток, чтобы найти правильный ключ для каждого замка.