Найди фальшивый камень с помощью весов,сделай как можно меньше взвешиваний

Классическая задача о поиске фальшивой монеты (или камня) решается с помощью алгоритма троичного поиска. Количество необходимых взвешиваний напрямую зависит от общего количества камней. Ниже приведено решение для стандартного сценария: у вас есть 12 камней, один из которых фальшивый (он может быть как легче, так и тяжелее настоящих), и вам нужно найти его за 3 взвешивания. Алгоритм решения (для 12 камней) Разделим камни на три группы по четыре: А (1, 2, 3, 4), Б (5, 6, 7, 8) и В (9, 10, 11, 12). Взвешивание №1 Положите группу А на левую чашу, а группу Б — на правую. Вариант 1: Весы в равновесии. Значит, фальшивый камень находится в группе В (9, 10, 11, 12). Все камни в А и Б — настоящие.

• Взвешивание №2: Сравните три настоящих камня (1, 2, 3) с камнями (9, 10, 11).
  • Равновесие: Фальшивка — камень 12. Взвесьте его с любым настоящим, чтобы узнать, легче он или тяжелее.
  • Неравенство: Теперь вы знаете, в какой тройке фальшивка и тяжелее она или легче (в зависимости от наклона весов).
• Взвешивание №3: Сравните камень 9 и 10. Если они равны — фальшивка 11. Если нет — фальшивка та, что соответствует результату 2-го взвешивания.

Вариант 2: Весы не в равновесии (А > Б). Это значит, что либо в А есть тяжелый камень, либо в Б — легкий. Группа В полностью состоит из настоящих камней.

• Взвешивание №2: Положите на левую чашу (1, 2, 5) и на правую (3, 4, 6). Оставшиеся камни: 7, 8.
  • Равновесие: Фальшивка среди 7 или 8. Так как в первом взвешивании группа Б была легче, сравните 7 и 8. Тот, что легче — фальшивый.
  • Левая чаша тяжелее (1, 2, 5 > 3, 4, 6): Либо 1 или 2 тяжелые, либо 6 легкий (так как 5 перешла на сторону «тяжелых», а 6 — на сторону «легких»).
  • Правая чаша тяжелее (1, 2, 5 < 3, 4, 6): Либо 3 или 4 тяжелые, либо 5 легкий.
• Взвешивание №3: Исходя из результата, сравните два подозрительных камня между собой.

Общая формула Минимальное количество взвешиваний $n$ для поиска одной фальшивой монеты (если известно, что она отличается по весу, но не известно как) среди $N$ камней определяется неравенством: $3^n\ge 2N+3$

Как минимизировать процесс

1. Деление на три: Всегда старайтесь делить общее количество камней на 3 максимально равные группы.
2. Использование эталона: Как только вы определили группу, в которой нет фальшивки, используйте эти камни как «гири» для проверки подозрительных экземпляров.
3. Информативность: Каждое взвешивание должно иметь 3 возможных исхода (лево, право, равновесие). Если какой-то исход невозможен, алгоритм не оптимален.

Хотите, чтобы я рассчитал пошаговый алгоритм для конкретного количества камней (например, для 27, 81 или 100)?