Форум: "Потрепаться";
Текущий архив: 2002.12.19;
Скачать: [xml.tar.bz2];
ВнизЗадача монетами Найти похожие ветки
← →
QUE (2002-11-26 10:22) [0]Есть 12 монет 11 из них одинаковой массы 1 монета отличной массы от остальных( неизвестно больше или меньше ) есть весы с двумя чашками нужно за 3 взвешивания определить фальшивую монету
← →
Manic Mechanic (2002-11-26 10:32) [1]Взвешиваем 10 монет, по пять - если массы равны, сами понимаете. То же самое делаем с оставшимися группами по 5 монет (взвешиваем 4 по 2).
← →
Дмитрий К.К. (2002-11-26 10:32) [2]Разбиваем на три кучки и взвешиваем две из них.
← →
Kaban (2002-11-26 10:35) [3]задача появлялась с месяц назад и решение не такое простое, я в него не вдавался
естественно разбиением на три кучки решить не удасться
← →
Дмитрий К.К. (2002-11-26 10:38) [4]1) 4
2) 4
3) 4
Если 1 и 2 равны, то в 3-й фальшивка.
Одним взвешиванием отсекаем сразу 8.
Затем 1 1 1 1
Двух оставшихся взвешиваний хватит :D
← →
Дмитрий К.К. (2002-11-26 10:39) [5]Kaban, ты неправ!
← →
Kaban (2002-11-26 10:41) [6]А теперь представьте, что будет если весы, на чашках которых находится по четыре монеты, не уравновесятся
← →
Kaban (2002-11-26 10:43) [7]задача, кстати, справедлива и для 13 монет
← →
Digitman (2002-11-26 10:45) [8]задача уже зажевана)
именно - сразу же разбиением на 3 кучи по 4 монеты
это - единственный верный алгоритм
← →
Дмитрий К.К. (2002-11-26 10:45) [9]неизвестно больше или меньше... да уж... пардон :(((
← →
Manic Mechanic (2002-11-26 10:47) [10]И мой пардоН :(((
← →
dolmat (2002-11-26 10:48) [11]Эту задачу я помню еще когда я был в школе в классе 7-8 на уроке математики а это было в 1985 примерно и решали ее разбиением на 3 кучки. но именно максимум 3 взвешивания т.к. по веле случая можно взять и две монеты и попадется сразу одна фальшивка.
1 е взвешивание 1 из 4 4 4
т.к. заранее известно что одна фальшивка то при одинаковой массе двух разбиваем третью по одной либо тяжелейшую
2-е взвешивание 1 1
при одинаковой массе
3-е 1 1
← →
Kaban (2002-11-26 10:50) [12]почему-то все исходят из того, что первые две кучки обязательно уравновесятся и останется рассмотреть третью кучку :)
← →
Дмитрий К.К. (2002-11-26 10:50) [13]dolmat, тебе же сказано, весы могут в САМОМ НАЧАЛЕ не уравновеситься.
← →
Дмитрий К.К. (2002-11-26 10:51) [14]Kaban, видать, желание идти по линии наименьшего сопротивления ;)
← →
int64 (2002-11-26 10:51) [15]6 вариантов решения не считая зеркальных.
Где-то есть даже урл с готовым ответом.
← →
Kaban (2002-11-26 10:52) [16]да нет, просто эту задачу путают с той, в которой известно, в какую сторону изменяется вес фальшивой монеты
← →
Calm (2002-11-26 10:54) [17]Помню мы с друзьями решили эту задачу, но давно, уже не помню как.
Суть заключается в том, что снача монеты группируются в 3 кучи по 4 монеты и взвешиваются.
Потом нужно как-то хитро часть монет перекладывать в другие кучи. Тогда все получится.
Вспоминать точно сейчас нет времени :(
← →
Дмитрий К.К. (2002-11-26 10:54) [18]int64, ну-ка поделись.
← →
Дмитрий К.К. (2002-11-26 10:57) [19]6 3 3
2 2 2
1 1
← →
Manic Mechanic (2002-11-26 10:58) [20]Берем 4 монеты, которые оказались тяжелее, и взвешиваем их по 2.
1) если равно - нестандартная монета в оставшишся 4 и она легче других
2) неравенство - нестандартная монета среди тех двух, которые тяжелее.
← →
Manic Mechanic (2002-11-26 11:00) [21]ЗЫ к пункту 2) нестандартная монета тяжелее
← →
Дмитрий К.К. (2002-11-26 11:01) [22]Не годится
← →
Kaban (2002-11-26 11:02) [23]кто-нибудь хочет подумать или предоставить решение?
← →
OutSidEr (2002-11-26 11:03) [24]Господа, задача вполне простая, если задуматься.
Монеты разбиваются на 4 кучки, по 3 монеты, и выполняется взвешивание двух кучек между собой. Мы получили 6 монет, среди которых одна фильшивая. Назовем эти 6 монет группой 1. Далее, берется 3 монеты из группы 1 и сравниваются с тремя заведомо настоящими монетами(из тех 6, что отсеялись при первом взвешивании). Теперь у нас есть 3 монеты, одна из которых фальшивая, и всего 1 взвешивание, плюс ко всему мы теперь знаем, в какую сторону отличается вес фальшивой монеты.
А уж зная, в какую сторону отличается вес, из 3 монет за одно взвешивание определить фальшивую элементарно даже для 3-классника.
Решение я нашел за 5 минут.
← →
Manic Mechanic (2002-11-26 11:04) [25]
> Дмитрий К.К. © (26.11.02 11:01)
Почему ? :((
← →
OutSidEr (2002-11-26 11:05) [26]Ой, стормозил, сорри... уже вижу свою ошибку.
← →
Kaban (2002-11-26 11:06) [27]2 OutSidEr (26.11.02 11:03)
Не говорите гоп раньше времени (это я про 5 минут).
Допустим вы определили группу 1.
Взяли 3 монеты из этой группы и 3 заведомо нефальшивые монеты. Что вы будите делать если при этом взвешивании будет равенство.
← →
Дмитрий К.К. (2002-11-26 11:08) [28]
> OutSidEr (26.11.02 11:03)
> Господа, задача вполне простая, если задуматься.
Я дальше даже читать не стал :)
← →
Kaban (2002-11-26 11:08) [29]я пытался решить задачу таким образом, сравнивая вес монет с заведомо нефальшивыми, чтобы определить в какую сторону различается вес, за три взвешивания, похоже, не получается
← →
int64 (2002-11-26 11:13) [30]Kaban © (26.11.02 10:52)
> да нет, просто эту задачу путают с той, в которой известно,
> в какую сторону изменяется вес фальшивой монеты
Ничего я не путаю.
За два взвешивания:
2 варианта из 4 монет определить фальшивку.
3 варианта из 3+3.
Итого, если скомбинаторить 2*3.
← →
Kaban (2002-11-26 11:14) [31]2 int64 © (26.11.02 11:13)
Да я знаю, как решить эту задачу
← →
Manic Mechanic (2002-11-26 11:18) [32]Плз.объясните, чем плох мой ваиант, если после второго взвешивания у меня остаются 4 монеты и я знаю тяжелее или легче фальшивая ?
← →
Kaban (2002-11-26 11:22) [33]а как вы это узнали?
← →
Дмитрий К.К. (2002-11-26 11:22) [34]Лан, я должен отлучиться. Надеюсь, когда вернусь, решение таки будет опубликовано ;)
← →
OutSidEr (2002-11-26 11:24) [35]Тогда, начиная со второго взвешивания, нужно комбинировать кучки по частям между собой. Это уже надо с ручкой и бумажкой...
← →
Manic Mechanic (2002-11-26 11:31) [36]
> Kaban © (26.11.02 11:22)
> а как вы это узнали?
Если не было равновесия при первом взвешивании
Берем 4 монеты, которые оказались тяжелее, и взвешиваем их по 2.
1) если равно - нестандартная монета в оставшишся 4 и она легче других
2) неравенство - нестандартная монета среди тех двух, которые тяжелее.
Но так все равно не хватает одного взвешивания. Сорри.
← →
NeyroSpace (2002-11-26 11:43) [37]>Manic Mechanic © (26.11.02 10:32)
Сразу дал оптимальное решение, т.е. если бы вместо монет были бы мешочки по 50кг, то он бы гнул спину меньше всех :-)
← →
vopros (2002-11-26 11:44) [38]У меня дежа вю?
← →
Johnmen (2002-11-26 11:53) [39]>vopros © (26.11.02 11:44)
Точно !
У меня тоже...:)))
← →
Alex Y (2002-11-26 11:54) [40]Господа, а кто вам сказал, что фальшивая монета тяжелее (или легче) :)
← →
SPeller (2002-11-26 12:03) [41]Я уже задавал такой вопрос.. Нашёл решение, но оно не всегда выполнимо
← →
icWasya (2002-11-26 12:04) [42]1) 1, 2, 3, 4 <=> 5, 6, 7, 8
2) 1, 9, 10, 11 <=> 2, 3, 4, 5
3) 3, 7, 10, 12 <=> 1, 4, 6, 11
← →
SPeller (2002-11-26 12:05) [43]Решение есть в книге Мартина Гарднера "Математические досуги"
← →
OutSidEr (2002-11-26 12:08) [44]Хе. Решение есть и в инете. У меня даже есть ссылка. Только интереснее решить самому.
← →
Wonder (2002-11-26 12:11) [45]Вот они, эти взвешивания:
MA DO - LIKE
ME TO - FIND
FAKE - COIN
Буквами обозначены монеты с первой по двенадцатую. :)
По результатам этих взвешиваний однозначно делается вывод о фальшивке и ее весе.
← →
Курящий (2002-11-26 13:44) [46]Есть десять мешков с золотыми монетами. В одном мешке все монеты фальшивые. Пусть настоящая монета весит 5 гр., а фальшивая - 4 гр. Есть цифровые весы, которые показывают вес. Как с помощью одного взвешивания определить, в каком мешке фальшивые монеты?
← →
OutSidEr (2002-11-26 13:45) [47]О! Вроде как еще одно решение появилось в голове.
Значит делим на три группыпо 4 монеты. Взвешиваем
две между собой.
Опустим вариант, когда они уравниваются-там элементарно все.
Итак, одна чаша перевесила. Обзовем ее 1. А вторую - 2.
Откладываем 3 монеты из группы 2 в сторонку, заменяя их 3 монетами из группы 1. А пустые места в группе один занимаем монетами из группы 3. Снова взвешиваем группы 1 и 2. Вероятны 3 исхода:
1: 1 снова перевесила. Значит единственная там оставшаяся от предыдущей раскладки монета - и есть фальшивка
2: на этот раз перевесила 2 - значит фальшивка находится среди 3 монет, переложенных из группы 1 в группу 2, и она тяжелее остальных. Зная, в какую сторону отличается вес фальшивки, среди 3 монет ее элементарно вычислить за одно взвешивание.
3: чаши уравнялись - значит фальшивка в трех отложенных из группы 2 монетах, и она легче остальных. Опять же, из 3х монет ее вычислить элементарно за одно взвешивание.
Вроде все....
← →
OutSidEr (2002-11-26 14:03) [48]2Курящий:
Просто ложить мешки по одному, цифра на весах будет увеличиваться. И когда она увеличится не на такое число, как предыдущие(или последующие - без разницы), тогда и найдешь ты мешок с фальшивками 8))))
← →
OutSidEr (2002-11-26 14:04) [49]2Курящий(вдогонку)для чистоты эксперимента, можешь ложить не мешки, а по одной монете из каждого мешка.
← →
Сатир (2002-11-26 14:28) [50]2OutSidEr (26.11.02 14:04)
каждый раз, когда ты будешь добавлять по монете или мешку и смотреть на весы, это будет считаться как следующее взвешиваение, а нужно только один раз положить монеты на весы, посмотреть на значение, которое они весят, посчитать и сказать в каком мешке фальшивка, а не добавлять по одной монете и смотреть на показания весов. Взвешивать можно только один раз.
← →
Wonder (2002-11-26 14:37) [51]Ну с мешками - это легко.
Начиная с одной монеты из первого мешка, вынуть из каждого поледующего мешка на одну монету больше и покласть это все на весы, поставив в соответствие с мешками.
← →
Kaban (2002-11-26 15:17) [52]OutSidEr (26.11.02 13:45)
А если монет 13?
← →
OutSidEr (2002-11-26 16:01) [53]2Kaban:
Пишу навскидку(работать надо 8) - можно попробовать отложить одну из монет, с 12 проделать вышеописанные манипуляции, и если там не обнаружится фальшивки(всегда будет равновесие), то значит отложенная - и есть фальшивка)
← →
Manic Mechanic (2002-11-26 16:05) [54]>> OutSidEr (26.11.02 13:45)
> Зная, в какую сторону отличается вес фальшивки
Откуда зная ?
> ( неизвестно больше или меньше )
← →
Kaban (2002-11-26 16:08) [55]2 OutSidEr (26.11.02 16:01)
да нет, твой способ похоже работает для 13 монет, для кучек
4-4-5 из кучки в пять монет можно выделить фальшивую двумя взвешиваниями
← →
Johnmen (2002-11-26 16:20) [56]>Kaban © (26.11.02 16:08)
Нет. Максимум 12 за 3.
← →
Kaban (2002-11-26 16:29) [57]Johnmen © (26.11.02 16:20)
Нет. По крайней мере 13 за 3.
← →
Johnmen (2002-11-26 16:50) [58]>Kaban © (26.11.02 16:29)
Приведи алгоритм. Причем я уверен, что он некорректный.
(Для определения не только фальшивой, но и ее относительного веса)
← →
OutSidEr (2002-11-26 16:52) [59]Да, согласен с Кабаном
← →
OutSidEr (2002-11-26 16:56) [60]Кому интересно - я нашел целую статью посвященным этой задаче и ее модификациям(вернее она сама есть модификация классической задачи).
http://www.computerra.ru/offline/1997/228/969
правда в описанный там способ я так до конца и не врубился, чисто математический подход. У меня с этим туго...
← →
Kaban (2002-11-27 09:51) [61]2 Johnmen © (26.11.02 16:50)
Отложим в сторону тринадцатую монету. Обозначим 12 монет буквами
латинского алфавита:
A, B, C, D, E, F, G, H, I, J, K, L
Проведем три взвешивания:
EBHK - JFCD
EDLK - AFGH
ABCD - IKFG
Обозначим буквами Л, П, Р положения чашек весов:
Л - перевесила левая чашка
П - перевесила правая чашка
Р - равенство
монета A легче : РПЛ монета A тяжелей : РЛП
монета B легче : ЛРЛ монета B тяжелей : ПРП
монета C легче : ПРЛ монета C тяжелей : ЛРП
монета D легче : ПЛЛ монета D тяжелей : ЛПП
монета E легче : ЛЛР монета E тяжелей : ППР
монета F легче : ППП монета F тяжелей : ЛЛЛ
монета G легче : РПП монета G тяжелей : РЛЛ
монета H легче : ЛПР монета H тяжелей : ПЛР
монета I легче : РРП монета I тяжелей : РРЛ
монета J легче : ПРР монета J тяжелей : ЛРР
монета K легче : ЛЛП монета K тяжелей : ППЛ
монета L легче : ЛРЛ монета L тяжелей : РПР
Если при всех трёх взвешиваниях весы будут сбалансированы
фальшивой является отложенная нами, тринадцатая монета.
Мы не сможем сказать легче она или тяжелей настоящей,
но этого в задаче и не требуется.
Кроме того, способ, представленный OutSidEr (26.11.02 13:45) похоже работает и для 13 монет
← →
sonja (2002-11-27 12:25) [62]>OutSidEr (26.11.02 16:56)
Хотелось бы понять откуда взялся такой способ нумерования монет...
Страницы: 1 2 вся ветка
Форум: "Потрепаться";
Текущий архив: 2002.12.19;
Скачать: [xml.tar.bz2];
Память: 0.59 MB
Время: 0.008 c