Гномы нашли клад из 239 монет. Известно, что в кладе есть две монеты, отличающиеся по...

Question

Гномы нашли клад из 239 монет. Известно, что в кладе есть две монеты, отличающиеся по весу
от других. Если эти две монеты легче остальных - то они фальшивка; если тяжелее – то это
волшебные неразменные монеты. Минимальное количество взвешиваний на двучашечных весах
без гирь, за которое можно определить, фальшивка или волшебные неразменные монеты в кладе
(сами монеты находить ненужно, т.е. нужно только выяснить – 2 монеты легче или тяжелее, чем
остальные 237):
1 3 взвешивания 2 39 взвешиваний 3 119 взвешиваний

Answer 1

3 взвешивания достаточно.

Одну монету откладываем в сторону. Оставшиеся разделяем на две кучки по 119 монет и взвешиваем в первый раз. Если чаши в равновесии, то берем одну кучку и присоединяем к ней монету, которую отложили, делим образовавшуюся кучку пополам - по 60 монет - и взвешиваем во второй раз. Если чаши в равновесии, то по одной искомой монете лежит в каждой чаше. Берем одну группу монет, делим пополам и взвешиваем по 30 монет, обнаруживая кучку, которая тяжелее или легче.