Сообщений в теме: 20

[Vadziku]

Вот, на экслеровском форуме изящная задачка промелькнула, есть над чем поломать голову  

Задача про 12 шаров и 3 взвешивания
Программист из Львова сказал, что те, кто решает эту задачу за 2 часа принимаются на Лондонскую биржу.
Мы с ним поспорили (в поезде на Москву), что решим эту задачу за час

Решение пришло на 45-й минуте, но так как все к этому времени приняли изрядную дозу пива, доказывали мы друг другу истину до самого утра. Таможенники нас не трогали и относились с пониманием.

Условия:
Есть 12 шаров, 11 одинаковых, 12-й либо тяжелее, либо легче (это неизвестно)
Есть весы, которые бывают в 3-х положениях "больше", "меньше" и "поровну"
Есть 3 взвешивания, которые можно сделать

Необходимо определить какой из шаров - имеет аномальную массу

[udaFF]

Очень просто:
1 взвешивание - на каждой из чашек по 6 шаров,
выкидываем 6 шаров, которые больше (меньше)
2 взвешивание - взвешиваем на каждой из чашек по 3 шара, выкидываем 3 шара, которые больше (меньше)
3 взвешивание - взвешиваем любые два шара, если равно, то третий шар искомый и так далее.

[Da_ReBeL]

2Udaff
ни пайдет... ты ж не знаиш, больше он или меньши... тебе уже панадабицца 4 взвешивания минимум.

[udaFF]

ну тады ой, буду думать :0)

[шрайбикус]

Очень просто:
1 взвешивание - на каждой из чашек по 6 шаров,
выкидываем 6 шаров, которые больше (меньше)
2 взвешивание - взвешиваем на каждой из чашек по 3 шара, выкидываем 3 шара, которые больше (меньше)
3 взвешивание - взвешиваем любые два шара, если равно, то третий шар искомый и так далее.

так ведь загвоздка в том, что

12-й либо тяжелее, либо легче (это неизвестно)

так что неизвестно какие первые 6 шаров вы выкинете, все одинаковые или с тем самым 12-м

[Joe Hollenbeck]

Условия:
Есть 12 шаров, 11 одинаковых, 12-й либо тяжелее, либо легче (это неизвестно)
Есть весы, которые бывают в 3-х положениях "больше", "меньше" и "поровну"
Есть 3 взвешивания, которые можно сделать
Необходимо определить какой из шаров - имеет аномальную массу

1. Если допустить что на каждую сторону весов можно положить только один шар то 3*2=6 => задача нерешаема.
2. Так что допустим что на весы можно класть неопределенное количество шаров.
Вариант с 6 и 6 на первом взешивании мертворожденный.
Пробуем так:
1. 4 и 4 (Допустим что первая четверка тяжелее)
2. первая четверка и оставшиеся невзвешенными 4.
Тут два варианта:
Если равный вес - значит в первом взвешивании более легкий шар во второй четверке.
Если Первая четверка тяжелее - значит в ней более тяжелый шар.
В 1 пункте можно сделать любое допущение - выводы будут аналогичными.
Таким образом после 2х взвешиваний мы получаем 4 шара среди которых есть один аномальный и мы точно знаем тяжелее остальных он или легче.
НО за одно взвешивание узнать который из них ОН я не знаю как.
Так что задачку я не решил
Будем думать дальше...

[Vadziku]

Задачка нетривиальная. Понятно, что надо перегруппировывать шарики, вопрос в алгоритме перегруппировки.

[Joe Hollenbeck]

А вот и решение:
Все как в моем предыдущем варианте но взвешивание производится по 3 шара! Все сходится - ЭВРИКА!!!!!

[Joe Hollenbeck]

Задачку я увидел в 17.35 ответ пришел в голову в 18.05. Даже если не учитывать то, что меня отвлекали на работе, то получается 30 минут - это получше чем 45 минут

[Старая Волчица]

А вот и решение:
Все как в моем предыдущем варианте но взвешивание производится по 3 шара! Все сходится - ЭВРИКА!!!!!

это как это?   а если при первом взвешивании 3+3 вес равный?  

[шрайбикус]

Решил вроде  

надо только сначала пометить шары: 1 2 3 4 5 6 7 8 9 10 11 12

1. (1 2 3 4 х 5 6 7 8) уравнялись - см.2, не уравнялись - см.3

2. (1 2 3 х 10 11 12) уравнялись - искомый ?9, не уравнялись - см.2-2

2-2. Из 2. известно, тяжелее или легче дефектный, потому что 1 2 3 нормальные. Поэтому (10 х 11) уравнялись - дефектный ?11, не уравнялись - дефектный тот, кто ведет себя, как 10 11 12 в 2.

3. Тасуем колоду. 9 10 11 12 - нормальные, взвешиваем теперь (1 6 7 8 х 5 10 11 12). Если перекос весов не изменился, то дефектный или 1 или 5 (см.3-1) Если изменился, то дефектный 6 7 8 (см.3-2), если весы уравнялись, то дефектный 2 3 4(см.3-3)

3-1. взвешиваем (1 х 10) Если равны, то 5, если неравны, то 1

3-2. взвешиваем (6 х 7). Равны - искомый ?8, не равны - тот, кто перекосил, как в п.1.

3-3. взвешиваем (2 х 3) Равны - искомый ?4, не равны - тот, кто перекосил, как в п.1.

блин сколько бумаги исписал  
уж подумал консилиум с секретаршей созвать

[шрайбикус]

надо отдать должное Joe Hollenbeck

он дал кое-какие идеи в своем посте для дальнейших размышлений

итог: полтора часа раздумий с перекурами

[Старая Волчица]

кажется ошибочка вышла...

[шрайбикус]

если вкратце, 4-4, 3 взвеш.- 3 новых, 1-1 ?
у меня так получается...
по времени не скажу - писала письмо (изображала работу), а в уме решала...
правильно?  

немного не так
здесь и важна нумерация шаров для подборки различных комбинаций, при которых можно узнать например тяжелее или легче дефектный шар
короче, перетрудился я  
хотя раньше в детстве увлекался такими задачками

[Старая Волчица]

если вкратце, 4-4, 3 взвеш.- 3 новых, 1-1 ?
у меня так получается...
по времени не скажу - писала письмо (изображала работу), а в уме решала...
правильно?  

немного не так
здесь и важна нумерация шаров для подборки различных комбинаций, при которых можно узнать например тяжелее или легче дефектный шар
короче, перетрудился я  
хотя раньше в детстве увлекался такими задачками

да, написала, потом Ваш ответ прочитала и поняла, где моя ошибка... стереть бесследно не успела      

[шрайбикус]

да, написала, потом Ваш ответ прочитала и поняла, где моя ошибка... стереть бесследно не успела      

ну ничего, ведь правильное решение приходит путем ошибок
а так пусть ваш пост висит памятником, подтверждающим ваши попытки решить, сиречь памятником мозговой разминке  
peace

тему мона закрывать, если кто нибудь не найдет более легкого решения

[Старая Волчица]

ну ничего, ведь правильное решение приходит путем ошибок
а так пусть ваш пост висит памятником, подтверждающим ваши попытки решить, сиречь памятником мозговой разминке  
peace

в смысле, как у Вишневского "Любимая, да ты и собеседник?!... "     peace

сорри за офф

[Vadziku]

А вот и решение:
Все как в моем предыдущем варианте но взвешивание производится по 3 шара! Все сходится - ЭВРИКА!!!!!

А как именно по 3 шара? Решение - в студию  
У aday решение отличается от того что было на экслеровском. Там были группы по 4, правда группы по 4 позволяют различить 13 шаров, и это теоретический предел.

[шрайбикус]

У aday решение отличается от того что было на экслеровском. Там были группы по 4, правда группы по 4 позволяют различить 13 шаров, и это теоретический предел.

но ведь правильно я решил, неважно по 3 или 4  
можете опубликовать решение экслеровского форума?
спасибо

[Vadziku]

У aday решение отличается от того что было на экслеровском. Там были группы по 4, правда группы по 4 позволяют различить 13 шаров, и это теоретический предел.

но ведь правильно я решил, неважно по 3 или 4  
можете опубликовать решение экслеровского форума?
спасибо

Да кто спорит - правильно. Я просто сказал, что решение другое.