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

Letuchaya

8

Чтобы решить данную задачу, мы можем использовать подход, основанный на двоичном кодировании. Давайте разделим монеты на две группы равного размера: первую группу обозначим как "A", а вторую группу - как "B". Предположим, что среди этих двух групп фальшивых монет нет.

1. Первое взвешивание:
- Положим 8 монет в каждую чашу весов.
- Если чаша с группой "A" легче, то одна из 8 монет в чаше - фальшивая. Обозначим эту группу как "A1".
- Если чаша с группой "B" легче, то аналогично в одной из 8 монет она содержится. Обозначим эту группу как "B1".
- Если чаши равны по весу, значит, все монеты настоящие, и мы завершаем процесс взвешивания.

2. Второе взвешивание:
- Возьмем группу "A1" (если в первом взвешивании чаша "A" была легче) и расположим по 4 монеты в каждой чаше весов.
- Если одна из чаш весов легче, то одна из 4 монет в этой чаше фальшивая. Обозначим эту группу как "A2".
- Если чаши равны по весу, значит, все монеты "A1" - настоящие, а фальшивые монеты находятся в группе "B1". В этом случае переходим к третьему взвешиванию.

3. Третье взвешивание:
- Берем 4 монеты из группы "B1" и располагаем по 2 монеты в каждой чаше весов.
- Если одна из чаш весов легче, то одна из 2 монет в этой чаше фальшивая. Обозначим эту группу как "B2".
- Если чаши равны по весу, значит, все монеты в группе "B1" - настоящие, а фальшивые монеты находятся в группе "A2".

4. Четвертое взвешивание:
- Берем 2 монеты из группы "B2" (если в третьем взвешивании чаша "B" была легче) и располагаем по 1 монете в каждой чаше весов.
- Если одна из чаш весов легче, то эта монета является фальшивой.
- Если чаши равны по весу, то оставшаяся монета в группе "B2" является фальшивой.

Таким образом, минимальное число взвешиваний для определения всех фальшивых монет из 16 монет составляет 4.