Задача 103009
|
|
 |
Условие
Имеются 6 запертых чемоданов и 6 ключей к ним. При этом неизвестно, к какому чемодану подходит какой ключ. Какое наименьшее число попыток надо сделать, чтобы наверняка открыть все чемоданы? А сколько понадобится попыток, если ключей и чемоданов будет не по 6, а по 10?Подсказка
Попробуйте за пять попыток определить, к какому из 6 чемоданов подходит первый ключ.Решение
Стандартное неверное решение: «Каждый из шести чемоданов пытаемся открыть каждым из шести ключей, всего попыток 6 · 6 = 36». Можно найти соответствие между ключами и чемоданами за меньшее число попыток.Берем первый ключ и по очереди пытаемся открыть им чемоданы. Если один из чемоданов открылся — прекрасно, отставляем в сторону этот чемодан с этим ключом. Если же среди первых 5 чемоданов ни один не открылся, то значит, этот ключ непременно соответствует шестому чемодану. Что произошло? Мы использовали не более пяти попыток; у нас осталось 5 ключей и 5 чемоданов.
Снова берем один ключ и открываем все чемоданы подряд. Для того чтобы определить, какому чемодану соответствует этот ключ, нужно четыре попытки. И так далее. Всего понадобится 5 + 4 + 3 + 2 + 1 = 15 попыток. А если бы чемоданов было 10, число попыток было бы 9 + 8 + … + 2 + 1 = 45.
Доказательство того, что меньшим количеством попыток не обойтись, можно прочитать в статье «Сто замков и сто ключей» в журнале Квантик №1(2023).
