Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

179

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

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

Решение

Приведу решение, присланное Олегом Полубасовым.

Обсуждение

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

Ответом (положительным) на второй вопрос и явилась задача ММ179. Впрочем, позже я нашел еще несколько вариантов условия, в которых первое взвешивание в решении не является симметричным. Ответ на второй вопрос я тогда не нашел. Но теперь знаю. И вновь, благодаря Константину Кнопу. В то время как я в поисках контрпримера извращался, вовлекая в условие все больше типов разных монет, следовало просто увеличить число комбинаций. Так, для 36 одинаковых с виду монет, из которых 4 фальшивых, задача не имеет решения за 10 взвешиваний, хотя C(36,4) < 310$. Неразрешимость очевидна из-за невозможности обеспечить первое взвешивание так, чтобы при любом исходе на подозрении осталось не более $39 = 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) < 39, но за девять взвешиваний гарантированно найти фальшивые монеты нельзя.

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

Награды

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

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


 

 


Страница: [[marathon:problem_179]]

marathon/problem_179.txt · Последние изменения: 2019/10/31 20:40 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006