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

billic

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

нет. _промежуточные_ взвешивания дают _больше_ информации. Мы не только узнаём, в какой чашке лежит другой шарик(и лежит-ли, 3 варианта), но ещё и легче он или тяжелее(точнее, узнаём не легче/тяжелее, но если левая перевесила, то другой либо тяжелее и в левой, или легче и в правой).

qnikst

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

1. именно ЭТОЙ задачи не было.
2. я доказал, что 2х взвешиваний недостаточно, а достаточно 3х. И то не всегда. Что уже является решением worst cost
3. далее я задал вопрос - а существует-ли более лучшее решение в смысле amortised cost?

2. я доказал, что 2х взвешиваний недостаточно, а достаточно 3х. И то не всегда. Что уже является решением worst cost

молодец, чо... ничего, что в случае до 13 шаров включительно с одним неправильным с неизвестным отклонением 3х достаточно _всегда_?

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

а) Взвешиваешь шары 123 и 456, 789 лежат.
Если вес одинаковый, то сразу выкидываем 123456 и берём 789. У нас есть два взвешивания, но неизвестно в какую сторону отличается шар.
б) Взвешиваешь шары 123 и 789, 456 лежат.
Если вес одинаковый, то выкидываем 123789 и берём 456, при этом если в первый раз 123 было тяжелее, то искомый шар легче и наоборот. Мы знаем в какую сторону отличается вес и у нас одно взвешивание.
Если оба раза весы не уравновешиваются, то шар в 123. При этом если 123 меньше по весу, то искомый шар лёгкий и наоборот. Мы знаем в какую сторону отличается вес и у нас одно взвешивание.

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

При одном взвешивании всё просто. Вешаем 1 и 2. Если одинаковые, то 3. Если разные, то мы знаем в какую сторону отличается вес искомого.

При двух взвешиваниях:
1 и 2. Если одинаково, то искомый шар 3, но мы не знаем тяжелее он, или легче. Нужно будет взвесить 1 и 3 и определить куда перекосит.
Если не одинаково, то тоже вешаем 1 и 3. Если одинаково, то искомый 2, если не одинаково, то искомый 1. Ну и вспоминаем куда перекашивало равновесие.

Таким образом определяем и шар и направление отличия его веса.
Примерно как-то так.

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

Ни в каком. При любых раскладах нужно будет именно три взвешивания.
твоё решение выше не читал. :(

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

Нет. Насколько я знаю в задаче с неопределённым весом есть условие определить в какую сторону отличается этот вес. Для этого потребуется третье взвешивание.

ну и что? Тогда будет точно 3 взвешивания по любому.

случай с 13ю шарами я не рассматривал.

Я собственно именно об этом и сказал.

откуда тогда у тебя 4 взвешивания взялось?

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

То же самое.

Ну объясни как ее решить также (если это тоже самое).

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

более лучшее решение

Математики не дружат с языками? Почему не «самое более лучшее решение»?

Насколько я знаю в задаче с неопределённым весом есть условие определить в какую сторону отличается этот вес.

Для 3 шаров это определяется в 2 шага элементарно.

обычно забывают, что весы имеют 3 состояния, а не 2. Тред не читал

Там же не 3 шара, а 9.
Ну да ладно.
Задача с 13 шарами. Если известно в какую сторону отклонение искомого шара, то в 3 взвешивания решается элементарно. Вешаются 1234 и 5678 шары. Остальные пять шаров не принимают участие. По результатам первого взвешивания получаем задачу для 9-ти шаров и 2-х взвешиваний, которая легко решается. Оптимальную стратегию взвешивания 13 шаров для случая неизвестного отклонения в весе пока не продумывал.

Комментя не читал, дабы натолкнуться на ответ.

Откладываем из 9 3 в сторону. Оставшиеся 6 делим на весах по 3 на чашку. Если весят одинаково, то выкидываем все 6, и вторым (*) взвешиванием кладем на весы два из трех оставшихся: если один весит больше -он тот, кого мы ищем, если равны, то тот, которого не взвесили - искомый. Если на первом взвешивании всё же одна чашка весов перевесила, значит выкидываем шары с более лёгкой чашки и те, что мы отложили. Берем 3 оставшихся и делаем второе взвешивание (*)

ты уже пятый

Надеюсь меня не считали? Я же более усложнённый вариант рассматривал. :)

Задача с 13 шарами. Если известно в какую сторону отклонение искомого шара, то в 3 взвешивания решается элементарно.

Я знаю 3 варианта её решения. Кто продемонстрирует решение с неизвестным отклонением?

За пять взвешиваний решение лёгкое, за четыре... я пока пасс. А есть информация, что за четыре взвешивания она решается?

1) Взвешиваем 2 по 3, определяем где фальшивый шар. 2) Из этой троицы взвешиваем два шара, определяем фальшивый.

А есть информация, что за четыре взвешивания она решается?

Как два пальца абасфальт.