Занимательная задача про взвешивание монет

Ютуб подсунул ролик со следующей задачей (предлагалась в качестве вступительной для поступающих в 8-й класс с профильной математикой 179-й школы Москвы).

У нас есть чашечные весы без гирь и 99 монет, расположенных в ряд. Известно, что среди этих монет 74 настоящие (которые весят одинаково) и 25 фальшивых (которые весят меньше настоящих). Причём все фальшивые монеты расположены подряд в общем ряду. За какое минимальное число взвешиваний мы можем гарантировано найти хотя бы одну фальшивую монету?

Вторая версия той же задачи, но у нас всего 100 монет, из которых 75 настоящих.

Надо не только указать способ, но и доказать, что он минимален.

searcher
В 1 случае за 1 взвешивание можно
Во 2 за 2, но не знаю пока как доказать, что за 1 нельзя

Правильно.

Вот это самое трудное.

Это как?

ivashenko
Взвесить 25 и 50 монеты, если одна меньше, то она фальшивая, если равны, то фальшивая 75

Да, действительно.

При 100 монетах как и в первом случае всегда могут попасться одинсковые монеты, какие бы мы монеты ни взяли. Если мы возьмем монеты с расстоянием ближе чем 26, то могут попасться как разные монеты( и этот случай неинтересен) так и одинаковые фальшивые или одинаковые настоящие и, соответственно нам придется делать дополнительное взвешивание, чтобы определить фальшивые они или настоящие, поэтому имеет смысл рассматривать только монеты расстояние между которыми не менее 26. Но если мы возьмем монеты расстояние между которыми не менее 26, при этом могут попасться либо фальшивая и настоящая, либо обе настоящие. Первый случай удовлетворяет условию отыскания фальшивки в 1 ход, поэтому его опустим. Остается случай, когда мы выбираем монеты на расстоянии не менее 26 и обе они настоящие. Если мы возьмем интервал более 26 монет, так, что левее и правее от этих монет останется не более чем по 24 монеты, то фальшивые монеты окажутся внутри этого интервала среди не менее чем 52-х монет для выявления фальшивой среди них понадобится доп взвешивание. Если по краям интервала более чем из 26 монет оставим не менее 25 монет, то фальшивые могут оказаться как внутри, так и снаружи этого интервала и нам обязательно понадобятся взвешивания, чтобы определить где находятся эти монеты. Поэтому необходимо рассматривать только случай, когда берется ровно 26 монет подряд и взвешиваются крайние из них. Только в этом случае мы можем допустить нахождение фальшивой монеты в 1 взвешивание. Теперь мы берем 26 монет подряд так, что левая из них будет правее 25 монеты, а правая левее 76. Фальшивые могут оказаться как справа от этих 26 монет так и слева и для их выявления понадобится взвешивание. Поэтому, чтобы дополнительного взвешивания не потребовалось нам необходимо расположить наши 26 настоящих монет так, чтобы с одной стороны от них оказалось менее 25 монет. Т.е. оказалось 0-24 монеты, соответственно фальшивые монеты окажутся с другой стороны среди 50-74 оставшихся монет. Минимум 50 со второй стороны, среди которых мы не можем однозначно определить фальшивые без доп взвешивание. Вот если бы со второй стороны было не 50, а 49(т.е. всего 99 монет), то мы могли бы сказать, что средняя из них фальшивая. А так всегда потребуется доп взвешивание.

Это невозможно сделать. Если во втором случае откинуть одну монету скраю, и она с большей вероятностью окажется настоящей, тогда получится первый случай, который решается за одно взвешивание. Значит, минимально одно взвешивание возможно, и нельзя ни опровергнуть, ни доказать.

Вообще, по-моему, задача сводится к следующему: всегда отбросим с обоих краёв ряда по 24 монеты. В первом случае останется 51 монета, во втором 52 монеты, среди которых, по крайней мере, одна фальшивая с интервалом 25.

3axap
Ты таблетки принять забыл? Санитаров позвать?