Логин:Пароль:
FAQ по форумуНовые сообщения на Форуме
  • Страница 5 из 6
  • «
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • »
Форум Эрудитов » Логические задачи и головоломки » Математические задачи » Монеты (sml[theme])
Монеты
VitaДата: Четверг, 22.02.2018, 09:33 | Сообщение # 41
Мыслитель
Сообщений: 873
Награды: 158
Совы: 9
Race, браво! Вы порешали все возможные варианты условия задачи! ;)





Теперь, конечно, когда он выпущен на свободу, он уже
по-прежнему не замечает птиц.


Сообщение отредактировал Vita - Четверг, 22.02.2018, 19:20
 
VitaДата: Четверг, 22.02.2018, 19:19 | Сообщение # 42
Мыслитель
Сообщений: 873
Награды: 158
Совы: 9
Прикрепления: 7811197.jpg(48.2 Kb)


Теперь, конечно, когда он выпущен на свободу, он уже
по-прежнему не замечает птиц.
 
KreativshikДата: Четверг, 22.02.2018, 23:30 | Сообщение # 43
Гений
Сообщений: 2472
Награды: 258
Совы: 113
Понарешали вы тут.
Данная задача является немного изменённым вариантом задачи
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.

В  нашей задаче не известно, весят ли фальшивые лёгкие (тяжелые) одинаково, либо по разному. При этом "по разному" может быть по разному.
В любом случае всем спасибо за участие.
Прикрепления: 8150990.jpg(113.1 Kb)


Жёлтый Зелёный Красный


Сообщение отредактировал Kreativshik - Четверг, 22.02.2018, 23:37
 
RaceДата: Пятница, 23.02.2018, 11:18 | Сообщение # 44
Гуру
Сообщений: 444
Награды: 35
Совы: 12
Kreativshik,
спасибо, как всегда очень интересно.
Я сам решил за 9 взвешиваний, 7 получилось после оптимизации решения Vita в 8 действий.

Касательно задачи при  различном весе легких и тяжелых монет, на данный момент получено решение в 18 взвешиваний, представляющее собой обычную сортировку.
 
VitaДата: Понедельник, 26.02.2018, 18:55 | Сообщение # 45
Мыслитель
Сообщений: 873
Награды: 158
Совы: 9

Цитата Kreativshik ()
Буквой Л обозначим легкие монеты,  Т — тяжелые,  Н — настоящая.Первые четыре взвешивания — это попарные сравнения восьми монет друг с другом.
Если одна из двух взвешиваемых монет оказалась тяжелее, то кладем ее в «Т-группу», а вторую — в «Л-группу».
Если же обе монеты равны, то можно их выкинуть.
Монету, которая в этих четырех взвешиваниях не была на весах, обозначим буквой 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.2018, 19:05
 
RaceДата: Понедельник, 26.02.2018, 19:05 | Сообщение # 46
Гуру
Сообщений: 444
Награды: 35
Совы: 12
Vita,
аналогично как и в предыдущем решении

А(ттл)>В(ттл) => настоящая л из А, либо одна из тт из В. Соответственно взвешиваем тт из В между собой, в случае равенства - л из А, в случае неравенства та т что легче.
В других случаях неравенство не может выполниться, то есть есть всего 3 равно возможных варианта:
А(ттн)>B(ттл)
А(ттл)>В(нтл)
А(ттл)>В(тнл)
В данном способе 2 монеты могут быть определены исключением, 9 мы вообще не взвешивали,  точно так же как не взвешивали л из А отдельно ни с какой другой.


Сообщение отредактировал Race - Понедельник, 26.02.2018, 19:06
 
VitaДата: Понедельник, 26.02.2018, 19:14 | Сообщение # 47
Мыслитель
Сообщений: 873
Награды: 158
Совы: 9
Race, например - тяжелых четыре осталось, настоящая и две легких. Но мы не знаем этого наверняка, ведь могли уйти две тяжелые. В принципе вариантов то всего два, иначе настоящая в Х и уйдут и пара тяжелых, но, что взвешивать пятым?

Левый вариант Х - Т4                                                  Правый вариант  Х- Л4

А(Т1+Т2+Т3)> В(Н+Л3+Л4)                                          А(Т3+Т4+Н)>B(Л1+Л2+Л3)
Кажется дошло: Х с одной из выбывших  пятыми взвешиваем, узнаем какой из вариантов левый или правый.
Тогда шестым взвешиванием или в А(если выбывшие тяжелые, сравниваем любые две - если равны, то третья, или та, что легче) , или в В если выбывшие лёгкие аналогичным образом находим Настоящую. При равенстве лёгких и равенстве тяжелых.


Теперь, конечно, когда он выпущен на свободу, он уже
по-прежнему не замечает птиц.


Сообщение отредактировал Vita - Пятница, 02.03.2018, 02:31
 
RaceДата: Понедельник, 26.02.2018, 22:01 | Сообщение # 48
Гуру
Сообщений: 444
Награды: 35
Совы: 12
Vita,
да именно так) не думаю что появится 5) Я то максимум 9 придумал)
 
KreativshikДата: Вторник, 27.02.2018, 16:03 | Сообщение # 49
Гений
Сообщений: 2472
Награды: 258
Совы: 113

Цитата
если одна пара ушла, мы не знаем каких и осталось 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.2018, 16:15
 
VitaДата: Вторник, 27.02.2018, 19:35 | Сообщение # 50
Мыслитель
Сообщений: 873
Награды: 158
Совы: 9
Цитата Kreativshik ()
Обозначим оставшиеся монеты Т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
не понятно :(


Теперь, конечно, когда он выпущен на свободу, он уже
по-прежнему не замечает птиц.
 
Форум Эрудитов » Логические задачи и головоломки » Математические задачи » Монеты (sml[theme])
  • Страница 5 из 6
  • «
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • »
Поиск:

Интересная информация
Последние задачи Сообщество эрудитов ВКонтакте Рейтинг сообщений Совиный рейтинг
1.Антифразы54
2.Занимательная математика200
3.Улыбка Бога0
4.Необычная копилка11
5.Мужики и лошадь1
6.Достаточность основания11
7.Театр одного зрителя3
8.Сигнал для управления4
9.Шахматный марафон44
10.Поломайте-ка голову9
1.Rostislav4810
2.Lexx4728
3.nebo3484
4.Иван3061
5.Kreativshik2472
6.никник2242
7.Гретхен1802
8.erudite-man1317
9.Valet937
10.Vita873
1.nebo115
2.Kreativshik113
3.sovetnik49
4.IQFun30
5.Pro100_Artyom27
6.MrCredo26
7.marutand20
8.хан20
9.slltllnll12
10.никник12


ГлавнаяГостевая книгаFAQНаписать админуКоллегиФорум ЭрудитовХостинг от uCoz