Процессы и алгоритмы

Пример. Пронумеруем коробочки числами от до Первыми семью вопросами узнаем про коробочки Если была найдена тройка коробочек, в которой лежит монетка, то оставим из этой тройки только две, добавив третью, заведомо пустую коробку (например, из другой тройки). Если при такой проверке Гриша получит тройку без монетки, то монетка была в третьей коробоке из тройки. Если монетка по-прежнему присутствует, то из пары коробочек оставим одну, дополнив двумя пустыми коробочками. Монетка будет определена. Если же монетки не оказалось ни в одной из коробок с номерами то на восьмой раз Гриша указывает коробочки Тогда монетка будет или в паре или в паре Последним, девятым ходом, Гриша указывает и находит монетку.

Оценка. Меньше, чем за ходов Гриша не найдет монетку. Если за ходов он укажет суммарно меньше, чем на коробочки, то не сможет узнать, в какой из оставшихся монетка, если она там окажется. Если он укажет на то каждый раз — на три новых коробочки. Если монетка будет в последней тройке, то Гриша ее не найдет.