===== 179 =====

**Конкурсная задача ММ179**(10 баллов)

Имеется 11 монет: 2 золотых; 4 серебряных; 5 бронзовых. Известно, что одна золотая, одна серебряная и 2 бронзовых монеты - фальшивые. Все настоящие монеты равны по весу. Все фальшивые тоже равны по весу, но легче настоящих.Золотые, серебряные и бронзовые отличаются друг от друга по внешнему виду. За четыре взвешивания на чашечных весах без гирь определить фальшивые монеты.

**Решение**

Приведу {{:marathon:mm179_полубасов.pdf|решение}}, присланное Олегом Полубасовым.

**Обсуждение**

Задачу ММ179 я придумал несколько лет назад, заинтересовавшись (с подачи Константина Кнопа) подобными задачами.
Я пытался найти ответ на два вопроса:\\
1. Является ли очевидное необходимое условие "число различных комбинаций не превосходит 3<sup>n</sup>" достаточным для существования решения за n взвешиваний?\\
2. Может ли оказаться, что единственно возможное первое взвешивание в решении не обладает симметрией?

Ответом (положительным) на второй вопрос и явилась задача ММ179. Впрочем, позже я нашел еще несколько вариантов условия, в которых первое взвешивание в решении не является симметричным.
Ответ на второй вопрос я тогда не нашел. Но теперь знаю. И вновь, благодаря Константину Кнопу. 
В то время как я в поисках контрпримера извращался, вовлекая в условие все больше типов разных монет, следовало просто увеличить число комбинаций.
Так, для 36 одинаковых с виду монет, из которых 4 фальшивых, задача не имеет решения за 10 взвешиваний, хотя C(36,4) < 3<sup>10</sup>$. Неразрешимость очевидна из-за невозможности обеспечить первое взвешивание так, чтобы при любом исходе на подозрении осталось не более $3<sup>9</sup> = 19683$ комбинаций.
Вот как распределяются количества возможных комбинаций в зависимости от исхода первого взвешивания и количества монет на чаше:

                        1, [5984, 46937, 5984]

                       2, [10480, 37945, 10480]

                       3, [13788, 31329, 13788]

                       4, [16173, 26559, 16173]

                       5, [17865, 23175, 17865]

                       6, [19059, 20787, 19059]

                       7, [19915, 19075, 19915]

                       8, [20558, 17789, 20558]

                       9, [21078, 16749, 21078]

                      10, [21530, 15845, 21530]

                      11, [21934, 15037, 21934]

                      12, [22275, 14355, 22275]

                      13, [22503, 13899, 22503]

                      14, [22533, 13839, 22533]

                      15, [22245, 14415, 22245]

                      16, [21484, 15937, 21484]

                      17, [20060, 18785, 20060]

                      18, [17748, 23409, 17748]

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

Ситуация с тремя фальшивыми из 50-и одинаковых с виду монет дает еще один контрпример: C(50,3) < 3<sup>9</sup>, но за девять взвешиваний гарантированно найти фальшивые монеты нельзя. 

Итак, ответы на оба сформулированных выше вопроса получены. Но это, конечно, не означает, вопросов не осталось. Заинтересовавшихся отсылаю к статье большого спеца по взвешиваниям Константина Кнопа в первом номере журнала "Квант" за этот год и его же книжке К.Кноп "Взвешивания и алгоритмы: от головоломок к задачам", М.; МЦНМО 2011.

**Награды**

За верное решение задачи ММ179 Алексей Волошин, Олег Полубасов, Анатолий Казмерчук, Виктор Филимоненков, Сергей Половинкин и Ариадна получают 10 призовых баллов. 

**Эстетическая оценка задачи 4.8 балла**
----