Задача монетами

← →
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 © (26.11.02 10:52)

> да нет, просто эту задачу путают с той, в которой известно,
> в какую сторону изменяется вес фальшивой монеты

Ничего я не путаю.
За два взвешивания:
2 варианта из 4 монет определить фальшивку.
3 варианта из 3+3.
Итого, если скомбинаторить 2*3.

Плз.объясните, чем плох мой ваиант, если после второго взвешивания у меня остаются 4 монеты и я знаю тяжелее или легче фальшивая ?

а как вы это узнали?

Лан, я должен отлучиться. Надеюсь, когда вернусь, решение таки будет опубликовано ;)

← →
OutSidEr (2002-11-26 11:24) [35]

Тогда, начиная со второго взвешивания, нужно комбинировать кучки по частям между собой. Это уже надо с ручкой и бумажкой...

> Kaban © (26.11.02 11:22)
> а как вы это узнали?

Если не было равновесия при первом взвешивании

Берем 4 монеты, которые оказались тяжелее, и взвешиваем их по 2.
1) если равно - нестандартная монета в оставшишся 4 и она легче других
2) неравенство - нестандартная монета среди тех двух, которые тяжелее.

Но так все равно не хватает одного взвешивания. Сорри.

>Manic Mechanic © (26.11.02 10:32)
Сразу дал оптимальное решение, т.е. если бы вместо монет были бы мешочки по 50кг, то он бы гнул спину меньше всех :-)

У меня дежа вю?

Господа, а кто вам сказал, что фальшивая монета тяжелее (или легче) :)

Задача монетами Найти похожие ветки