Дано:
- 81 монета, из которых одна фальшивая, легче остальных.
- Нужно определить, какая монета фальшивая, используя чашечные весы без гирь.
- Определить количество взвешиваний для 80 монет и для произвольного количества n монет.
Найти:
1. Можно ли определить фальшивую монету за четыре взвешивания для 81 монеты?
2. Сколько взвешиваний потребуется для 80 монет?
3. Сколько взвешиваний потребуется для произвольного числа n монет?
Решение:
1. Для 81 монеты:
Разделим монеты на три группы по 27 монет. В первом взвешивании сравниваем две группы по 27 монет. Если они равны, то фальшивая монета находится в оставшейся группе из 27 монет. Если они не равны, то фальшивая монета находится в более легкой группе из 27 монет.
Теперь у нас есть 27 монет. Разделим их на три группы по 9 монет и сравним две группы по 9 монет. Аналогично, если они равны, то фальшивая монета в оставшейся группе из 9 монет. Если они не равны, то фальшивая монета в более легкой группе из 9 монет.
У нас осталось 9 монет. Разделим их на три группы по 3 монеты и сравним две группы по 3 монеты. Если они равны, то фальшивая монета в оставшейся группе из 3 монет. Если они не равны, то фальшивая монета в более легкой группе из 3 монет.
У нас осталось 3 монеты. Сравнив две из них, мы сразу определим, какая из них фальшивая, или если они равны, то фальшивая монета — оставшаяся.
Таким образом, можно определить фальшивую монету за 4 взвешивания.
2. Для 80 монет:
Следует аналогично разделить 80 монет на три группы, однако без остатка, чтобы соответствовать условию деления. Например, 80 можно разделить на группы по 26, 26 и 28, что осложняет процесс. При таком подходе потребуется больше взвешиваний, так как деление не всегда дает равные группы. При оптимальном делении (например, деление на группы 27, 27 и 26) число взвешиваний также может достичь 4, но проверка требует больше времени.
3. Для произвольного числа n монет:
Для нахождения фальшивой монеты требуется log_3(n) взвешиваний. Это число округляется вверх до ближайшего целого. Формула:
k = ceil(log_3(n)).
Например, для n = 81, log_3(81) = 4, что соответствует 4 взвешиваниям.
Ответ:
1. Можно определить фальшивую монету за 4 взвешивания для 81 монеты.
2. Для 80 монет в общем случае может потребоваться больше, чем 4 взвешивания.
3. Для произвольного числа n монет потребуется ceil(log_3(n)) взвешиваний.