Как решить задачу?

как я понял, мы с Вами разные задачи решаем, эту, за 2 взвешивания с одним тяжелым шаром решили сразу - а ту, где неизвестно тяжелее или легче и за 3 взвешивания в треде почему-то решить не смогли. именно её решение у меня написано.

понятно, что не смогли - когда мы взвешиваем 3 шарика, то та чашка, которая _тяжелее_ содержит нужный шарик. Если мы знаем, что он тяжелее. А если не знаем, то и ответа это взвешивание не даст. Придётся ещё одно сделать, что-бы сравнить любой из взвешенных шариков с не взвешенным. Условие:

A == B
B != C

да, нам понадобится 1 взвешивание с вероятностью 1/3, и 2 взвешивания с вероятностью 2/3. Т.о. понадобится 1+2/3 взвешиваний для 3х шариков.

ну правильно, если x != y - то мы делаем ещё одно взвешивание, через которое мы не только узнаем, в которой кучке шарик, но и то, тяжелее он или легче, в итоге нам нужно либо 2 взвешивания кучек и одно шариков, либо одно кучек и 2 шариков.

а зачем тут вероятность - я не знаю =(

billic

ну правильно, если x != y - то мы делаем ещё одно взвешивание, через которое мы не только узнаем, в которой кучке шарик, но и то, тяжелее он или легче, в итоге нам нужно либо 2 взвешивания кучек и одно шариков, либо одно кучек и 2 шариков.

неправильно. Возможно нам понадобится всего 2 взвешивания: к примеру если мы взяли 2 кучки с одинаковыми шариками (другой шарик в третей кучке), а потом два одинаковых шарика из третьей кучки. Но нам может понадобится и 4 взвешивания.

а зачем тут вероятность - я не знаю =(

здесь почитай: http://ru.wikipedia.org/wiki/Математическое_ожидание

По условию, шарики с виду одинаковые, и значит мы кладём на весы их в случайном порядке. Проще говоря, если мы проведём 1 000 000 тестов с тремя шариками, то нам потребуется примерно 1 666 666 взвешиваний. Т.е. в среднем 5/3 взвешиваний. Ну а т.к. в одном опыте нам нужно 2 теста, то получаем 3 333 333 взвешиваний на 1 000 000 опытов. Или 10/3 взвешиваний на опыт.

Ну и после этого не надо мне рассказывать, что программеру математика не нужна. :-)

а, ну да... блин, запутали меня. тут тесты зависимые. Т.е. с вероятностью 1/3 мы узнаём, что шарик в третьей кучке, и нам ещё понадобится одно взвешивание с вероятностью 1/9 или 2 взвешивания с вероятностью 2/9. Т.е.

1/9 - 2 взвешивания
2/9 - 3 взвешивания

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

Для симметричного случая симметрично.

Таким образом нам надо провести 5/3+1 взвешивание, или 8/3 взвешиваний на опыт.

опять ошибся (:

для второго случая (вероятность 3/9) имеем 3 взвешивания, как и для третьего. Итого, 8/9 это 3 взвешивания, и 1/9 это 2.

В итоге 26/9 = 2.88888...

Вроде так правильно.

ппц... спросони не могу решить задачку для второго класса ): Вправду - старый стал совсем.

извини, конечно, но я прочитал по диагонали (=

Но нам может понадобится и 4 взвешивания.

в каком случае?

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

в каком случае нам придётся делать 4 измерения-то?

Обязательное условие: шар аномальный и неизвестно он тяжелее или легче. Решение задачи очень красивое.

интересно какое? Ты из трёх шаров меньше чем за 2 взвешивания не сможешь найти нестандартный. Эта неопределённость портит всю малину. Систему из 13 шаров с известным отклонением веса одного шара можно решить за 3 взвешивания тремя разными способами.

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

А вот с этого места по-подробнее... я зпсываю :)

ну так выше же у меня написан алгоритм, что с ним не так? %)

billic

в каком случае нам придётся делать 4 измерения-то?

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

Как решить задачу? (комментарий)

а, сказывается, что я по-диагонали читал ^_^

полагаю, мы сошлись во мнении? (=

да, только 1/9 случаев, когда нам стало известно после двух измерений мы знаем какой шарик аномальный, но не знаем в какую сторону. но так как у нас остаётся ещё одно измерение можно исправить и это ^_^

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

billic

взвешиваем две кучки из трёх шаров.

если кучки равны - то остается одна,
взвешиваем два шара из неё,
если равны - возвращаем третий
если не равны - то
взвешиваем с оставшимся один из имеющихся.
если не равны - значит тот шар, который не трогали,
если равны - значит тот шар, который убрали.

если кучки не равны - то
взвешиваем оставшуюся кучку с той, которая тяжелее
если равны - то (1. шарик легче, 2. он в более легкой кучке)
взвешиваем два шарика из легкой кучки
если равны - возвращаем третий
если не равны - то возвращаем более легкий.
если не равны - то (1. шарик тяжелее, 2. он в более тяжелой кучке)
взвешиваем два шарика из лёгкой кучки
если равны - возвращаем третий
если не равны - возвращаем более тяжелый

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

ну у меня простым методом получилось 2.88888... взвешиваний. У вас - 3.0. Смысл?

Хотя можно наверное и что-то придумать, или доказать, что моё решение лучшее.

В принципе, первое взвешивание делит область из 9и решений на 3 равные части.

Первая часть - это когда весы в равновесии. Очевидно, что в этом случае, мы получаем 1/3 информации для решения этой задачи - мы узнали только нужную кучку, и всё. теперь нам остаётся только одно - выкинуть 6 шариков с весов, ибо не нужны. Останутся 3. Из них можно взять только 2. Опять возможно 3 равновероятных исхода, однако эти исходы неравноценны - если весы опять в равновесии, то задача уже решена всего за 2 взвешивания. Мы правда не узнали, легче или тяжелее шар, но это и не нужно. Если не в равновесии, нам по любому надо делать ещё взвешивание.

Вторая часть - это если левая тяжелее. Теперь мы знаем, что:
1. в третей кучке нет нужного
2. либо нужный шар лежит слева и тяжелее, либо он справа и легче

Далее я предлагаю сравнивать эталонную третью кучку (в которой нет нужного) с первой, что-бы выяснить
3. кучки равны, а следовательно нужный шарик лежал справа(1), и он легче(2)
4. первая(левая) тяжелее, а следовательно шарик слева(1) и тяжелее
5. первая(левая) легче, но такого не может быть. Что говорит о том, что теоретически можно распилить шарики таким образом, что-бы получить из этого теста не 2 результата, а три. Вот как это сделать(и можно-ли) - сами думайте :)

billic

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

не «мы», а ты. А вот я найду нужный шарик иногда(1/9) за 2, а иногда(8/9) за 3 взвешивания. Что безусловно лучше. Мало того, мой метод не оптимальный, ибо в 2/3 случаев я получаю от своих весов слишком мало информации.

Это решение для 9 шаров с неопределённым отклонением веса одного шара в 3 шага. Я могу это решить ещё проще. А привести решение для 13 шаров с таким же условием?

не «мы», а ты. А вот я найду нужный шарик иногда(1/9) за 2, а иногда(8/9) за 3 взвешивания

пардон, а у меня разве не так же? О_о

взвешиваем две кучки из трёх шаров.

если кучки равны - то остается одна,
взвешиваем два шара из неё,
если равны - возвращаем третий

те же самые 2 взвешивания в том же случае, так что та же самая вероятность %)

Attila

Я могу это решить ещё проще.

реши. :)

да, «проще» не нужно. нужно лучше. Выше я уже доказал, что 2х взвешиваний недостаточно для всех случаев, как минимум в 2/9 случаев нужно 3. Остаётся ещё 6/9 случаев.

я не говорил, что выдам решение этой задачи. я говорю, что в цитируемом мной сообщении собеседник сдался пытаясь решить эту. %)

billic

те же самые 2 взвешивания в том же случае, так что та же самая вероятность %)

а, ну да. невнимательно прочитал. однако,

взвешиваем две кучки из трёх шаров.

если кучки равны - то остается одна,
взвешиваем два шара из неё,
если равны - возвращаем третий

а легче или тяжелее этот шарик? нам не известно.

billic

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

т.ч...

надо наверное попробовать во время второго взвешивания брать сразу по 1 или по 2 шарика, а не по 3. Может в этом случае, при должном выборе шариков, будет возможно 3 результата. А может и нет.

Attila

А привести решение для 13 шаров с таким же условием?

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

а легче или тяжелее этот шарик? нам не известно.

а разве в твоём случае при попадании на вариант с двумя взвешиваниями мы знаем тяжелее он или легче?

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

т.ч...

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

billic

а разве в твоём случае при попадании на вариант с двумя взвешиваниями мы знаем тяжелее он или легче?

нет конечно. но в условии задачи это вроде и не требуется.

Меня больше другое интересует: если более оптимальный метод? И если нет - почему?

надо наверное попробовать во время второго взвешивания брать сразу по 1 или по 2 шарика, а не по 3.

в таком случае можно напороться на 4 измерения - если менять один - то можно попасть, когда уравновесятся чаши - 1/6, но в остальных случаях придётся делать разделять оставшиеся 5, а это минимум на 2 замера. если менять два - то тут придётся с вероятностью 1/3 измерять ещё один раз и 2/3 ещё два раза, так что вариант менять меньше, чем 3 шарика несколько непрактичен, как я понимаю.

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

но это не тянет на доказательство, наверное.

Cancellor

Детишек готовят к невесомости? Ну тогда вместо весов должна быть центрифуга

не нужно.
Ставим один идеально сферический и идеально упругий шарик идеально посередине идеальной сферы (в идеальном вакууме конечно).
Кидаем второй шарик на первый
Шарики разлетаются по сторонам. Тот шарик, который достиг стенки сферы раньше и является более лёгким
профит

< Меня больше другое интересует: если более оптимальный метод? И если нет - почему?

а случайно не очевидно, что первый шаг должен быть делением на 3 группы? если так - то я не вижу других, не описанных возможностей %)

ну у нас остаётся 3+3 шарика, причём нам известно:
1. нужный шарик у нас есть среди шести
2. либо он слева и тяжелее (левая чашка перевешивает), либо справа и легче.

дальше вариантов много, для всех надо считать вероятности. Мне лениво. Однако, хочу заметить, что подобные задачи часто встречаются в программировании. ИЧСХ, если будет тут маловероятный вариант в 4 взвешивания, однако _в среднем_ взвешиваний будет меньше 2.88888, то мне это решение понравится больше.

Решение задачи для 9 шаров с одним неопределённым в 3 шага.
ШАГ1:делим всё на 3 кучи по 3 шара. берём две кучи и сравниваем их на весах, если вес равный, значит нестандартный шар в отложенной тройке и определяется за 2 шага элементарно.
ШАГ2:Если вес не равный, запоминаем (например) тяжелую тройку, снимаем её кладём на её место отложенную, если коромысло выравнялось, значит шар тяжелый и находится в тяжелой тройке, если осталось в прежнем положении, значит шар лёгкий и находится в лёгкой тройке.
ШАГ3: Берём ту тройку, в которой нашли нестандартный шар и элементарно находим тяжелый или лёгкий шар в зависимости от результата на ШАГЕ2

billic

а случайно не очевидно, что первый шаг должен быть делением на 3 группы?

не очевидно. Можно например взять по 1 шарику. Тогда в 2/9 случаев мы получаем ответ сразу за 2 взвешивания, вот только это тоже явно не оптимальный алгоритм, по той причине, что второе взвешивание даст нам тоже только 2 результата. Кроме того, даже в этом случае мы ещё и узнаем дополнительную информацию, которая нам не нужна. Ну я уже молчу о том, как мы будем узнавать 1 шарик из 7и, в случае равновесия (вероятность 7/9). Для 2+2 шарика картина получше, но всё равно 3+3 ещё лучше.

Можно попробовать и 4+4, тогда 1/9 это ответ за 1 взвешивание

или потом выбираем 2+2. В случае равновесия - мы не ту кучку взяли

В случае не равновесия имеем 1+1 (3 взвешивания, вероятность 4/9),

Или 4 взвешивания, вероятность 4/9

Итого 29/9 == 3.222222 взвешиваний.

извините, конечно, но чем это отличается от двух, предложенных ранее вариантов?

Attila

Решение задачи для 9 шаров с одним неопределённым в 3 шага.

дык я тоже самое написал.

Attila

делим всё на 3 кучи по 3 шара. берём две кучи и сравниваем их на весах, если вес равный, значит нестандартный шар в отложенной тройке и определяется за 2 шага элементарно.

не всегда за 2. Если на втором шаге равновесие, то третьего шага не нужно.

А теперь докажи, что это решение оптимально.

извините, конечно, но чем это отличается от двух, предложенных ранее вариантов?

Да ничем. Я всё жду решения для 13-ти шаров. И чуйствую уже не дождусь :)

теперь я Вас понял.

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

а, я понял.

у Вас ещё хуже с восприятием собеседника, нежели чем у меня.

А теперь докажи, что это решение оптимально.

а что понимается под оптимальностью решения и зачем это вообще нужно?

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

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

Attila

Да ничем. Я всё жду решения для 13-ти шаров. И чуйствую уже не дождусь :)

может сначала решим для 9и? Кстати, посмотрите на сабж - вопрос был не «решите задачу», вопрос был КАК решить? Ваше решение - не оригинальное, не первое, и даже без доказательства оптимальности.

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

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

и речь идёт не о худшем случае решения, а о самом решении в целом, да и последнее защищаемое решение было приведено в пример, как я понимаю.

13

а 13 за сколько надо? С 12-ю за три вроде решил не особо напрягаясь

qnikst

а что понимается под оптимальностью решения

ну представьте, что Ваша работа заключается в решении таких задач. Точнее взвешивают негры, вы только придумываете алгоритм. У вас есть Over9000 негров, и каждый за день может проделать 100500 взвешиваний. Время каждого взвешивания фиксировано и известно.

qnikst

и зачем это вообще нужно?

негров у меня нет, однако есть компьютеры, которые тоже принимают решения. Типа

if(x < y)
 ...;
else if(x == y)
 ...;
else
 // x > y
 ...;

ну представьте, что Ваша работа заключается в решении таких задач. Точнее взвешивают негры, вы только придумываете алгоритм. У вас есть Over9000 негров, и каждый за день может проделать 100500 взвешиваний. Время каждого взвешивания фиксировано и известно.

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

и зачем это вообще нужно?

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

тоже за 3.

lazyklimm

С 12-ю за три вроде решил не особо напрягаясь

как я понимаю, с 12ю за 3 будет оптимальным решением, причём оптимальность ИМХО несложно доказать. А для 13и очевидно 3х будет мало, и должно быть 4 (видимо). А вот сколько в среднем - затрудняюсь сказать.

qnikst

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

мда... Кстати, тут решений немного, около <100, причём функцию качества я уже ввёл. Т.ч. решить легко, но это уже читерство.

qnikst

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

не, оптимальность доказать таки можно. Фишка в том, что тут не только неизвестен шарик, но и неизвестно отклонение. И хотя в конце оно нам и не нужно, но оно прямо влияет на результат взвешиваний. По нашей схеме мы не только знаем после 2х взвешиваний номер группы, но и отклонение. И это позволяет нам обойтись всего ещё одним взвешиванием.

Но решение может быть и не оптимальным, ибо от второго взвешивания мы могли-бы получить _больше_ информации.

по Вашему критерию один вариант с 4-мя взвешиваниями (4* 1/9) стоит двух вариантов с 2-мя (2 * 2/9). таким образом необходимо найти решение, в котором хотябы будет 3 варианта с двумя шарами и один с 4. я правильно понял?

ты, кстати, знаешь разницу между amortised cost и worst-case cost, задача была на worst-case, зачем ты изменил задачу (при этом явно об этом не написав) стал требовать от всех её решения?