|
|
 |
Условие
Есть трое песочных часов: большие на 5 минут, средние на 3 минуты и маленькие на 2 минуты. Но в одних из них песка чуть больше, чем надо, и он сыплется на несколько секунд дольше, чем положено. Как найти бракованные часы, затратив меньше пяти минут? (Считаем, что на запуск и переворачивание часов время не тратится.)Решение
Рассмотрим следующий алгоритм:1. Запустим одновременно часы на 2 и на 3 минуты.
2. Как только весь песок в часах на 2 минуты будет внизу, перевернём их и одновременно с этим запустим часы на 5 минут.
3. Как только весь песок в часах на 3 минуты будет внизу, перевернём часы на 5 минут (чтобы уже насыпавшийся песок высыпался обратно).
Дальше будем следить, в каких часах песок кончится раньше: в 2-минутных или в 5-минутных.
Пусть мы начали шаг 1 в 00:00.
Если бракованными были часы на 3 минуты, то часы на 5 минут запустятся ровно в 00:02, но перевернём обратно мы их позже, чем в 00:03 (средняя линия на схеме). То есть в начале шага 3 в 2-минутных часах сверху будет песка меньше, чем на минуту, а в 5-минутных снизу — больше, и после переворачивания 5-минутные часы «финишируют» позже, чем 2-минутные (причём 2-минутные закончат ровно в 00:04).
Если бракованными были часы на 2 минуты, то часы на 5 минут запустятся позже, чем в 00:02, то есть до переворачивания их в 00:03 пройдёт меньше одной минуты (нижняя линия на схеме). Значит, после переворачивания песок в них закончится раньше, чем в 2-минутных часах (и раньше, чем в 00:04). Так по результату наблюдений мы поймём, какие часы неисправны, потратив не более 4 минут.
Замечания
Если ограничения по времени нет, можно отмерить 6 минут с помощью маленьких («2») и с помощью средних («3») часов и сравнить результат:«2» + «2» + «2» > «3» + «3» — бракованные 2-минутные часы,
«2» + «2» + «2» < «3» + «3» — бракованные 3-минутные часы,
«2» + «2» + «2» = «3» + «3» — бракованные 5-минутные часы.
Но шести минут у нас нет. Как можно уменьшить это время? Вычтем из обеих частей «2»:
«2» + «2» ? «3» + «3» – «2»
В точности такое сравнение и приведено в решении. Разность «3» – «2» мы «запомнили» на 5-минутных песочных часах.
