Дано: 32 камня, попарно различных масс.
Найти: Доказать, что за 35 взвешиваний на чашечных весах без гирь можно определить самый тяжёлый и второй по массе камни.
Решение:
1. Построим дерево сравнения, в котором каждый камень сравнивается с другим камнем для нахождения самого тяжёлого и второго по массе.
2. Для поиска самого тяжёлого камня используем метод турнира:
- На первом этапе сравниваем камни попарно, что требует 16 взвешиваний (32 камня / 2).
- На втором этапе сравниваем победителей предыдущего этапа, что требует 8 взвешиваний (16 камней / 2).
- На третьем этапе снова сравниваем победителей, что требует 4 взвешивания (8 камней / 2).
- На четвёртом этапе снова сравниваем победителей, что требует 2 взвешивания (4 камня / 2).
- На последнем этапе сравниваем двух оставшихся камней, что требует 1 взвешивания (2 камня / 2).
Итак, для нахождения самого тяжёлого камня нужно 16 + 8 + 4 + 2 + 1 = 31 взвешивание.
3. После нахождения самого тяжёлого камня нам нужно найти второй по массе камень. Этот камень должен быть тем, который проиграл самому тяжёлому на любом из этапов турнира. Существует максимальное количество камней, которые могли быть побеждены этим камнем — 5 (в каждом этапе по 1 камню).
4. Для нахождения второго по массе камня из этих 5 камней нам нужно провести дополнительные взвешивания. Мы можем сделать это, используя метод сравнения:
- Сравниваем 5 камней попарно, что требует 4 взвешиваний.
Таким образом, для нахождения второго по массе камня потребуется 4 взвешивания.
Итак, общее количество взвешиваний: 31 (для нахождения самого тяжёлого) + 4 (для нахождения второго по массе) = 35 взвешиваний.
Ответ: Для нахождения самого тяжёлого и второго по массе камней требуется не более 35 взвешиваний.