В мешке находятся 294 монеты, из которых одна фальшивая, которая легче остальных. Имеются рычажные весы без гирь. Найдите наименьшее количество взвешиваний на рычажных весах для того, чтобы найти фальшивую монету?
Ответы
1) Делишь 80 монет на 3 кучки ( 27+27+26 монет) и одним взвешиванием определяешь где фальшивая..( взвешиваешь 2 кучки по 27монет.. если фальшивая в одной из них.. на весах видно будет.. если весы окажутся в равновесии.. то значит фальшивая в кучке из 26 монет)
2) кучку с фальшивой монетой снова делишь на 3 ( 9+9+9) либо (9+9+8) взвешиваешь две.. и понимаешь в какой из трех кучек фальшивая
3) снова делишь кучку с фальшивой на три..(3+3+3) либо (3+3+2) в зависимости от того в какой была фальшивая из 27 или 26 монет.. снова взвешиваешь две кучки.. и понимаешь в какой из трех фальшивая
4) и наконец.. остается либо 3 либо две монеты.. две взвешиваешь и понимаешь какая из трех.. либо если осталось две монеты.. на весах понятно какая фальшивая
Ответ:
Действительно, самый быстрый путь это делить на 3 кучки, каждый раз, но давайте адаптируем и объясним этот способ.
1) Разделили на 3 кучки по 294/3=98 монет.
Если при взвешивании одна кучка весит меньше - фальшивка в ней, иначе в кучке, которая вне весов.
2) Снова делим на 3. 98/3=33, 33, 32.
Берем кучки 33 и 33 и на весы.
Или останется 33 монеты после взвешивания или 32 (если весы в равновесии)
3) Ecли 33, то делим по 11, если 32, то 11, 11, 10
Останется 11 или 10
4) Снова делим на 3 кучки
или 4, 4, 3 или 3, 3, 4
Останется 3 или 4
5) Делим 1+1+1 или 1+1+2
Останется 1 (решили) или 2 - снова на весы.
6) Взвешиваем последние 2 монеты. Это максимальное количество взвешиваний для этого способа с наименьшим количеством взвешиваний :).
Почему это быстрее, чем делить на 2 кучки? Потому что одним взвешиванием отсекаем 2/3 объема, а не половину, что увеличивает скорость поиска.
Объяснение:
За 6 взвешиваний мы точно найдем фальшивку (гарантировано), а может даже за 5 (вероятнее чем за 6, но вероятность не 100%).