Сообщения

1

Головомойки и задачки / Re: Задачи на поиск радиоактивных шаров

« : 02 Май 2021, 12:09:50 »

А вот как на счет решить задачу "3 шара из 9 за 7 измерений" ?

Вроде бы нашел элегантное решение подобное "2 из 15 за 7" описанное выше (3 первые измерения с 1м общим), но потом понял, что оно к сожалению неверное


Так же нашел красивое решение для "2 из 10 за 6" с 4мя первыми фиксированными измерениями!

см. картинку



распределения исходов приложил в txt файле

2

Головомойки и задачки / Re: Задачи на поиск радиоактивных шаров

« : 02 Апрель 2021, 12:38:25 »

Нашел еще вариант первых 3 х измерений

он имеет вид

1234
1567
7894



при всех отрицательных исходах получаем задачу "2 из 6 за 4" которая не имеет решения

и похоже больше вариантов 3х первых измерений нет. Таким образом задача решаема только при 3х фиксированных измерениях вида "1общий+4", в этом варианте 4е измерение уже обязательно идет с учетом результатов предыдущих. Полностью детерминированного решения не существует, расходимся

3

Головомойки и задачки / Re: Задачи на поиск радиоактивных шаров

« : 01 Апрель 2021, 13:05:10 »

Привет. Спасибо за отклик!

Про XOR не совсем понял

на примере найденного решения с 3мя первыми измерениями
12345
56789
5ABCD

(у меня 5 общий)

имеем таблицу

   1234567
1 1000000
2 1000000
3 1000000
4 1000000
5 1110000
6 0100000
7 0100000
8 0100000
9 0100000
A 0010000
B 0010000
С 0010000
D 0010000
E 0000000
F 0000000
далее ход мысли теряется.


У меня другой подход, каждое измерение должно делить количество исходов примерно пополам, а точнее чтобы количество исходов в группе не превышало соответствующую степень двойки. Отсюда понятно что первое измерение должно содержать либо 4 либо 5 шаров.
при 4х 105 = 55 + 50  (не превышено 64)
при 5и  105 = 45 + 60  (не превышено 64)

при 3х 105 = 66 +39  (превышено 64, не подходит)
при 6и  105 = 69 + 36 (превышено 64, не подходит)

таким образом каждое измерение при детерминированном решении будет содержать либо 4 либо 5 шаров и никак иначе, ведь очередность измерений не важна!

приложил скрипт на python для анализа, в нем можно заложить любую последовательность измерений и посмотреть на результат разбиений 105и исходов

В drozd_capacitor.txt результат  для
12345
56789
5ABCD

и наглядно видно что все группы содержат не более 16 исходов. Любая моя попытка добавить 4е измерение - ломает строй и мы видим более 8 исходов в какой то из групп Ну и как я писал выше, не удалось придумать даже первые 3 измерения отличного от "1общий+4" вида. Может у вас получится..


PS ради забавы drozd_dicho.py ищет шары за 7 измерений по нашему алгоритму

4

Головомойки и задачки / Re: Задачи на поиск радиоактивных шаров

« : 16 Март 2021, 20:32:52 »

Привет!

Давно знаю эту задачу и её решение с тремя первыми измерениями вида

1-2-3-4-5
1-6-7-8-9
1-10-11-12-13

но меня всегда интересовал вопрос можно ли разбить шары на 7 групп, измерить каждую, получить код в двоичном диапазоне 0000000-1111111 (128 комбинаций), чтобы можно было сопоставить каждой один из 105 вариантов размещений 2 из 15.

т.е. то, о чем вы пишете:

"P.S. Помнится, "авторское" решение подразумевало нумерацию шаров с последующим выкладыванием их в детектор в разных комбинациях - причем без оглядки на предыдущие измерения. Но подобрать комбинации заново у меня не получилось. (вероятно, так оно нагляднее было бы, но решение есть решение)"

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

1-2-3-4-5
1-6-7-8-9
1-10-11-12-13


произвести невозможно так, чтобы варианты были разбиты на группы с не более чем 8 исходов в каждой группе.
Более того, похоже не существует и другого варианта первых 3х независимых  измерений кроме указанного вида (1 общий + 4 в каждой группе)