ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 103009
Тема:    [ Теория алгоритмов ]
Сложность: 3
Классы: 5,6,7
В корзину
Прислать комментарий

Условие

Имеются 6 запертых чемоданов и 6 ключей к ним. При этом неизвестно, к какому чемодану подходит какой ключ. Какое наименьшее число попыток надо сделать, чтобы наверняка открыть все чемоданы? А сколько понадобится попыток, если ключей и чемоданов будет не по 6, а по 10?

Подсказка

Попробуйте за пять попыток определить, к какому из 6 чемоданов подходит первый ключ.

Решение

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

Источники и прецеденты использования

кружок
Место проведения МЦНМО
класс
Класс 5
год
Год 2004/2005
занятие
Номер 11
задача
Номер 11.3

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .