Dark Magus ([info]_darkus_) wrote,
@ 2008-04-17 10:13:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Entry tags:Наука

Ещё раз, что ли, взвесим шары?
Задача про поиск дефектного шара при помощи плечевых весов среди восьми данных шаров нашла неожиданно широкий отклик в сердцах моих читателей. Пришло время рассказать про варианты решения и задать новую задачу для размышления.

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


Этот вариант предложили следующие читатели (перечисляются в алфавитном порядке): [info]az_from_belarus, [info]bartus, [info]dbbeast, [info]gajewski, [info]gorrah, [info]hog_of_bore, [info]karelichus, [info]kladun, [info]krf, [info]man_with_dogs, [info]marilli0n, [info]mrlj, [info]nes_pv, [info]storm_book, [info]suhov, [info]sveigder, [info]yarryozzo, [info]yonsson, [info]yuri_rus, [info]zalex3d.

Второй вариант предполагает на первом шаге взвесить две тройки шаров. После этого взвешивания дефектный шар можно определить либо на следующее взвешивание (если повезёт), либо ещё за два, но особым образом. Опять же, схема приведена на следующем рисунке, на которой также описаны два подметода, разнящиеся с основным методом вариациями на тему перекладывания шаров с чашки на чашку.


Этот вариант предложили следующие читатели: [info]dbbeast, [info]frogstail, [info]lich_phantom, [info]man_with_dogs, [info]rossomyha, [info]upstartn.

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


Итого правильное решение дали 24 человека, причём никто не предложил решение третьим вариантом. Тем не менее, отрадно, что задача так привлекла внимание, хотя она сама по себе достаточно проста (но то ли ещё будет)...

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

Дополнение: Если я не ответил на комментарий (и не раскрыл его), значит в этом комментарии приведён правильный ответ или даны слишком чёткие намёки на то, как решать. Решения задачи планируются к опубликованию в следующий четверг. Тогда же я перечислю всех, кто решил задачу правильно (и каким методом), и кроме того задам новую задачу, ещё более интересную. Также готов дать любые комментарии по приведённым в этом сообщении решениям.

(Post a new comment)


[info]grey_one
2008-04-17 06:22 am UTC (link)
Первый же вариант решения - всё тоже самое что и во взвешиваниях по 4 шара из первой задачи. Если повезёт и первое взвешивание не покажет отклонений - шар сразу найден.

(Reply to this)
По три шарика
[info]grey_one
2008-04-17 07:10 am UTC (link)
132456789

взвесим по три шара
123-456
если они равны - понятно, три шара 789 и два взвешивания.

если неравны.
- пусть первое дало 123/456.
- второе 123/789 и мы ищем среди 123 тот, который тяжелее
- второе 123-789 и мы ищем среди 456 тот, который легче

(Reply to this)

[info]yarryozzo
2008-04-17 07:11 am UTC (link)
Случай с девятью легко сводится в предыдущему варианту (№3): взвешвиаем две четвёрки. Если они уравновешены, то дефективный шарик — в остатке, если нет — то действуем, так сказать, по картинке.

(Reply to this)

[info]trixter_d
2008-04-17 07:58 am UTC (link)
Положим по 4 шара на каждую чашу весов.Если равновесие сохранится,то д-шар - оставшийся.Если изменится,то переходим к третьему варианту предидущей задачи.

(Reply to this)

[info]zalex3d
2008-04-17 07:59 am UTC (link)
2-й вариант (взвешивание по 3) решает эту задачу. Разница лишь в том что при первом взвешивании выявится либо 3 неизвестных и 6 эталонных (за 2 взвешивания находится дефектный), либо 6 неизвестных и 3 эталонных (далее решение ничем не отличается).
3-й вариант (взвешивание по 4) решает эту задачу. При первом взвешивании либо сразу определится дефектный шар, либо дальнейшее решение задачи пойдет по описанному алгоритму

(Reply to this)
по 2 в начале
[info]grey_one
2008-04-17 08:05 am UTC (link)
123456789

1)берём по 2 шара
12-34. определяем в какой четвёрке шаров есть дефектный - это 1234 или 5678 + 9 под подозрением
пусть 12349 - под подозрением а 5678 нормальные

2) берём 3 дефектных и 1 нормальный. 1235.
12-35. значит либо 4 либо 9 с дефектом - выясняется третьим взвешиванием
12/35. значит 12 тяжёлые или 3 лёгкий.

3) берём 2 подозрительных на дефект и сравниваем их. тот, где дефект проявился - нужный. если
дефект не проявился - значит третий дефективный.
1/2. 1 - дефективный
1\2. 2 - дефективный
1-2. 3 - дефективный.

12\35. значит 12 лёгкие или 3 тяжёлый.
см. выше с другим знаком.

(Reply to this)

[info]serge_redfield
2008-04-17 08:33 am UTC (link)
Третий способ, только на первом шаге один шар не взвешиваем.
Если весы в равновесии, то он дефектный, если нет - исключаем оставшийся шар из рассмотрения и переходим к шагам 2 и 3.

(Reply to this)

[info]krf
2008-04-17 08:38 am UTC (link)
1-е взвешивание: сравниваем по два любых шара.
Если вес этих пар не равен, то дефектный шар находится среди этих 4-х шаров и задача сводится к нахождению 1-го дефектного шара из 4-х за 2-а взвешивания при наличии эталонных шаров - как это сделать рассмотрено в предыдущем примере в варианте 1.
Если вес этих пар равен, то то дефектный шар находится среди остальных 5-и шаров и задача сводится к нахождению 1-го дефектного шара из 5-и за 2-а взвешивания при наличии 4-х эталонных шаров.

2-е взвешивание: Откладываем в сторону 2 шара из 5-и (№4 и №5), добавляем к оставшимся 3-м 1 эталонный шар из 4-х (э), получая 4-ку э,1,2,3. Проводим взвешивание - сравниваем э+1 и 2+3
Если вес равен, то дефектный шар находится среди шаров №4 и №5 и задача сводится к нахождению 1-го дефектного шара из 2-х при наличии эталонных (решается сравнением веса любого шара из этих 2-х с эталонным).
Если вес сравниваемых 2-ек не равен, значит дефектный шар находится среди №№1,2,3 - проводим третье взвешивание.

3-е взвешивание: Сравниваем №2 и №3
Если они равны, то дефектный шар - №1
Если они не равны, то №1 - эталонный, а дефектный шар находится среди №2 и №3
При этом:
Если на втором взвешивании э+1 было легче 2+3, то дефектный шар - тот из №2 и №3, который на третьем взвешивании был более тяжелым.
Если на втором взвешивании э+1 было тяжелее 2+3, то дефектный шар - тот из №2 и №3, который на третьем взвешивании был более легким.

(Reply to this)

[info]krf
2008-04-17 08:44 am UTC (link)
А у этой задачи сколько методов решения?

(Reply to this)(Thread)

[info]_darkus_
2008-04-17 08:47 am UTC (link)
Не менее трёх. Я пока всё дерево решений не исследовал за неимением времени...

(Reply to this)(Parent)(Thread)

[info]realurix
2008-04-19 02:26 am UTC (link)
> Я пока всё дерево решений не исследовал за неимением времени...

Мест три (0-Unused,1-Right,2-Left), измерений (позиций) три, итого 27 возможных состояний (троичная система счисления). Несложно заметить, что ответ можно получить только тогда, когда каждому шару присвоено число (отображение возможного пути измерения), которое отлично от остальных чисел остальных шаров. Итого получаем 27*26*25*24*23*22*21*20.

Вопрос: А Вы успеете за свою жизнь исследовать все состояния?

P.S. Это, кстати необходимое условие существования решения. Укажите достаточное.

(Reply to this)(Parent)(Thread)

[info]_darkus_
2008-04-19 06:18 am UTC (link)
Ну что же Вы обо мне так скверно мыслите. Я что, упой автомат? Я эвристиками, всё-так, пользуюсь. Мириадами отсекаю бесполезные ветви дерева решений.

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

(Reply to this)(Parent)(Thread)

[info]realurix
2008-04-19 06:50 am UTC (link)
Сомневаюсь, что все, поскольку не сформулировали достаточное условие. А значит, какие-то решения "просмотрели" мимо.

(Reply to this)(Parent)(Thread)

[info]_darkus_
2008-04-19 03:16 pm UTC (link)
Ну разве достаточное условие должно быть явно сформулировано? Оно у меня в голове есть, ну а то, что я в решении для восьми шаров не указал пару ветвей совершенно неинтересных (и тривиальных) не означает, что я их не обозрел.

(Reply to this)(Parent)(Thread)

[info]realurix
2008-04-19 07:05 pm UTC (link)
По поводу пары это ваше предположение? Кажется мне, что там не парой единиц, а, как минимум, парой сотен пахнет.

(Reply to this)(Parent)(Thread)

[info]_darkus_
2008-04-20 06:57 pm UTC (link)
Да ну. Вы хотели написать «пахнет порядка десяти тысяч»...

(Reply to this)(Parent)

[info]krf
2008-04-17 09:21 am UTC (link)
Кстати, описанный мною выше метод (начиная со 2-го взвешивания) можно использовать как 3-й подметод первого метода из прошлого задания.

А 2-1 подметод 1-го метода из прошлого задания, можно использовать как подметод описанного мною выше метода решения этого задания (начиная со 2-го взвешивания - при нахождении 1-го дефектного шара из 5-и за 2-а взвешивания при наличии 4-х эталонных шаров):

Т.е. 2-е взвешивание: Сравниваем 1+2+3 и э+э+э
Если они равны, то дефектный шар находится среди шаров №4 и №5 и задача сводится к нахождению 1-го дефектного шара из 2-х при наличии эталонных (решается сравнением веса любого шара из этих 2-х с эталонным).
Если они не равны, то дефектный шар находится среди №№1,2,3 + мы получаем информацию о том, в какую сторону по весу отличается дефектный шар от эталонных.

3-у взвешивание: Сравниваем №1 и №2
Если они равны - дефектный №3
Если они не равны - дефектный тот из №2 и №3, который отличается в от другого в ту сторону, в которую отличается дефектный от эталонного (как было выяснено на взвешивании 2).

(Reply to this)

[info]upstartn
2008-04-17 10:17 am UTC (link)
Если я ничего не путаю, то задача с двумя шарами легко решается приведенным Вами подходом №3 к задаче с 8 шарами.
Т.е. взвешиваем, 1234 и 5678, если они равны, то дефектный девятый, если же нет, то задача сводится к ситуации, которую мы имеем в третьем способе, после первого шага

(Reply to this)
Решение.
[info]az_from_belarus
2008-04-17 10:19 am UTC (link)
Делим на три части по три шара.
1. Взвешиваем Ч1 и Ч2 и фиксируем результат.
2. Взвешиваем Ч1 и Ч3 и фиксируем результат.
По первым двум взвешиваниям делается вывод о том, в какой части находится дефектный шар, и характер дефекта - больший или меньший вес. Это достаточно очевидно.
3. Взвешиваем два шара из трех подозрительных. Учитывая результат взвешивания и установленный характер дефекта, указываем на дефектный шар.

(Reply to this)

[info]storm_book
2008-04-17 10:55 am UTC (link)
Поступаем примерно так-же, как и первой задаче.
Взвешиваем две пары(I). При неравенстве - смотрим решение предыдущей задачи.
При равенстве получаем четыре эталонных и пять испытуемых.
Взвешиваем три испытуемых и три эталонных шара(II).
При равенстве
взвешиваем один из оставшихся с эталонным(III). -> решение найдено.
При неравенстве
.
Взвешиваем пару шаров из трех испытуемых(III). Если шары были тяжелее эталонных на взвешивании два, то выбираем более тяжелый, легче - более легкий. Если пара равна - искомый последний.

(Reply to this)

[info]marilli0n
2008-04-17 11:52 am UTC (link)
Так? Вроде ниче не напутал.

1) 1234 и 5678. Если равны, то 9 дефект. Будем считать 1234 тяжелее.
2) 125 и 367. а) равны: дефект 4 или 8; б) 367 тяжелей: дефект 3 или 5; в) 125 тяжелее, шары 3,5 эталонные. Случаи а и б решаются одним взвешиванием.
3) 16 и 57. а) равны: дефект 2; б) 16 тяжелей: дефект 1; 57 тяжелей: дефект 7.

1) 123 и 456. Равны: дефект в 789 (2 взвешивания). Будем считать 123 тяжелей.
2) 12 и 45. Равны: дефект 3 или 6 (1 взвешивание).
3) 14 и 56 - см предыдущий метод.

(Reply to this)

[info]marilli0n
2008-04-17 12:28 pm UTC (link)
1) 12 и 34. Равны: дефект в 56789.
2) 56 и 78. Равны: дефект 9.
3) 57 и 69. См. предыдущие методы.

(Reply to this)

[info]gajewski
2008-04-17 12:35 pm UTC (link)
Разделим все шары на три тройки.

1-е взвешивание. Взвесим две тройки между собой.

Если по весу они равны, то мы получаем шесть эталонных шаров, и далее за два взвешивания определим дефектный (на одной чаше всегда будет эталонный шар, а на другую чашу будем класть по одному шару из оставшейся тройки - за два взвешивания либо будет найден дефектный, либо дефектным будет третий шар, который не взвешивали).

Если по весу они не равны, то пронумеруем шары определенным образом. 1,2,3 - шары из той тройки, которая оказалась тяжелее. 4,5,6 - шары из тройки, которая оказалась легче. 7,8,9 - эталонные шары.

2-е взвешивание. Взвесим шары 1,2,4 и 7,8,9.

Если две тройки шаров равны по весу, то в третий раз взвесим шары 3,5 и 7,8. Если левая чашка окажется тяжелее, то дефектный шар - 3; если легче, то дефектный шар - 5; если чашки уравновесятся, то дефектный шар - 6.

Если чашка с шарами 1,2,4 окажется легче, то дефектный шар - 4 (нам повезло).

Если чашка с шарами 1,2,4 окажется тяжелее, то в третий раз взвесим шар 1 и шар 7. Тогда дефектный шар - 1 (если чашка с ним будет тяжелее), или 2 (если чашки уравновесятся).

(Reply to this)
Решение
[info]rossomyha
2008-04-17 03:10 pm UTC (link)
Копируем второй вариант решения задачи о восьми шарах, т.е. сначала взвешиваем две тройки (123 против 456). Если их веса не равны, то повторяем и остальные шаги -- таким образом, девятый шар остаётся не при делах, и задача сводится к предыдущей. Если же веса двух первых троек равны, то остаётся найти дефектный шар в оставшейся тройке (789), что за два оставшихся взвешивания делается тривиально.

(Reply to this)

[info]dbbeast
2008-04-17 09:57 pm UTC (link)
первый способ смешной: берём 8 шаров и взвешиваем 1234-5678; если весы в равновесии - дефектный N9, иначе - действуем согласно третьему способу для 8 шаров.

второй способ - с тройками: взвешиваем 123-456; если весы не в равновесии - см. второй способ для 8 шаров; если весы в равновесии, определение "дефектного" шара из трёх при неизвестном отклонении по массе за два взвешивания - тривиальная задача, даже "эталон" не нужен.

это что придумал с ходу. над третьим вариантом подумаю (и время есть).

(Reply to this)
Решение-2
[info]rossomyha
2008-04-18 04:08 pm UTC (link)
Взвешиваем 1234 против 5678. Если весы в равновесии, то 9-й шар является дефектным, в противном случае в точности повторяем третий вариант решения задачи о восьми шарах.

(Reply to this)

[info]gorrah
2008-04-19 12:54 am UTC (link)

Вариант 1
(1)
Взвешиваем две пары шаров.
U - 123456789
{12} != {34}
Тогда на втором взвешивании определяем пару, содержащую дефектный шар, а на третьем находим искомый.
Иначе:
(2)
U - 56789
T - 1234
{123} = {567}
Тогда мы определили пару {89}, содержащую дефектный шар, и на третьем взвешивании находим его.
Иначе имеем например:
U - 567
T - 123489
{123} > {567}
Это частный случай двух неравновесных троек, об одной из которых заведомо известно, что все шары в ней эталонные. Т.е. теперь мы знаем, что дефектный шар легче.
Проводим третье взвешивание:
(3)
Если {125} > {346} то дефектный шар {6}.
Если {125} < {346} то дефектный шар {5}.
Если {125} = {346} то дефектный шар {7}.
Случай {123} < {567} рассматривается аналогично.

Вариант 2
Взвешиваем две тройки шаров. Определяем либо дефектную тройку и определяем дефектный шар еще за одно или два взвешивания, либо приходим к варианту с двумя неравновесными тройками из предыдущей задачи. Эта ситуация также разрешается за два взвешивания методами, изложенными в решении предыдущей задачи.

Вариант 3
Взвешиваем две четверки шаров. Если они равновесны - то дефектный шар найден.
В противном случае мы имеем ситуацию первого взвешивания из третьего варианта решения предыдущей задачи.

Других вариантов не нашел.
Правда не сильно и старался.

(Reply to this)

[info]kladun
2008-04-19 12:08 pm UTC (link)
Делим шары на три тройки
1) ABC
2) DEF
3) GHI
взвешиваем тройки 1) и 2)
Если баланс => бракованный в тройке 3), а в тройках 1) и 2) эталонные. Взвешиваем G c эталонным => или он бракованный или бракованный среди H,I. В последнем случае взвешиваем H с эталонным => в случае отсутствия баланса бракованный H, в случае баланса бракованный I

Если в первом взвешивании баланса нет, то тройка 3) эталонная, бракованный среди троек 1) и 2). Запоминаем направление перевеса.
После этого взвешиваем пары AE и DB.
Если баланс => брак в паре СF.
Если перевес в ту же сторону, что при взвешивании троек => брак в паре AD
Если перевес в другую сторону => брак в паре BE

Из найденной пары шаров, содержащей брак, берём любой и взвешиваем с эталонным. В случае перевеса бракованный - взятый шар, в случае баланса бракованный - оставшийся из пары.

(Reply to this)

[info]dbbeast
2008-04-19 01:45 pm UTC (link)
Третий способ:

1. А. 12=34 => {T:1234; U:56789}
Б. 12<>34 => {U:1234; T:56789}
Вариант Б не рассматриваем (решается по аналогии с 8 шарами, способ 1).

Вариант А:

2. I. 45<67 => {T:123489; U:567} - либо 5 легче, либо 6 или 7 тяжелее
II. 45>67 => {T:123489; U:567} - либо 5 тяжелее, либо 6 или 7 легче
III.45=67 => {T:1234567; U:89}

Вариант III - определить один "дефектный" шар из двух (8 или 9) при наличии "эталонного" - тривиальная задача.

Варианты I и II - симметричные, рассмотрим I:

3. 6=7 => {T:12346789; F:5}
6>7 => {T:12345789; F:6}
6<7 => {T:12345689; F:7}

Решение для варианта II - по аналогии.

(Reply to this)

[info]karelichus
2008-04-20 10:33 pm UTC (link)
1. Взвешиваем 1234 и 5678. Из равновесия следует дефектность 9, иначе решение №3 предыдущей задачи.

2. Взвешиваем 123 и 456. Из равновесия следует, что дефектный в группе 789. Сравниваем эталон поочерёдно с любыми двумя шарами из этой группы.
Если же равновесия нет, то смотрим решение №2 предыдущей задачи.

3. Взвешиваем 12 и 34. При отсутствии равновесия смотрим решение №1 предыдущей задачи. Если же 12=34, то дефектный шар в группе 56789.
Взвешиваем 123 и 567:
а) 123 = 567. Дефектный 8 или 9. Сравниваем любой из них с эталоном.
б) 123 > или < 567. Находим знак разницы масс. Сравниваем между собой любые 2 шара из тройки 567.

Эх, рановато Вы все решения рассекретили!..

(Reply to this)

[info]sveigder
2008-04-22 03:10 pm UTC (link)
Ты ж сам подсказку даешь. Взвешиваем по 4 шара на каждой чаше весов. Если весы в равновесии, значит дефектный шар тот, который не на весах. Иначе используем третий вариант.

(Reply to this)

Create an Account
Forgot your login?
Login w/ OpenID
English • Español • Deutsch • Русский…