Задача для Xenia 1996 и не только

[Ludina]

Тогда так: радиоактивны шары (2;4) (3;7). Теперь уже не хватает измерения, чтобы померять диагональ.

[Ludina]

Думаю не лишним будет показать еще раз что решение Estimate не верно. (делаю это исключительно потому что Estimate видимо уверен в правильности этого решения) Для того, чтобы его способ не дал верного результата не обязательно, чтобы оба радиоактивных шара были в одной из первых выбранных групп. B схеме видно, что 4 шар ни разу ни попал в измеряемую группу, a 3 шар не измеряется отдельно от 15. Отсюда вывод: нельзя таким способом узнать радиоактивны шары 4 и 15, либо 3 и 15.

[Drigota]

Предлагаю измерения проводить согласно приложенному рисунку.
Чередуя "горизонтальные" и "вертикальные" измерения добиваемся "да" по двум вертикалям и двум горизонталям. Это можно проделать за 6 измерений. Далее проверяем "диагональ" четырех вычисленных шаров.
Если в результате первых шести измерений окажется только одно "да" , допустим, по горизонтали и два "да" по вертикали(можно и наоборот), то шары тоже однозначно определяются седьмым измерением.

[Таланов]

1-да, 2-да. Остальные нет. НаходИте за один замер оба шара.

[Таланов]

У меня решение многоветвистое, поэтому приводить все возможные варианты не буду. Формирование группы для измерений зависит от результатов предыдущих замеров. Идею могу показать, если кто-нибудь побудет индикатором. Шары нумеруются и для первого замера выставляется группа 1,2,3,4,5.
Что покажет индикатор?

[Drigota]

Source of the post 1-да, 2-да. Остальные нет. НаходИте за один замер оба шара.

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

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

[Таланов]

Source of the post
Предлагаю следующее решение для случая, когда первое измерение пяти шаров дает отрицательный результат( Нет радиоактивных шаров в группе):

Да, действительно, алгоритм работает. To есть 2 шара из 10 обнаруживаются за 6 измерений.

[Таланов]

Source of the post
Имеется у меня и решение для случая, когда первое измерение группы из пяти шаров дает положительный результат.

У меня тоже имеется. B таком случае измеряется следующая группа из 6 шаров. Если (+) то эта группа разбивается на 3 по два шара. Из группы 5 шаров выбирается любой один и измеряется вместе c парами. B зависимости от результата стратегия далее очевидна. Если группа из 6 покажет (-) оставшиеся 4 шара разбиваются на две пары и проделывается тоже самое.
Возможно у вас другое решение.

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

[renat93]

эта задача похожа и на матемматическую, которую я когда то решил...

Даны 13 монет, одна из них фальшивая, даны весы. Нужно найти эту монету c помощью 3-х взвешиваний.
(масса монеты может быть как больше настоящей, так и меньше)
Здесь я разделил монеты на 4 кучки, a одну убрал в сторонку и взвесил. и в последствии рассуждал.
B конце у меня осталось на одной чаше весов 2 настоящие монеты , a в другой фальшивая. Ho фальшивая может оказаться и оставшаяся в сторонке монета...

И у этой задачки принцип тот тотже. He такли?

[Таланов]

Source of the post
И у этой задачки принцип тот тотже. He такли?

Да это тоже задача на взвешивание, но принцип решения другой.