Question

Как за 3N – 2 взвешиваний найти самый лёгкий и самый тяжёлый камни из 2N камней, любые два из которых отличаются по весу? Все взвешивания производятся на двухчашечных весах без гирь.

Answer 1

Решение. За N взвешиваний попарно взвешиваем все 2N камней. Те камни, которые оказались тяжелее, складывать в одну кучу, те, которые легче – в другую. В первой куче находится самый тяжёлый камень, его следующим образом: нумеруем камни числами от 1 до N, берём камни 1 и 2, взвешиваем их, выбираем камень с наибольшим весом и сравниваем его вес с камнем 3 и т. д. На N – 1 взвешивании сравнивается вес N-го камня и самого тяжёлого из предыдущих N – 1 камней. Таким образом, самый тяжёлый камень в первой куче гарантированно находим за N – 1 взвешивание. Аналогично находим самый лёгкий камень во второй куче. Всего потребуется N + N – 1 + N – 1 = 3N – 2.