Question

У Снусмумрика есть 2020 одинаковых на вид шариков. Один из них отличается по весу от остальных. Снусмумрик на чашечных весах без гирь хочет гарантировано определить легче или тяжелее особенный шарик за несколько взвешиваний. Сам шарик Снусмумрик находить не требует. За какое наименьшее количество взвешиваний это можно гарантировано определить?

Answer 1

Разделим все шарики на две группы, в каждой по 1010 шариков.

На одну вашу весов положим первую группу, на вторую чашу – вторую группу.

Одна из чаш опустится, другая поднимится, поскольку в одной из групп есть шарик, отличающийся по весу.

Теперь, не смешивая эти группы, освободи весы. Разделим ту группу шариков, которая оказалась легче ещё на две группы по 505 шариков.

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

Ответ: за 2 взвешивания.

Answer 2

Для решения этой задачи можно воспользоваться методом деления множества на части. Для того чтобы гарантировано определить легчий или тяжелый шарик среди 2020 одинаковых на вид шариков, понадобится 3 взвешивания.

Вот как это делается:

1. Разделите 2020 шариков на три группы по 673 шарика в каждой (или ближайшее целое число, чтобы разделить поровну).

2. Взвесьте первые две группы по 673 шарика каждая на чашечных весах.

   a. Если весы сбалансированы, это означает, что "особенный" шарик находится в третьей группе из 673 шариков. Теперь у нас есть 673 шарика, среди которых нужно найти легчий или тяжелый.

   b. Если весы не сбалансированы, то одна из групп весит больше. Это означает, что "особенный" шарик находится в одной из первых двух групп по 673 шарика. Теперь у нас есть 673 шарика, среди которых нужно найти легчий или тяжелый.

3. Разделите 673 шарика на 3 группы по 224 шарика в каждой (или ближайшее целое число).

4. Взвесьте первые две группы по 224 шарика каждая на чашечных весах.

   a. Если весы сбалансированы, это означает, что "особенный" шарик находится в третьей группе из 224 шариков. Теперь у нас есть 224 шарика, среди которых нужно найти легчий или тяжелый.

   b. Если весы не сбалансированы, то одна из групп весит больше. Это означает, что "особенный" шарик находится в одной из первых двух групп по 224 шарика. Теперь у нас есть 224 шарика, среди которых нужно найти легчий или тяжелый.

5. Повторите процедуру разделения и взвешивания ещё один раз для оставшихся 224 шариков, разделив их на 3 группы по 74 шарика в каждой.

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

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