Question

как за 3N-2 взвешиваний найти самый лёгкий и самый тяжёлый камни из 2N камней , любые два из которых отличаются по весу? все взвешивания производятся на двухчашечных весах без гирь.

Answer 1

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

Answer 2

Для решения этой задачи с помощью 3N-2 взвешиваний, следует следующий алгоритм:

1. Разделим 2N камней на две равные группы по N камней в каждой (пусть это будут группы A и B).

2. Взвесим группы A и B на весах.

   2.1. Если весы сбалансированы, это означает, что самый легкий и самый тяжелый камни обязательно находятся в группе C (оставшиеся N камней).

   2.2. Если весы несбалансированы, предположим, что группа A была легче группы B (если наоборот, то рассуждения аналогичны).

3. Разделим группу A на две равные части по N/2 камней в каждой (пусть это будут группы D и E).

4. Проведем взвешивание групп D и E на весах.

   4.1. Если весы сбалансированы, самый легкий и самый тяжелый камни находятся в группе B (группа C исключается из дальнейших рассмотрений).

   4.2. Если весы несбалансированы, предположим, что группа D была легче группы E.

5. Теперь у нас есть две группы, содержащие N/2 камней каждая: D (содержащая легкие камни) и B (содержащая тяжелые камни).

6. Разделим группу D на две равные части по N/4 камней в каждой (пусть это будут группы F и G).

7. Проведем взвешивание групп F и G на весах.

   7.1. Если весы сбалансированы, самый легкий камень находится в группе E, а самый тяжелый камень находится в группе G.

   7.2. Если весы несбалансированы, предположим, что группа F содержит легкий камень.

8. Теперь у нас есть три группы: E (содержащая самый легкий камень), G (содержащая самый тяжелый камень) и B (содержащая оставшиеся N/2 камней).

9. Проведем взвешивание группы B с самым легким камнем из группы E.

   9.1. Если весы сбалансированы, самый легкий камень находится в группе E.

   9.2. Если весы несбалансированы, самый легкий камень находится в группе B.

10. Проведем взвешивание группы B с самым тяжелым камнем из группы G.

    10.1. Если весы сбалансированы, самый тяжелый камень находится в группе G.

    10.2. Если весы несбалансированы, самый тяжелый камень находится в группе B.

Таким образом, с помощью 3N-2 взвешиваний мы можем определить самый легкий и самый тяжелый камни из 2N камней.