Взвешивания и количество информации

Каждый раз весы показывают либо равенство, либо что первая чаша легче, либо что вторая чаша легче, а значит за два взвешивания мы получим максимум различных последовательностей ответов. Возможных вариантов, когда три рядом лежащие монеты фальшивые, — 20. Если мы сделали всего два взвешивания, то не получится однозначного соответствия возможных исходов и последовательностей ответов, значит, за 2 гарантированно определить фальшивые монеты не получится.

За три взвешивания— возможно.

Лемма: За взвешивание можно найти три фальшивые среди пяти подряд идущих монет. Доказательство: Пусть монеты Взвесим и Если весы показали равенство, то фальшивые Если тяжелее ( тяжелее аналогично), то фальшивые Таким образом, лемма доказана.

Пронумеруем монеты от до Первое взвешивание: монеты на первой чаше, а на второй.

Если весы показали равенство, то значит среди и монет нет фальшивых. Вторым действием: на первой чаше, а на второй. Равенства в таком случае быть не может. Одна чаша тяжелее, там и находятся все три фальшивые монеты. Наша задача за действие найти среди пяти подряд идущих монет три фальшивые, мы это умеем по лемме.

Если весы показали, что тяжелее ( тяжелее аналогично), то значит среди находятся все три фальшивые монеты. Вторым действием: взвесим и Если весы показали равенство — фальшивая тройка полностью содержится среди умеем находить за 1 действие по лемме. Если тяжелее, то все три фальшивые монеты находятся среди умеем находить за действие по лемме. Если тяжелее, то все три фальшивые монеты находятся среди умеем находить за действие по лемме.