Понарешали вы тут. Данная задача является немного изменённым вариантом задачи De-coin за авторством by Veronica Gross, Rob Speer, Catherine Havasi.
Ежегодно в MIT (Массачу́сетский технологи́ческий институ́т англ. Massachusetts Institute of Technolog ) устраивается некоторый квест. В институте собираются любители головоломок, Им даётся головоломка, решив которую они поймут где в институте искать следующую головоломку, так порядка ста головоломок, решив которые первым, Вы найдёте спрятанную специально изготовленную монету. Так вот в 2013 году одной из последних головоломок была De-coin. Формулируется она так «There are nine coins, one real and eight fake. Four of the fake coins weigh the same and are lighter than the real coin. The other four fake coins weigh the same and are heavier than the real coin. Find the real coin in seven weighings on the balance scale.»
На русском это озвучит так.
«Есть девять монет, одна настоящая и восемь фальшивых. Четыре из фальшивых монет весят одинаково и легче, чем настоящая монета. Остальные четыре фальшивые монеты весят одинаково и тяжелее настоящей монеты. Найдите настоящую монету за семь взвешиваний на чашечных весах.» Именно эту задачу решил Race, поэтому в подарок ему дарю изображение монеты, которую нашёл победитель игры в МИТ в 2013 году.
Кстати по легенде она стоит триллион долларов. Орегинального решения я не нашёл, по ссылке на эту задачу выплывает какая-то хрень. Архив всех задач можно посмотреть здесь Уверен решение Race, не хуже. Награду дать пока не могу ни кому, потому-что задача выложенная здесь не решена, да и собственно, задачу которую решали в МИТ в 2013 году можно решить за шесть взвешиваний Например вот по такому алгоритму:
Буквой Л обозначим легкие монеты, Т — тяжелые, Н — настоящая. Первые четыре взвешивания — это попарные сравнения восьми монет друг с другом. Если одна из двух взвешиваемых монет оказалась тяжелее, то кладем ее в «Т-группу», а вторую — в «Л-группу». Если же обе монеты равны, то можно их выкинуть. Монету, которая в этих четырех взвешиваниях не была на весах, обозначим буквой X .Рассмотрим наихудший случай:Т- и Л-группа состоят из 4 монет каждая, ни одной отложенной пары нет. Обозначим имеющиеся монеты Т1, Т2, Т3, Т4, Л1, Л2, Л3, Л4 и X. Пятое взвешивание: Т1 + Т2 + Л1 vs Т3 + Т4 + Л2. Равенство означает, что настоящей монетой может быть только какая-то из Л3, Л4 и X. Тогда сравнив Л3 с Л4, мы определим настоящую монету: либо более тяжелая из этих двух, а если они равны по весу, то X. Неравенство (например, Т1 + Т2 + Л1 легче Т3 + Т4 + Л2) означает, что настоящая монета — это либо Т1, либо Т2, либо Л2. Тогда достаточно сравнить шестым взвешиванием Т1 с Т2.
В нашей задаче не известно, весят ли фальшивые лёгкие (тяжелые) одинаково, либо по разному. При этом "по разному" может быть по разному. В любом случае всем спасибо за участие.
Kreativshik, спасибо, как всегда очень интересно. Я сам решил за 9 взвешиваний, 7 получилось после оптимизации решения Vita в 8 действий.
Касательно задачи при различном весе легких и тяжелых монет, на данный момент получено решение в 18 взвешиваний, представляющее собой обычную сортировку.
Буквой Л обозначим легкие монеты, Т — тяжелые, Н — настоящая.Первые четыре взвешивания — это попарные сравнения восьми монет друг с другом. Если одна из двух взвешиваемых монет оказалась тяжелее, то кладем ее в «Т-группу», а вторую — в «Л-группу». Если же обе монеты равны, то можно их выкинуть. Монету, которая в этих четырех взвешиваниях не была на весах, обозначим буквой X .Рассмотрим наихудший случай: Т- и Л-группа состоят из 4 монет каждая, ни одной отложенной пары нет. Обозначим имеющиеся монеты Т1, Т2, Т3, Т4, Л1, Л2, Л3, Л4 и X. Пятое взвешивание: Т1 + Т2 + Л1 vs Т3 + Т4 + Л2. Равенство означает, что настоящей монетой может быть только какая-то из Л3, Л4 и X. Тогда сравнив Л3 с Л4, мы определим настоящую монету: либо более тяжелая из этих двух, а если они равны по весу, то X. Неравенство (например, Т1 + Т2 + Л1 легче Т3 + Т4 + Л2) означает, что настоящая монета — это либо Т1, либо Т2, либо Л2. Тогда достаточно сравнить шестым взвешиванием Т1 с Т2.
В нашей задаче не известно, весят ли фальшивые лёгкие (тяжелые) одинаково, либо по разному. При этом "по разному" может быть по разному. В любом случае всем спасибо за участие.
И вам спасибо за решение, но если одна пара ушла, мы не знаем каких и осталось 7 монет, то какое пятое ? еле-еле усвоила как за семь, с этим вариантом совсем туго
Сообщение отредактировал Vita - Пн, 26.02.18, 19:05
А(ттл)>В(ттл) => настоящая л из А, либо одна из тт из В. Соответственно взвешиваем тт из В между собой, в случае равенства - л из А, в случае неравенства та т что легче. В других случаях неравенство не может выполниться, то есть есть всего 3 равно возможных варианта: А(ттн)>B(ттл) А(ттл)>В(нтл) А(ттл)>В(тнл) В данном способе 2 монеты могут быть определены исключением, 9 мы вообще не взвешивали, точно так же как не взвешивали л из А отдельно ни с какой другой.
Сообщение отредактировал Race - Пн, 26.02.18, 19:06
Race, например - тяжелых четыре осталось, настоящая и две легких. Но мы не знаем этого наверняка, ведь могли уйти две тяжелые. В принципе вариантов то всего два, иначе настоящая в Х и уйдут и пара тяжелых, но, что взвешивать пятым?
Левый вариант Х - Т4 Правый вариант Х- Л4
А(Т1+Т2+Т3)> В(Н+Л3+Л4) А(Т3+Т4+Н)>B(Л1+Л2+Л3) Кажется дошло: Х с одной из выбывших пятыми взвешиваем, узнаем какой из вариантов левый или правый. Тогда шестым взвешиванием или в А(если выбывшие тяжелые, сравниваем любые две - если равны, то третья, или та, что легче) , или в В если выбывшие лёгкие аналогичным образом находим Настоящую. При равенстве лёгких и равенстве тяжелых.
Сообщение отредактировал Vita - Пт, 02.03.18, 02:31
если одна пара ушла, мы не знаем каких и осталось 7 монет, то какое пятое
Обозначим оставшиеся монеты Т1, Т2, Т3, Л1, Л2, Л3, X. Пятое взвешивание: Т1 + Л1 vs Т2 + Л2.Равенство означает, что Н — либо Т3, либо Л3, либо X. Шестым взвешиванием можно сравнить Т1 + Л1 с Т3 + Л3: если Т3 + Л3 легче, то настоящей является Т3, если тяжелее, то — Л3, а при равенстве — X.Если например, Т1 + Л1 < Т2 + Л2, то настоящая — либо Л2, либо Т1. Тогда сравниваем Л1 с Л2 , ипо результату этого взвешивания узнаем настоящую.
Сообщение отредактировал Kreativshik - Вт, 27.02.18, 16:15
Обозначим оставшиеся монеты Т1, Т2, Т3, Л1, Л2, Л3, X. Пятое взвешивание: Т1 + Л1 vs Т2 + Л2.Равенство означает, что Н — либо Т3, либо Л3, либо X.Шестым взвешиванием можно сравнить Т1 + Л1 с Т3 + Л3: если Т3 + Л3 легче, то настоящей является Т3, если тяжелее, то — Л3, а при равенстве — X.Если например, Т1 + Л1 < Т2 + Л2, то настоящая — либо Л2, либо Т1. Тогда сравниваем Л1 с Л2 , ипо результату этого взвешивания узнаем настоящую.
Были монеты 1гр=Л1, 2гр=Л2,3гр=Л3 4гр=Л4 5гр=Н 6гр=Т1 7гр=Т2 (Т3=8гр и Т4=8гр выбыли) Переобозначили 1=Л1, 2=Л2,3=Л3 4=Т1 5=Т2? 6=Т3 7=Х пятое 1+4<2+5 шестое 1+4<3+6 не понятно
