Как при помощи одного взвешивания найти

Десять мешков

Имеется 10 мешков монет. В одном мешке все монеты фальшивые.

Подлинная монета весит 10 грамм, а Фальшивая монета весит 9 грамм. Как при помощи одного взвешивания на весах с делениями определить мешок с фальшивыми монетами?

Решение

Для начала надо пронумеровать все мешки от 1 до 10, далее необходимо взять из каждого мешка столько монет, сколько составляет его порядковый номер (от 1 до 10). Если бы все монеты были настоящие, то куча монет бы весила 550 грамм (1 + 2 + 3 … + 10) * 10 = 550. Если мешок с фальшивыми монетами имеет номер N (N = от 1 до 10), то взятые из мешков монеты будут весить на N граммов меньше, следовательно, взятая куча монет будет весить меньше на N грамм. Т.е. на сколько грамм куча по весу отличается от 550 грамм, такой по счету мешок содержит фальшивые монеты.

Восемь мешков

У вас имеется 8 мешков с монетами, по 48 монет в каждом. В пяти мешках настоящие монеты, а в остальных – фальшивые. Фальшивые монеты на 1 грамм легче настоящих. С помощью одного взвешивания на точных весах определите все мешки с фальшивыми монетами, используя минимальное количество монет.

Решение

Из первого мешка монет доставать не надо (0), из второго мешка необходимо достать одну монету (1), из третьего две (2), четвёртого – четыре (4), пятого – семь (7), шестого – тринадцать (13), седьмого – двадцать четыре (24), восьмого – сорок четыре (44). Каждые три «кучки» монет, взятые вместе, уникальны в том плане, что дают определённый точный вес, позволяющий определить мешки с фальшивыми монетами (всего используется 95 монет). Если все монеты в предложенном решении были бы настоящими, то их суммарный вес был бы 95 у.е. (0+1+2+4+7+13+24+44). Сравните показание весов с тем, которое было бы в идеале, если бы все монеты были бы настоящими. Полученная разница (число условных единиц) укажет на номера мешков с фальшивыми монетами. Например, если разница составит 21, то фальшивые монеты во втором, пятом и шестом мешках, т.к. именно из них мы взяли 21 монету (1+7+13).

Новогодние шары

На новогодней ёлке висят три пары шаров: два белых, два голубых и два красных. Внешне шары одинаковые. Однако в каждой паре есть один лёгкий и один тяжёлый шар. Все лёгкие шары весят между собой одинаково, и так же все тяжёлые шары. С помощью двух взвешиваний на чашечных весах определите все лёгкие и все тяжёлые шары.

Решение

Положите один красный и один белый шар на левую чашу весов, а на правую чашу один синий и второй белый шар. Если достигнуто равновесие, то очевидно, что на каждой чаше есть один тяжёлый и один лёгкий шар. Поэтому достаточно сравнить два белых шара, чтобы узнать ответ на интересующий нас вопрос. Однако если после первого взвешивания равновесие не достигнуто, то на той стороне, что тяжелее, лежит тяжёлый белый шар. Следующим логическим шагом будет сравнение веса уже взвешенного красного шара и еще не взвешенного синего шара. После этого Вам будет ясно, какие шары лёгкие, а какие тяжёлые.

Девять мешков

Имеется девять мешков: восемь с песком и один с золотом. Мешок с золотом немного тяжелее. Вам даётся два взвешивания на чашечных весах, чтобы найти мешок с золотом.

Решение

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

27 теннисных мячей

Имеется 27 теннисных мячей. 26 весят одинаково, а 27-й немного тяжелее. Какое минимальное количество взвешиваний на чашечных весах гарантирует нахождение тяжёлого мячика?

Решение

Достаточно воспользоваться весами три раза. Разделите 27 мячей на 3 группы, по 9 мячей в каждой. Сравните две группы – тяжелый мячик окажется в той группе, которая перевесит. Если весы достигли равновесия, то тяжёлый мячик в третьей группе. Таким образом, мы определим группу из 9 мячиков, один из которых искомый. Поделите эту группу на 3 подгруппы, по три мячика в каждой. Аналогично первому шагу сравните вес двух любых подгрупп. Теперь сравните два мячика (два из трех, среди которых точно должен быть искомый).

Расколотая гиря

Купец уронил 40-фунтовую гирю, и она раскололась на 4 неравные части. Когда эти части взвесили, то оказалось, что вес каждой из них (в фунтах) – целое число. Более того, с помощью этих частей можно было взвесить на чашечных весах любой вес (представляющий собой целое число) до 40 фунтов. Сколько весила каждая часть?

Решение

Осколки весили: 1 фунт, 3 фунта, 9 фунтов и 27 фунтов, что в сумме дает 40 фунтов.

Гвозди в мешке

В мешке 24 кг гвоздей. Каким образом можно на чашечных весах без гирь отмерить 9 кг гвоздей?

Решение

Один из вариантов: разделите 24 кг на две равные части по 12 кг, уравновесив их на чашах весов. Затем так же разделить 12 кг на две равные части по 6 кг. После этого отложить одну часть, а другую разделить таким же способом на части по 3 кг. Наконец к шестикилограммовой части добавьте эти 3 кг. В результате получится 9 кг гвоздей.

Время на прочтение
3 мин

Количество просмотров 204K

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

Наиболее распространенные из таких задач — определение количества взвешиваний для выявления фальшивой монеты, если:

1) неизвестно какая она по весу;
2) известно, что она легче/тяжелее остальных.

Или обратная задача: можно ли за определенное количество взвешиваний выявить фальшивую из заданного количества монет.

1. Давайте сначала разберемся с 2 вариантом, который является частным случаем варианта 1.

Некоторое время назад, я на Хабре уже описывал решение такой задачи, но в одном из комментариев было замечание о немного странном первом разделении монет, по-этому предлагаю другой алгоритм решения. Хотя результат будет тот же и формула решения задачи остается та же:

N >= log₃A,

где N — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
A — количество монет.
Которая выведена на основании опытов (за 1 взвешивание можно найти одну фальшивую из 3-х монет, за 2 — из 9, за 3 — из 27 и т.д.)

Сам алгоритм решения простой, и я покажу его на примерах

1) Пусть у нас есть 26 монет. Нужно найти одну, которая легче/тяжелее

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

A = 2 * B + C,

где A — количество монет;
B — частное от деления количества монет на 3, натуральное число, округленное в большую сторону;
C — остаток.

По условию задачи

26/3 = 8.666(6),

26 = 2 * 9 + 8,

При первом взвешивании будут сравниваться две группы: правая (ПГ) — 9 монет и левая (ЛГ) — 9 монет.

Далее у нас возможны два варианта:

1) фальшивая монета в левой/правой группе (9 монет)
2) фальшивая монета в остатке (8 монет)

для 1 варианта следующее деление на группы будет — 9 = 2 * 3 + 3;
для 2 варианта — 8 = 2 * 3 + 2

Ну и за одно взвешивание можно определить какая из 2 или 3 монет легче/тяжелее

Этот же результат я приведу в таблице

по формуле — log₃26 =2.9656 — соответственно количество взвешиваний — 3.

еще пример:
число монет- 71. По формуле log₃71 =3.8800 — количество взвешиваний — 4. Проверяем

Ну с алгоритм решения этих задач, я думаю, понятен.

2. Теперь перейдем к задачам, в которых не известно легче монета или тяжелее.

В данном случае я предлагаю такое первое действие: разделить монеты на четыре группы, три — с максимально одинаковым количеством монет, а в четвертой группе — остаток. Причем в остатке должны быть 1 или 2 монеты. То есть при делении на 3 частное округляется до меньшего натурального числа.

A = 3 * B + C,

где A — количество монет;
B — частное от деления количества монет на 3, натуральное число, округленное в меньшую сторону;
C — остаток.

Например, для 58-ми монет — это будет 58 = 3 * 19 + 1, для 23 = 3 * 7 + 2, для 15 = 3 * 5 + 0 и т. д.

Далее выполняем два взвешивания:
1) первая и вторая группы;
2) первая и третья группы;
и анализируем результат.
Здесь возможны четыре варианта:1, 2, 3 — это первая, вторая или третья группа отличаются по весу от двух остальных, или они равны, тогда нам повезло, так как фальшивая — в остатке. Так же два взвешивания помогают определить определить тяжелее фальшивая монета или легче. Кстати, если в остатке две монеты, то нужно выполнить еще 2 взвешивания для определения фальшивой монеты.

Теперь у нас есть задача: определить одну фальшивую монету из группы, которая легче/тяжелее.
Что касается формулы, то она примет следующий вид

N >= log₃B + 2,

где N — максимально необходимое количество взвешиваний, натуральное число;
B — количество монет в группе после второго взвешивания.
А если учесть, что B = A/3, где A — количество всех монет, тогда получим:

log3B = log₃A — 1,

N >= log₃A + 1

Итог:

1) если известно, что фальшивая монета легче/тяжелее, тогда максимальное число взвешиваний определяется по формуле:

N >= log₃A

2) если не известно, какая фальшивая, тогда максимальное число взвешиваний определяется по формуле:

N >= log₃A + 1

где N — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
А — количество монет.

Коля решил украсить новогоднюю ёлку, и повесил на её 3 пары шаров. Первая пара шаров была красного цвета. Вторая пара шаров была белого цвета. Третья пара шаров была чёрного цвета.

В каждой паре шаров, был один лёгкий шар, а другой тяжёлый. При том что, все лёгкие шары между собой весят одинаково. И все чёрные между собой весят одинаково.

Как с помощью двух взвешиваний чашечных весах, определить в каждой паре лёгкие и тяжёлые шары?

Положите первую чашу красный и чёрный шар, а на вторую чашу красный и белый шар.

1. Если чаша уравновесилась, то взвешиваем два красных шара между собой. Таким образом, мы определим, какой из красных шаров весит больше, а какой меньше.
а) Если с первой чаши красный шар оказался легче второго, то это означает, что чёрный шар который взвешивался в первый раз, будет тяжёлым. А белый шар, который находился во второй чаше, будет лёгким. Следовательно белый шар который не взвешивался будет тяжёлым, а чёрный шар который не взвешивался будет лёгким.

2. Если Первая чаша тяжелее, то взвешиваем чёрный и белый шар, которые находились на весах
а) Если чёрный шар на первой чаше тяжелее, это значит, то и белый шар который бил с ним, тоже тяжёлый, иначе бы изначально весы уравновесились.А это значит, что те 2 шара на вторых весах лёгкие. Два не взвешенных шара определяются методом исключения, как и в первом варианте