Question

В мешке находятся 294 монеты, из которых одна фальшивая, которая легче остальных. Имеются рычажные весы без гирь. Найдите наименьшее количество взвешиваний на рычажных весах для того, чтобы найти фальшивую монету?

Answer 1

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 либо две монеты.. две взвешиваешь и понимаешь какая из трех.. либо если осталось две монеты.. на весах понятно какая фальшивая

Answer 2

Ответ:

Действительно, самый быстрый путь это делить на 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%).

Answer 3

Для решения этой задачи можно использовать стратегию деления на две равные части.

1. Разделим 294 монеты на две равные группы по 147 монет в каждой. Положим одну группу в одну чашу весов, а другую группу в другую чашу весов.

2. Если весы сбалансированы и не наклоняются ни вправо, ни влево, то фальшивая монета находится вне рассматриваемых 294 монет. В этом случае осталось всего одно взвешивание, чтобы определить фальшивую монету: положить любые две монеты на весы, и если они имеют разный вес, то фальшивая монета будет легче из них.

3. Если весы наклонились влево или вправо, то фальшивая монета находится в одной из рассматриваемых групп по 147 монет. Отбросим оставшиеся 147 монет и возьмем группу, в которой находится фальшивая монета.

4. Разделим эту группу по 147 монет на две равные подгруппы по 73 монеты. Положим одну подгруппу на одну чашу весов, а другую подгруппу на другую чашу весов.

5. Далее использовать аналогичную стратегию, как в пунктах 2-4, чтобы найти фальшивую монету. Продолжаем делить оставшуюся группу до нахождения одной фальшивой монеты.

Таким образом, наименьшее количество взвешиваний на рычажных весах для того, чтобы найти фальшивую монету, составляет 3.