ну тут по-моему надо взвесить 49 и 49. в случае если одна из них перевесит все легко. если нет - то в них либо по 1й либо по 2 фальшивых. взвесить 2 из одной из них с 2мя оставшимися вроде так и получается.

В Москве, как выяснилось, трое. Так что, наверное, всё же больше.

берем 5 монет... дальше тривиально...

да, что-то погорячился, неочевидно. Сейчас склоняюсь к невозможности сделать это.

сравниваем две группы по 33, (обозначим их A,B, оставшиеся 34 обозначим С)
если одна из них тяжелее, то в ней не больше 1 фальшивой, сравниваем две монеты из нее, та что не легче другой - настоящая
если они равны по весу
берем монетку x и переносим из A в B
далее сравниваем вес B+x c C
если B+x > C, то x - настоящая
если B+x = C, то все оставшиеся в А настояшие (это возможно только если в C две фальшивых, соответственно в A и B было по одной и как раз х фальшивая)
если B+x < C, то все в C настоящие

Делим монеты на четыре кучи: 1+32+33+34. Первое взвешивание: 1+32<>33. Если нет равновесия, то в тяжелой куче не более одной фальшивой монеты. Берем из нее две монеты, взвешиваем и находим натоящую. В случае равновесия, второе взвешивание: 1+33<>34. В случае равенства все монеты в куче из 32 настоящие; перевесила левая часть в -- куче из 34 монет все настоящие; перевесила правая часть -- в куче из 1 монеты все настоящие))

Делим монеты на 3 части - 33, 33 (кучки) и 34 (куча)

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

Пусть они весят одинаково. Тогда в куче 0, 2 или 4 фальшивые (четвертого не дано).

(2) Берем одну монету из одной кучки (первая) и добавляем ее ко второй кучке (вторая), в которой после этого окажется 34 монеты (новая куча). Взвешиваем новую кучу с начальной кучей (старая).

3 варианта:

а. Старая тяжелее. Тогда в ней, очевидно, нет фальшивых монет. Взяв любую, решим задачу.
б. Весят одинаково. Такое возможно, когда в старой 2 фальшивые и при этом та монета, которую мы "перекладывали" тоже фальшивая. Значит оставшиеся монеты в первой кучке настоящие - решили задачу.
в. Старая легче. Это возможно в двух случаях: в старой 4 фальшивые монеты, тогда берем из новой любую - она настоящая; в старой 2 фальшивые, тогда та монета, которую мы перекладывали обязана быть настоящей. Решили задачу.

Другие решения вообще возможны? (кажется, что нет..)

Да, можно "вскрыть" достоверно аж 14 настоящих монет (это, кажется максимум). Но при этом решение "принципиально" не поменяется (кучки будут по 28 монет, а куча 42).

А вот есть ли "принципиально" другое решение?

Кстати, можно ли доказать, что 14 (или что-то другое?) действительно максимум?

Разделим на три группы А, Б и В по 33,33 и 34 монеты соответственно
Взвесим А и Б. Если одна группа перевесила, то в ней не более 1 фальшивой монеты. Соответственно берем из этой группы любые две и вторым взвешиванием задача решена.
Если группы по весу равны, то берем А + одну монетку из Б и взвешиваем с В. При этом заметим, что в В четное число фальшивых монет.
1.Если весы уравновесились, то в В ровно две фальшивые, в А одна => оставшиеся в Б настоящие.
2.Если В перевесила, то в В не больше одной фальшивой => в В все настоящие.
3.Если В легче, то в В или 4 или 2 фальшивые. В обоих случаях та монета, которую мы взяли из Б
будет настоящей.

Первое взвешивание: по 49 монет на каждую чашку весов (остаются две). Если одна перевесила, в ней не больше одной фальшивой монеты. Берём любые две монеты с этой чашки и сравниваем: более тяжёлая -- настоящая, при равенстве -- настоящие обе.

Если обе группы по 49 монет весят одинаково, значит, в каждой из них по одной или по две фальшивых монеты. (Из четырёх фальшивых монет в число 98 обязательно попадут хотя бы две). Берём с одной из чашек две группы по 24 монеты (остаётся одна монета с этой чашки) и взвешиваем. Группа, которая перевесила -- настоящая вся. Если группы весят одинаково, в каждой из них по одной фальшивой монете, тогда отложенная монета -- настоящая.

(В последнем случае две монеты, отложенные при первом взвешивании, настоящие тоже. То есть, мы всегда можем найти не менее трёх настоящих монет.)

Да, ошибся :-(

Обозначаем монеты М1, М2, ..., М100.

Первое взвешивание: М1 - М33 vs. М34 - М66
Если монеты на какой-то чаше тяжелее, скажем монеты М1 - М33, тогда решение очевидно. Среди М1 - М33 не более одной фальшивой монеты; второе взвешивание, например: М1 - М16 vs. М17 - М32; если одна чаша тяжелее, то все монеты на ней настоящие, а если равенство, то все М1 - М32 настоящие.

Итак, предположим, что М1 - М33 уравновешивают М34 - М66. Это значит, что возможны 3 варианта:
(a) среди М1 - М33 и М34 - М66 - по 2 фальшивых монеты, среди М67 - М100 - ни одной
(b) среди М1 - М33 и М34 - М66 - по одной фальшивой монете, среди М67 - М100 - 2 фальшивых монеты
(c) все 4 фальшивых монеты среди М67 - М100.

Второе взвешивание: М1 - М34 vs. М67 - М100.

Если М67 - М100 перевешивают, значит имел место вариант (a), и М67 - М100 - настоящие.
Если равенство, значит имел место вариант (b), и при этом М34 оказалась фальшивой. Тогда М35 - М66 - настоящие.
Если М1 - М34 перевешивают, то тогда возможны еще 2 случая. Во-первых, возможен вариант (b), где М34 оказалась настоящей. Во-вторых, возможен вариант (c). Но в любом случае, М34 тогда - настоящая.


Правильно?
А сколько у школьников всего было заданий, и сколько им давалось времени на этой олимпиаде? Я эту задачу долго решал, :) если на олимпиаде и решил бы, ничего другого бы не успел.

Делим 100 монет на 5 групп по 20-ть (нумеруем группы с 1-й по 5-ю)

Ставим на весы группы 1+2 <> 3+4
1 Если они уравновешиваются, значит на обоих чашах весов поровну фальшивых монет
Т.е. или ноль или по одной или по две фальшивки.
Соответсвенно в группе 5 или четыре или две или ноль фальшивых монет
Меняем группу 1 с группой 5 и снова взвешиваем: 5+2<>3+4
1.1 Если они уравновешенны, значит в них поровну фальшивых монет, т.е. 1 = 5. Это возможно только если и в 1 и в 5 нет фальшивых монет!
1.2 Если группы 2+5 тяжелее 3+4, значит в 1 была одна или две фальшивые монеты, т.е. в 5 нет фальшивых монет.
1.3. Если группы 3+4 тяжелее 2+5 значит, в 1 была одна фальшивая монета, а в 5 - две фальшивые монеты. Т.е. в группе 2 фальшивых монет нет.
2 Если оне не уравновешиваются, т.е. 1+2 тяжелее 3+4 Т.е. в 1+2 фальшивых монет меньше, или одна или ноль. Сравниваем группы 1 и 2 и если они равны то в них нет фальшивых монет. Если 1 тяжелее, значит в ней нет фальшивок, а в 2 есть одна фальшивка или наоборот.

Если ничего не перепутал, то решений - много. Все они могут быть построены по следующей схеме. На первом взвешивании можно выбрать от 26 до 48 монет на каждой чаше, обозначим как N. На втором взвешивании - из правой чаши перекладываем в левую X монет, все монеты, которые не использовались на первом взвешивании, кладем на правую, а излишек монет с правой откладываем в сторону. Число X можно выбрать любое, удовлетворяющее условию: max(1, 100-3N) <= X <= 49 - N.

Интересный вопрос при этом - какое максимальное число настоящих монет можно гарантировнно найти? И ответ, если не ошибаюсь - 10. Первый раз для этого нужно взвешивать 33, 34 или 35 монет.

С максимальностью проблема в том, что она дается не столько взвешиванием, сколько последующим доказательством. У меня вот сильное подозрение, что применение вышеуказанного алгорифма для 33 монет дает в итоге 11 (хотя самая маленькая кучка 10, да).

А, ну да, настоящие ведь не только в одной группе.
Я могу найти 14 настоящих, и сильно подозреваю, что это максимум.

Сообщено Ильей Богдановым, проверявшим работы в Москве. Следовательно, это либо решение Юлии Гребенниковой, либо Никиты Сопенко.

Разобьем все на группы 1,2,23,26,48. Первое взвешивание: 1+2+23 с 26. Если неравенство, то дальше по стандарту.
Пусть они равны. Тогда второе взвешивание: 1+48 против 23+26.
Варианты:
1 | 2 | 23 | 26 | 48 | Рез-т
--+---+----+----+----+-------
0 } 0 | 0 | 0 | 4 | <
1 } 0 | 0 | 1 | 2 | <
0 } 1 | 0 | 1 | 2 | <
0 } 0 | 1 | 1 | 2 | =
как угодно | 2 | 0 | >
Итого при результате "<" можно сделать вывод о 23 настоящих монетах, при равенстве - о трех, при результате ">" - о 48.

Думаю что да. Но твое решение я "стандартным" не считал.
Стандартное - это когда 1+32+33+34.

Для 200 монет лучшее решение (которое я нашел) - 28 монет. Складывается определенный паттерн :)

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