воскресенье, 25 сентября 2011 г.

Задача про монеты

Имеется 12 монет, среди которых ровно одна фальшивая (неизвестно какая). Все настоящие монеты одного веса, а фальшивая легче или тяжелее. На чашечных весах можно сравнивать по весу любые две группы монет. Нужно найти фальшивую монету и выяснить, легче она или тяжелее. Сколько взвешиваний для этого достаточно?

Придумал алгоритм для решение этой задачи для произвольного числа монет. Получились следующие цифры:

  • 3 монеты → 2 взвешивания
  • 4 монеты → 3 взвешивания
  • 13 монет → 4 взвешивания
  • 40 → 5
  • 121 → 6

Напрашивается естественная закономерность:

число взвешиваний = Ceiling[Log[3, 2×число монет + 2]].


А в прошлый раз мне эта задача не поддалась.

Комментариев нет: