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





Сообщение отредактировал Vita - Чт, 22.02.18, 19:20
 
VitaДата: Чт, 22.02.18, 19:19 | Сообщение # 42
Мудрец
Сообщений: 1488
Награды: 241
Совы: 13
Прикрепления: 7811197.jpg (48.2 Kb)
 
KreativshikДата: Чт, 22.02.18, 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.18, 23:37
 
RaceДата: Пт, 23.02.18, 11:18 | Сообщение # 44
Просветленный
Сообщений: 459
Награды: 41
Совы: 12
Kreativshik,
спасибо, как всегда очень интересно.
Я сам решил за 9 взвешиваний, 7 получилось после оптимизации решения Vita в 8 действий.

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

Цитата 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.18, 19:05
 
RaceДата: Пн, 26.02.18, 19:05 | Сообщение # 46
Просветленный
Сообщений: 459
Награды: 41
Совы: 12
Vita,
аналогично как и в предыдущем решении

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


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

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

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


Сообщение отредактировал Vita - Пт, 02.03.18, 02:31
 
RaceДата: Пн, 26.02.18, 22:01 | Сообщение # 48
Просветленный
Сообщений: 459
Награды: 41
Совы: 12
Vita,
да именно так) не думаю что появится 5) Я то максимум 9 придумал)
 
KreativshikДата: Вт, 27.02.18, 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.18, 16:15
 
VitaДата: Вт, 27.02.18, 19:35 | Сообщение # 50
Мудрец
Сообщений: 1488
Награды: 241
Совы: 13
Цитата 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.Цифра)))2
2.Бессмысленное и загадочно...9
3.Помощь с решением задачи1
4.Помогите решить ребус1
5.О времена, о нравы ...10
6.Случайная хорда3
7.Лучше9
8.Акула12
9.6 ребусов3
10.Головоломка без ключа1
1.Rostislav5379
2.Lexx4728
3.nebo3636
4.Иван3061
5.никник2735
6.Kreativshik2472
7.Гретхен1807
8.Vita1488
9.erudite-man1378
10.Valet937
1.nebo123
2.Kreativshik113
3.sovetnik49
4.MrCredo38
5.IQFun30
6.Pro100_Artyom27
7.marutand20
8.хан20
9.никник15
10.Фигаро15

ГлавнаяГостевая книгаFAQОбратная связьКоллегиФорум Эрудитов