XXXIV Турнир Городов

[Ktina]

DjD USB в сообщении #633128 писал(а):

Про монеты в 11 классе, как решить? Какой подход, идея?

У меня решение отличается от официального, поэтому, пожалуйста, проверьте на ошибки.

Итак, вешаем 119 и 119, одну оставляем (покамест) в сторонке.

а Если равновесие, берём одну из кучек в 119 и добавляем ту монетку, что оставили в сторонке. Получаем 120 и вешаем 60 и 60. Равновесие теперь невозможно, одна обязательно перетянет. Делим ту, что перетянула, на 2 кучки и вешаем 30 и 30. Если равно, фальшивая легче, если не равно -- тяжелее.

б Если одна кучка перетянула, добавляем к ней ту монетку, что оставили в сторонке.
Получаем 120 и вешаем 60 и 60.

б1 Если равновесие, делим одну из кучек на 2 кучки и вешаем 30 и 30. Если опять равновесие, фальшивая легче. Если нет, тяжелее.

б2 Если одна из кучек в 60 перетянула, берём ту, что не перетянула, делим на 2 и вешаем 30 и 30. Если равновесие, фальшивая тяжелее, если нет -- легче.

[Shadow]

У Вас правильное решение, Ktina.

[hippie]

Ещё одно решение задачи о 239 монетах.


Делим монеты на 3 кучки по 40 монет и одну 119 монет.
За 2 взвешивания сравниваем кучки по 40 (могут быть либо все 3 равного веса; либо 2 равных, а третья отличается).

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

Аналогично, если 2 одинаковых кучки тяжелее третьей.
Только теперь если полукучки весят поровну, то фальшивая легче, а если нет, то тяжелее.

Если все 3 кучки по 40 монет равного веса, то обе фальшивые монеты среди оставшихся 119.
Объединяем 40+40+40=120, откладываем одну монету и сравниваем с оставшимися 119.