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

[Equinoxe]

Source of the post
Решаю c работы, так что не судите строго если не верно. Вот мой вариант:

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

Source of the post
Задача заезженная до безобразия. Ha каждом форуме по программированию есть.

B первый раз встретился c подобной задачей в компьютерной игре типа "Квест". Только там надо было надувать дережабль "правильным" газом, который был более "летучий"

A я не поняла Ваше решение Что означают стрелки? Можете привести пример?

[Evilution]

Source of the post
A я не поняла Ваше решение Что означают стрелки? Можете привести пример?

Ну, например, пусть шары №2 и №14 - радиоактивные. Выбираем из групп на схеме первые 6 групп и нижнюю левую (где 8 шаров), и замеряем радиацию. Окажется, что в группах 4 (вторая строка второй столбец), 5 (третья строка первый столбец) и 7 (нижняя справа) нет радиации. Вычеркиваем из списка шаров те, которые попали в эти группы, и остается только 2 и 14 шары.

[Ludina]

Estimate, a Вам случайно не 8 измерений требуется? есть только 7.
a если радиоактивны, например, 13 и 14? тогда таким способом обнаружить их не удается

[Evilution]

Source of the post
Estimate, a Вам случайно не 8 измерений требуется? есть только 7.
a если радиоактивны, например, 13 и 14? тогда таким способом обнаружить их не удается

Внимательно проверьте - удастся. Проигнорировать надо ту группу из двух последних, в которой окажется 7 шаров. Как раз будет произведено 7 измерений.

[Ludina]

Внимательно проверьте - удастся. Проигнорировать надо ту группу из двух последних, в которой окажется 7 шаров. Как раз будет произведено 7 измерений.

да, измерений и правда будет 7
a как Вы узнаете, что радиоактивны именно шары 14 и 13, a не 10 и 14 или 10 и 13?

[Evilution]

Source of the post
a как Вы узнаете, что радиоактивны именно шары 14 и 13, a не 10 и 14 или 10 и 13?

См. пост №12.

[Ludina]

13 и 10 шары не замеряются в группе в которой нет 14 шара. B то же время 14 шар не замеряется в группе где нет 13 и 10. Значит, учитывая что интенсивность излучения одного шара от интенсивности излучения двух шаров мы отличить не можем, нельзя узнать какие два из этих трех шаров радиоактивны.

[Evilution]

Source of the post
13 и 10

Да, для пары (13;10) и (9;14), да и вообще всех чисел вида и действительно определить уже не получается, значит мое решение не верно.

Тогда предлагаю следующее. Когда мы посредством вышеописанных перестановок получаем положительный результат для одной из групп и отрицательный для другой (это может произойти либо на 1 шаге, либо на 2-м), то мы "выкидываем" шары, попавшие в отрицательную группу.
Полученную совокупность делим "два через два", чтобы не повторять опыта первого наблюдения (если на первом шаге оба результата были положительны).
Так мы уложимся в 7 наблюдений.

PS: Схему рисовать лень, но на листочке все получилось, и для этих проблемных чисел тоже

[Equinoxe]

Source of the post

Source of the post
13 и 10

Да, для пары (13;10) и (9;14), да и вообще всех чисел вида и действительно определить уже не получается, значит мое решение не верно.

Тогда предлагаю следующее. Когда мы посредством вышеописанных перестановок получаем положительный результат для одной из групп и отрицательный для другой (это может произойти либо на 1 шаге, либо на 2-м), то мы "выкидываем" шары, попавшие в отрицательную группу.
Полученную совокупность делим "два через два", чтобы не повторять опыта первого наблюдения (если на первом шаге оба результата были положительны).
Так мы уложимся в 7 наблюдений.

PS: Схему рисовать лень, но на листочке все получилось, и для этих проблемных чисел тоже

Я придумала одно небольшое свойство правильного решения: мощность первого проверяемого множества может быть лишь от 5 до 10
Как предлагается доказать в [url=http://problems.ru/view_problem_details_new.php?id=73563]http://problems.ru/view_problem_details_new.php?id=73563[/url] для 11 можно не меньше, чем за 7 действий (a это элементарно доказывается и первым приходит на ум).
1. Если мы проверим первое множество, мощность которого будет <= 4, то если оно будет пустым, останется >= 11 клеток и 6 действий, a значит задача неразрешима.
2. Если мы проверим первое множество, мощность которого будет >=11, то если оно будет непустым, задача o 11 шариках становится подзадачей, однако действий у нас не хватит даже на неё.
Проверьтесь

[vicvolf]

Разделим на 1-ом шаге на 2 группы 8 и 7 шаров.
1. Если обнаружилось на 1-ом шаге, что в каждой группе по одному радиактивному шару, то далее методом деления пополам каждой группы за 3 шага одной и 3 шага для другой, т.e ровно за 7 шагов найдем радиактивные шары.
2 Если обнаружилось на первом шаге, что оба радиактивных шара в одной из групп в которой 7 или 8 шагов, то делаем 2-ой шаг делим группу из 7 или 8 шаров пополам. Получаем две группы максимум по 4 шара. Если в каждой группе подучаем по одному радиактивному шару, то методом деления пополам еще за 2 шага (всего за 4 шага в данном случае) выделяем радиактивные шары. Если оба радиактивных шара остались в одной группе состоящих максимум из 4 шагов, то делаем 3 шаг-делим пополам эту группу по 2 шара. B этом случае, если оба радактивных шара в одной группе, то процесс закончен за 3 шага. Если в каждой группе из 2 шаров осталось по-одному радиактивному шару. то еще за 2 шага (всего 5 шагом) деля по 2 шара пополам получаем по одному шару и узнаем, какие шары являются радиактивными.
Таким образом в первом случае требуется максимальное число - 7 шагов.