|
|
задача
02.12.2002 23:58
|
|
|
12 шаров, один "левый", три попытки взвешивания. Определить "левый" шар. Легче он или тяжелее "нормальных", неизвестно. Насколько я знаю, для 11 шаров решение есть. А вот для 12 не получается. Думается, это сделать нельзя. Может, я ошибаюсь? Какие будут соображения ?
|
|
|
Painkiller
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 29.08.2002
|
|
Сообщений: 3012
|
|
Из: nowhere
|
|
Рейтинг: 20
|
|
|
А напиши плиз решение для 11 шаров 
|
:::
:::
::: |
|
|
bay
|
|
|
|
|
|
|
|
|
Рег.: 06.11.2002
|
|
Сообщений: 38424
|
|
|
|
Рейтинг: 10923
|
|
|
Задачка известная.Попробую вспомнить.
|
|
|
|
|
Так, с 11 я поторопился (если честно, мне просто сказали, что для 11 есть, хотя, кажется, я сам когда-то это проверял): утверждение для 11 шаров снимается. Прошу прощения.
|
|
|
Painkiller
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 29.08.2002
|
|
Сообщений: 3012
|
|
Из: nowhere
|
|
Рейтинг: 20
|
|
|
Вот что я слышал очень давно от какого-то товарища
3 взвешивания - это 3 бита информации
больше 8 чисел тремя битами не кодируется
поэтому больше чем для восьми задача неразрешима
не знаю насколько это правдоподобно
думать лень
|
:::
:::
::: |
|
|
sonte
|
|
|
|
|
|
|
|
|
Рег.: 29.08.2002
|
|
Сообщений: 1077
|
|
Из: this country
|
|
Рейтинг: 461
|
|
|
Вспоминать решение пока лень, но ответ следующий (предполагается взвешивание на чашечных весах без гирь).
Для 12 монет - можно указать фальшивую и сказать, легче она или тяжелее, для 13 - можно указать фальшивую, но нельзя сказать, легче она или тяжелее остальных.
|
|
|
Painkiller
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 29.08.2002
|
|
Сообщений: 3012
|
|
Из: nowhere
|
|
Рейтинг: 20
|
|
|
Вспомни плизззз а то мне дико интересно 
|
:::
:::
::: |
|
|
steam
|
|
|
|
(172.16.1.153)
|
|
|
|
|
|
|
|
|
|
|
Рейтинг: 3392
|
|
|
В одном взвешивании больше одного бита, так как возможны три исхода.
|
|
|
Vilka
|
|
|
|
|
|
|
|
|
Рег.: 08.11.2002
|
|
Сообщений: 2565
|
|
|
|
Рейтинг: 390
|
|
|
1. 3 - 3
1.1Равны по весу - левый в оставшихся пяти.
Взвешиваем 3 из первых шести (они гарантированно нормальные) и три из 5.
1.1.1 Равны по весу - левый в оставшихся двух. Третьим взвешиванием легко его определеям.
1.1.2 Не равны. По тому какая сторона перевесит определяем легче или тяжелее левый шар. Взвешиваем два из подозрительных. Если левый шар среди них, то мы определим какой, т.к. знаем тяжелее он или легче. Если нет - то оставшийся.
1.2 Не равны. Заменям три из шаров с одной стороны на три из 5(нормальных). Взвешиваем.
1.2.1 Равны. Не нормальный в трех замененных. Третьим взвешиванием определяем какой (как см. выше)
1.2.2 Не равны. Ненормальный в трех снятых. Какой определяется аналогично.
|
"вилкам велкам!" - надпись на розетке. |
|
|
|
|
Решение для 9:
Взвешиваем 2 тройки: 1-ю и 2-ю.
1. Если равенство, то "левый" шар в третьей тройке и как его найти за 2 взвешивания, думаю, понятно.
2. Если неравенство, то заменяем одну из троек (скажем, 2-ю) на третью.
2.1 Если неравенство сохранилось, то "левывй" шар в 1-ой тройке и при этом по отклонению весов мы узнаем, легче или тяжелее шар нормальнго "левый" шар. Следующим взвешиванием находим этот левый шар.
2.2 Если равенство: аналогично 2.1 определяется тройка с "левым" шаром и легче или тяжелее он. Далее понятно.
|
|
|
Edward
|
|
|
|
(172.16.4.30)
|
|
|
|
|
|
|
|
|
|
|
Рейтинг: 3392
|
|
|
А два из этих исходов не равноценны, если неизвестно, легче шар или тяжелее?
|
|
|
Vilka
|
|
|
|
|
|
|
|
|
Рег.: 08.11.2002
|
|
Сообщений: 2565
|
|
|
|
Рейтинг: 390
|
|
|
это решение для 11
|
"вилкам велкам!" - надпись на розетке. |
|
|
Edward
|
|
|
|
(172.16.4.30)
|
|
|
|
|
|
|
|
|
|
|
Рейтинг: 3392
|
|
|
А в 2.2 у тебя не 4 взвешивания получилось?
|
|
|
|
|
пока писал про 9, написали про 11....
|
|
|
Wass
|
|
old hand
|
|
|
|
|
|
|
Рег.: 23.10.2002
|
|
Сообщений: 897
|
|
|
|
Рейтинг: 1236
|
|
|
Одно взвешивание- это больше однго бита, так результат может быть такой- тяжелее одна, другая или вообще обе чашки весов равны. Так что изначальная задача (с 12-ю) шарами вроде решается.
|
|
|
sonte
|
|
|
|
|
|
|
|
|
Рег.: 29.08.2002
|
|
Сообщений: 1077
|
|
Из: this country
|
|
Рейтинг: 461
|
|
|
Схема такая: делим на три группы по 4, сравниваем две; потом меняем состав групп (есть мнемоническое правило с использованием лат. букв, для каждого из трех взвешиваний получается более-менее осмысленная пара английских слов); для каждого из 27 (троичная система счисления!) исходов логически мыслим. Подробнее ну так лень... Давай ты сам придумаешь?
|
|
|
|
|
нет. после 2-х взвешиваний мы в любом случае определяем тройку с "левым" шаром и его массу относительно нормального. далее одного взвешивания достаточно.
|
|
|
|
|
маза когда мне сегодня говориили про решение, упомянули филологов ))
|
|
|
Nuke
|
|
sir
|
|
|
|
|
|
|
Рег.: 25.10.2002
|
|
Сообщений: 1080
|
|
Из: Москва
|
|
Рейтинг: 11
|
|
|
Помню решение, если известно, легкий или тяжелый "левый шар". А может оно и для неизвестного годится, но что-то не получается.
Насколько помню, надо разделить шары по 3, сначала сравнить 2 троики, если не одинаковые, то в троике с фальшивым шаром надо сравнить 2. Если одинаковые - фальшивый третий. Если разные - тоже известен. Третье измерение нужно на случай, если первые 2 тройки одинаковые.
|
Quis сustodiet ipsos custodies |
|
|
Painkiller
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 29.08.2002
|
|
Сообщений: 3012
|
|
Из: nowhere
|
|
Рейтинг: 20
|
|
|
Точно
Я ж говорю, что думать вломы
|
:::
:::
::: |
|
Список
Плоский
Дерево
