задача про взвешивание шаров

Timoha

шаров, один "левый", три попытки взвешивания. Определить "левый" шар. Легче он или тяжелее "нормальных", неизвестно. Насколько я знаю, для 11 шаров решение есть. А вот для 12 не получается. Думается, это сделать нельзя. Может, я ошибаюсь? Какие будут соображения ?

galya1

А напиши плиз решение для 11 шаров

Forsit

Задачка известная.Попробую вспомнить.

Timoha

Так, с 11 я поторопился (если честно, мне просто сказали, что для 11 есть, хотя, кажется, я сам когда-то это проверял): утверждение для 11 шаров снимается. Прошу прощения.

galya1

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

kravecnata

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

galya1

Вспомни плизззз а то мне дико интересно

KOHCTAHTA

В одном взвешивании больше одного бита, так как возможны три исхода.

AMALINKA22

3 - 3
1.1Равны по весу - левый в оставшихся пяти.
Взвешиваем 3 из первых шести (они гарантированно нормальные) и три из 5.
1.1.1 Равны по весу - левый в оставшихся двух. Третьим взвешиванием легко его определеям.
1.1.2 Не равны. По тому какая сторона перевесит определяем легче или тяжелее левый шар. Взвешиваем два из подозрительных. Если левый шар среди них, то мы определим какой, т.к. знаем тяжелее он или легче. Если нет - то оставшийся.
1.2 Не равны. Заменям три из шаров с одной стороны на три из 5(нормальных). Взвешиваем.
1.2.1 Равны. Не нормальный в трех замененных. Третьим взвешиванием определяем какой (как см. выше)
1.2.2 Не равны. Ненормальный в трех снятых. Какой определяется аналогично.

Timoha

Решение для 9:
Взвешиваем 2 тройки: 1-ю и 2-ю.
1. Если равенство, то "левый" шар в третьей тройке и как его найти за 2 взвешивания, думаю, понятно.
2. Если неравенство, то заменяем одну из троек (скажем, 2-ю) на третью.
2.1 Если неравенство сохранилось, то "левывй" шар в 1-ой тройке и при этом по отклонению весов мы узнаем, легче или тяжелее шар нормальнго "левый" шар. Следующим взвешиванием находим этот левый шар.
2.2 Если равенство: аналогично 2.1 определяется тройка с "левым" шаром и легче или тяжелее он. Далее понятно.

tinka2302

А два из этих исходов не равноценны, если неизвестно, легче шар или тяжелее?

AMALINKA22

это решение для 11

tinka2302

А в 2.2 у тебя не 4 взвешивания получилось?

Timoha

пока писал про 9, написали про 11....

Max1977

Одно взвешивание- это больше однго бита, так результат может быть такой- тяжелее одна, другая или вообще обе чашки весов равны. Так что изначальная задача (с 12-ю) шарами вроде решается.

kravecnata

Схема такая: делим на три группы по 4, сравниваем две; потом меняем состав групп (есть мнемоническое правило с использованием лат. букв, для каждого из трёх взвешиваний получается более-менее осмысленная пара английских слов); для каждого из 27 (троичная система счисления!) исходов логически мыслим. Подробнее ну так лень... Давай ты сам придумаешь?

Timoha

нет. после 2-х взвешиваний мы в любом случае определяем тройку с "левым" шаром и его массу относительно нормального. далее одного взвешивания достаточно.

Timoha

маза когда мне сегодня говориили про решение, упомянули филологов

Pups12

Помню решение, если известно, легкий или тяжелый "левый шар". А может оно и для неизвестного годится, но что-то не получается.
Насколько помню, надо разделить шары по 3, сначала сравнить 2 троики, если не одинаковые, то в троике с фальшивым шаром надо сравнить 2. Если одинаковые - фальшивый третий. Если разные - тоже известен. Третье измерение нужно на случай, если первые 2 тройки одинаковые.

galya1

Точно
Я ж говорю, что думать вломы

tinka2302

Кстати в 1.1.1 не удастся определить, легче "левый" шар или тяжелее
А нам совсем сказочные результаты обещает

Pups12

Удасться - для 11 правильное решение - читай внимательнее.
Для 12 что-то не придумать, получается, 4 взвешивания нужно.
Вообще задача вроде решена в "Занимательной математике" Перельмана.

AMALINKA22

ну первоначально в задаче не спрашивалось определить тяжелее он или легче поэтому я и не думала.
а про 12 шаров надо делить не на 4-ки, а опять же на тройки.

Timoha

да вот как-то не получается по 3...

AMALINKA22

ой, на 6-ки

tinka2302

Решение поставленной задачи правильное, не спорю - мы находим левый шар. Но определить, легче он или тяжелее остальных, не можем.
Ну еще точнее - в 1.1.1 остается два шара. Взвешиваем один из них и нормальный шар - если кто-то перевесил, то мы все нашли, а вот если ровно - тогда понятно что оставшийся шар - левый, но легче он или тяжелее - непонятно.

tinka2302

А на 6-ки как?

Pups12

Все равно 4 измерения надо.
3 измерения хватает, если известно, легкий или тяжелый левый шар (см. мое решение).

Pups12

Согласен. Это я не дочитал.

gmgm

Шары обозначаем буквами от A до L
1. ABCD - EFGH
2. CDHI - BEJK
3. CFIK - DGHL
Теперь осталось придумать, как переименовать буквы для получения чего-то осмысленного.

IVA030360

да... задача на убой
решение тоже )
имеем 12 монеток
делим 4:4:4, взвешиваем 2 кучки
1) =
фальшивая в 3-й кучке
а в1,2 - все нефальшивые
берём 2 монеты из 3-й и взвешиваем
1.1) =
значит фальшивая в оставшихся 2-х
1.2) !=
фальшивая среди них
знаем среди каких 2-х монет фальшивая, взвешиваем одну из них с заведомо нефальшивой и по результату легко определить какая из них фальшивая
2) !=
пусть 1-я кучка легче, 2-я тяжелее, а 3-я значит нефальшивая.
делим на такие кучки:
1: 3(a)+1(b)
2: 1(c)+3(d)
3: 3(e)+1
взвешиваем следующие кучки: a+c и b+e
варианты расположения фальшивой монеты:
a) результат взвешивания <, т.к. a - лёгкая
b) >
c) >
d) =
имеем следующие варианты:
2.1) <
значит монета в a и она легче, т.к. a из лёгкой кучки
из 3-х монет за 1 взыешивание можно найти фальшивую, зная что она легче
2.2) =
фальшивая в d и она тяжелее, далее так же из 3-х за одно взвешивание
2.3) >
b или c и не знаем тяжелее или легче
2 монетки - за одно взвешивани узнаём какая из них фальшивая
конец

Seka

может есть ошибка, но:
шары abcd, 1234.
abcd=1234 - просто
abcd>1234
1 ab1>cd3
1.1 a>b => a; a<b => b; a=b => 3
2 ab1<cd3
2.1 c>d ...
3 ab1=cd3 ...

gmgm

у меня решение гораздо короче как разбить на группы для каждого взвешивания - можно решить сразу (вне зависимости от результатов предыдущих взвешиваний). А результаты, как несложно убедиться, будут разные для всех возможных вариантов(нет фальшивых монет, "А" легче остальных, "А" тяжелее, "В" легче, "В" тяжелее... "L" легче, "L" тяжелее - всего 25 вариантов)

gmgm

и не только там. помнится была в детстве книжка типа "100 задач" какого-то польского автора... То ли Штокгауза, то ли как-то так...

kravecnata

Кажется, Штейнгауз.

AMALINKA22

фух, ну вы звери....!
у меня после 11 шаров мозги переутомились и отказались дальше действовать адекватно.......

gmgm

ТОЧНО!

Aristei

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

tanuhka3

Эта задача была на матбою Пермь-Челябинск (10 класс) на зональной олимпиаде, никто ее тогда не решил. Автором задачи был некто Рустэм Гусманович Женодаров(кто знает, тот знает). После этого она мне попалась в 11 классе на встрече сборная Москвы- сборная Челябинска (Москва тогда проиграла она была решена, я смогу даже вспомнить как.
Простому смертному решения не придумать, никакие разбиения на группы по 2,3,4,6 не помогут. Эта задача имеет красивое идейное решение...

Nataly-Lilly

Ну как же не помогут, когда выше приведены как минимум два таких решения

lodanap

Монстр... Как распределял?

tanuhka3

задача такая: 14 шаров, 3 взвешивания, определить левый шар.
если 13 шаров и 3 взвешивания, то и сказать еще, легче или тяжелее ли он обычных.
Это не халява!

FreeKill

А я помню такую задачу Женодарова: загадано одно из чисел (1, 2 или 3 как с помощью одного вопроса (варианты ответов да, нет, не знаю) определить, что это за число.

lodanap

Нереально... По крайней мере методом который привел ...

gmgm

в принципе, наверно решаемо - если 13 шаров, то это ровно 27 вариантов (каждый из шаров может быть легче или тяжелее + вариант, что все одинаковые). Но над решением надо еще думать

stm5451080

А Валечка Шаповалова, когда ей было 11, придумала потрясающее решение этой задачи :-)

playback

Она почти так же решается,разница только в последнем взвешивании.

lodanap

Ну приведи решение тогда...

tanuhka3

сказал грамотную идею
осталось додумать аккуратно решение
кто хочет может узнать его у меня, для 14 и 13 шаров..

Seka

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

Seka

что-то я нынче стал слеповат
сверху у тебя было правильное разбиение. я подобное строил часа два, а на решение попроще хватило 15-ти минут.
ты сам придумал ?
Оставить комментарий
Имя или ник:
Комментарий: