Выбрано 2 задачи 
Убрать все задачи
Даны два набора чисел: a1, ..., an и b1, ..., bn. Расположим числа ak в возрастающем порядке, а числа bk – в убывающем порядке. Получатся наборы
A1 ≤ ... ≤ An, B1 ≥ ... ≥ Bn. Доказать, что max{a1 + b1, ..., an + bn} ≥ max{A1 + B1, ..., An + Bn}.
РешениеСемь лыжников с номерами 1, 2, ... , 7 ушли со старта по очереди и прошли дистанцию – каждый со своей постоянной скоростью. Оказалось, что каждый лыжник ровно дважды участвовал в обгонах. (В каждом обгоне участвуют ровно два лыжника – тот, кто обгоняет, и тот, кого обгоняют.) По окончании забега должен быть составлен протокол, состоящий из номеров лыжников в порядке финиширования. Докажите, что в забеге с описанными свойствами может получиться не более двух различных протоколов.
Решение
|
|
 |
Условие
Имеются 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).
