Question

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

Answer 1

Разобьём камни на N пар по 2 камня и взвесим. Тяжёлый камень из пары отложим в одну кучку, а лёгкий - в другую (N взвешиваний). Взвесим любые два камня из кучки с лёгкими камнями, тяжёлый камень отбросим, а лёгкий оставим (с кучкой тяжёлых камней так же, но отбрасываем лёгкий камень, по N - 1 взвешиваний на каждую кучку). Оставшиеся два камня - самый тяжёлый и самый лёгкий.