Могу изложить общий подход при решении подобных задач. Но надо набраться терпения.
Показать скрытый текст 1. За одно взвешивание можно:
1.а Определить фальшивую монету из двух, не зная легче она или тяжелее, если дополнительно есть ещё одна нормальная монета (Н):
Н сравниваем с одной из двух.
- Если равновесие, фальшивая - оставшаяся и мы так и не знаем, легче она или тяжелее (но этого и не требуется)
- Если неравенство, фальшивая - выбранная и мы заодно узнаём, легче она или тяжелее.
1.б Определить фальшивую монету из трёх (1,2,3), если:
а)известно, что она либо более тяжелaя в группе Г2{1,2} из двух (1,2) или более легкая - Г1{3}
б)известно, что она наоборот, более лёгкая в группе Г2{1,2} из двух (1,2) или более тяжелая Г1{3}.
Это находится следующим образом (допустим - случай а)):
Сравниваются две монеты из Г2{1,2}
В случае равенства - 3-я монета.
В случае неравенства - если если она более тяжёлая в Г2{1,2} - то та, что тяжелее, если более лёгкая - то та, что легче.
Итак, за одно взвешивание можно определить фальшивую либо из двух (1а), либо из 3-х (1б), если есть некая дополнительная информация.
Не удивляйтесь пока такой какой-то странности, вычурности 1б, всё прояснится позже.
Главное, что нельзя за одно взвешивание определить фальшивую из более чем 2-х в случае 1а и более чем 3-х в случае 1б.
Из этого следует, что за 2 взвешивания можно определить одну фальшивую из 5, если неизвестно легче она или тяжелее и есть одна нормальная:
Делим эти 5 монет на 2 группы: Г3{1,2,3} и Г2{4,5}
1-е взвешивание: Н,1 сравниваем с 2,3.
Если равенство - фальшивая в Г2{4,5} и имеем случай 1а, решаемый за одно взвешивание
Если неравенство - фальшивая в Г3{1,2,3} и имеем случай 1б, решаемый тоже за одно взвешивание.
Итак, введём обозначения: макс. число монет как функция от числа взвешиваний:
М1(1) = 2, М2(1) = 3 = 2*М1(1)-1
М(2) = 5 = М1(1) + М2(1) = 3*М1(1) - 1.
Учитывая это, можно предположить, что за 3 взвешивания можно определить:
М(3) = 3*М(2) - 1 = 14.
Ниже я показываю стратегию для 14.
Разбиваем на 2 группы: Г9{1,2,...,8,9} и Г5{10,11,...,14}
1-е взвешивание: Н,1,2,3,4 и 5,6,7,8,9
При равенстве (лёгкий случай) - два взвешивания для 5 -> уже проходили.
При неравенстве (Фальшивая в Г9, а в Г5 все нормальные)
2-взвешивание: Н,10,11,...,14 и 1,2,3,5,6,7
Если Н,10,...,14 легче -> фальшивая в 5,6,7 и она тяжелее -> 1 взвешивание
Если Н,10,...,14 тяжелее -> фальшивая в 1,2,3 и она легче -> 1 взвешивание
При равенстве -> фальшивая либо 4(лёгкая), либо одна из [8,9], тяжёлая. Это случай 1б -> 1 взвешивание.
По аналогии 1 фальшивая среди 3*14 - 1 = 41 монет определяется 4-мя взвешиваниями. Здесь группы Г27 и Г14
Для 5 взвешиваний -> 41*3-1 = 122 монеты (Г81 и Г41)
Можно увидеть рекуррентную зависимость: М(К+1) = 3*М(К)-1 = 3К + М(К)
