2
1

Имеется 99 одинаковых на вид монет. Известно, что одна из них фальшивая, легче остальных настоящих. Можно ли, используя чашечные весы без гирь, найти фальшивую монету за 7 взвешиваний, если каждую монету можно взвешивать не более 2 раз?

задан 30 Сен '12 20:24

1

надеюсь, это не задачки из олимпиады, которая проходит прямо сейчас? )) а мы тут решаем...

(30 Сен '12 20:59) chameleon
1

Эта задача была на олимпиаде 1997 "Турнир Ломоносова" года.

(30 Сен '12 21:38) dmg3

Одно другому не мешает... )))

(30 Сен '12 21:47) DocentI

Что это значит "...каждую монету можно взвешивать не более 2 раз"?

(1 Окт '12 17:26) Anatoliy

Пример: 1,2,6 сравнить с 5,7 потом 1,7 сравнить с 2,5,6 и больше монеты 1,2,5,6,7 на весы класть нельзя

(1 Окт '12 17:31) dmg3

Что это значит "...каждую монету можно взвешивать не более 2 раз"?

Что каждая монета может оказаться на весах не более 2 раз.

(1 Окт '12 19:19) DocentI
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
3

Для начала, отметим, что класть на весы разное количество монет абсолютно бесполезно. Значит, единственный способ решения задачи - на каждом шаге делить все монеты на три группы размерами $%i, i, n-2i$% (где $%n$% - число монеток) и класть на весы первые две группы, что однозначно покажет, в какой из трех групп находится фальшивая монетка.
Сначала решим более простую задачку: из скольки монет (максимум) можно найти фальшивую за $%m$% взвешиваний, если каждую монету можно класть на весы только один раз? Из-за такого строгого ограничения есть только один способ нахождения фальшивой монетки: класть на весы по две монетки за шаг ($%i=1$%). Следовательно, за $%m$% взвешиваний мы сможем найти фальшивую монетку в группе максимум из $%2m+1$% монеток.
Вернемся к исходной задаче. Если мы хотим найти фальшивую монетку в группе из $%n$% монеток за $%m$% взвешиваний, то оптимальным алгоритмом будет сравнить на первом шаге группы из $%i=2m-1$% монеток. Если одна из групп легче, то в ней фальшивая монетка, которую нам надо найти за $%m-1$% взвешиваний. В предыдущем абзаце доказано, что это возможно. Если же весы уравновешены, то фальшивая монетка находится в третьей группе, и мы повторяем тот же алгоритм для новых параметров: $%n_{i+1}=n_i-2(2m-1), m_{i+1}=m_i-1$%. Итак:
$%n_0=99;m_0=7$%
$%n_1=99-2(2 \times 7-1)=73;m_1=6$%
$%n_2=73-2(2 \times 6-1)=51;m_2=5$%
$%n_3=51-2(2 \times 5-1)=33;m_3=4$%
$%n_4=33-2(2 \times 4-1)=19;m_4=3$%
$%n_5=19-2(2 \times 3-1)=9;m_5=2$%
$%n_6=9-2(2 \times 2-1)=3;m_6=1$%
$%n_7=3-2(2 \times 1-1)=1;m_7=0$%
То есть, после седьмого взвешивания в третьей группе осталась ровно одна монетка, которая и является фальшивой. То есть, ответ - да, можно.
P.S. у меня есть доказательство оптимальности алгоритма, который я использовал выше, но его я приводить здесь не буду, т.к. формально цель достигнута - найден способ. А вот если бы монеток было 100, то пришлось бы писать, чтоб доказать, что способа нет...

ссылка

отвечен 1 Окт '12 21:46

изменен 1 Окт '12 23:50

DocentI's gravatar image


9.8k1042

Верно, но фразы типа "единственный способ решения задачи -..." для решения не нужны и могут лишь создать поводы для придирок.

(1 Окт '12 22:07) dmg3

Хммм... Я имел в виду "оптимальный", а не "единственный", извиняюсь. То, что приведенные алгоритмы действительно оптимальны, для себя я доказал (так как изначально думал, что это задачка на доказательство невозможности, а не на поиск возможности, так сказать). А в данном случае эти слова действительно лишние, согласен =)

(1 Окт '12 22:14) chameleon

@chameleon, Вы явно ценное приобретение для нашего форума. Но все-таки следите и за грамматикой: слова "ложить" в русском языке нет. Я поправила у Вас в тексте ответа.

(2 Окт '12 0:37) DocentI

Спасибо =)

(2 Окт '12 1:00) chameleon
10|600 символов нужно символов осталось
0

Я знаю, подобные задачи решал мой внук у себя в лицее. Автор вопроса вероятнее всего школьник лет десяти. Ему могут быть непонятны Ваши выкладки. Я бы ответил так:

  • Откладываю одну монетку в сторону;
  • Оставшиеся 98 монет делю на две равные кучки по 48 монет и кладу их в разные чаши весов;
  • Маловероятно, но возможно, весы могут быть уравновешены. Тогда искомая монета отложена мной в сторону;
  • Более легкую кучку делю на две равные кучки по 24 монеты и путем сравнивания веса кучек на весах выбираю более легкую;
  • Снова делю выбранную кучку на две равные кучки по 12 монет, сравниваю их вес и выбираю более легкую;

Таким образом в конце концов в сравниваемых кучках останется по 3 монеты. Думаю, что из трех монет определить более легкую при наличии весов ни у кого не вызовит затруднений. Алгоритм простой, возможно не оптимальный. Но семи взвешиваний как раз достаточно для нахождения фальшивки.

ссылка

отвечен 1 Окт '12 23:39

3

Автор вопроса определенно не школьник, так как в другом вопросе спрашивает о гомоморфизмах групп.

98 : 2 = 49 , а не 48.

Ваше решение неверное, так как не учитывает ограничение двух взвешиваний.

(1 Окт '12 23:47) DocentI

$%99 = 1 + 98 = 1 + 2 \cdot 49 = 1 + 2 \cdot 7^2 = 1 + 2 \cdot 7 \cdot (8 - 1) = 1 + 2 \cdot \sum_{i = 1}^{7} (2i - 1)$%

(2 Окт '12 5:26) Галактион
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×995
×17
×4

задан
30 Сен '12 20:24

показан
2696 раз

обновлен
8 Окт '13 5:02

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru