Tramvision
Всякая всячина => Головомойки и задачки => Тема начата: Dendr от 21 Февраль 2017, 20:50:56
-
Есть такая разновидность задач, похожих на задачи на взвешивание, но с небольшой спецификой.
Классическая задача на эту тему:
1. Имеется 15 внешне неотличимых шаров, среди которых два радиоактивных. У вас есть детектор радиоактивности, в который можно загрузить любое количество шаров, и он покажет, есть ли среди них радиоактивные.
Можете ли вы найти радиоактивные шары а 7 измерений?
Очевидно, что один шар легко найти за 4, и второй - еще за 4. При удаче будет быстрее, но в общем случае - восемь. Но нельзя ли подсократить?
А эта задача была, в облегченном виде, на одной из прошлогодних олимпиад. Я же жалеть никого не стану, а спрошу иначе.
2. Дано 100 шаров, из них 51 радиоактивный. Детектор, однако, слабенький: вмещает только два шара, да и срабатывает, если только оба они радиоактивны.
За сколько проверок гарантированно найдутся все радиоактивные шары?
3. Кому охота совсем голову сломать: обобщение обеих задач: есть N шаров, из них K радиоактивных. Вторая, кстати, обобщается проще, но при условии на K.
-
Вернулся вот перечитать тему, и понял, что сам не помню ответа. И главное, не помню, где я эти задачи встретил - теперь надо перерешивать заново, а, чтобы в следующий раз не терять, оставляю для истории.
Приходится импровизировать, поэтому ответ будет сумбурным.
Задача о двух радиоактивных шарах среди 15.
Сначала следует упомянуть, что найти один шар среди N можно простой дихотомией. Все, кто взялся решать такой тип задач, уже должны знать, о чем идет речь, поэтому не буду останавливаться.
В частности, это означает, что за 4 пробы легко найти первый шар, а затем, еще за 4 (среди 14) и второй.
Два из пятнадцати означает 15*14/2=105 комбинаций. Так как результат бинарен, то за 6 попыток мы можем различить 64 вариантов - то есть 6 проб явно не хватит, а вот хватит ли 7?
Начнем издалека - ищем два из пяти. Это 10 комбинаций, и значит, теоретический минимум равен 4. Здесь просто: берем и проверяем подряд по одному шару. За 4 пробы мы либо найдем оба шара, либо только один - тогда пятый, нетронутый, и есть второй искомый.
Итак, 2 из 5 решается за 4 пробы. (также можно показать, что 6 решается таким же образом за 5, а за 4 никак не успеть)
Дальше - 2 из 7. Это 21 вариант, можно попытаться свести к пяти пробам.
Перебрав немного вариантов, можно легко убедиться, что взяв в пробу номер 1 два шара, при отрицательном результате приходим к предыдущему случаю. А при положительном поступим так: проверим (пробой №2) один из уже проверенных шаров. Если детектор скажет, что он чистый, мы сделаем вывод, что его "напарник" радиоактивен, и ищем второй активный среди оставшихся пяти шаров. Если же проба была положительной, мы просто присоединим "напарника" к тем пяти. В любом случае, нам надо обнаружить 1 шар из 5 или 6. Это, очевидно, еще 3 пробы.
Итого - 2 из 7 ищется за 5 измерений.
Можно показать (но я этого делать не буду), что из 8 не хватит 5 проб, но за 6 -легко.
Перейдем сразу к поиску 2 из 10.
Первая проба - три шара, при отрицательном результате придем к поиску 2 из 7 - за 5 ходов, итого 6 хватит.
При положительном - пробы №2 и №3 рассмотрят по одиночке два шара из тех трех. Либо мы находим оба, на чем и закончим, либо один шар, тогда второй радиоактивный может быть как последним в тройке, так и среди семи нетронутых, либо ни одного, что означает, что последний из тройки точно радиоактивен, а другой - среди семи.
В последних двух случаях мы ищем один шар из 7 или 8. На это уйдет три пробы.
Таким образом, 2 из 10 находятся за 6 проб.
Наконец, вишенка на торте: мы ищем 2 из 15.
Сразу берем 5 шаров: при отрицательном результате ищем 2 из 10 - плюс 6 ходов, итого 7.
При положительном начинается свистопляска. Обозначим проверенные шары буквой a, остальные - b. Имеем набор: aaaaa bbbbbbbbbb.
Возьмем для второй пробы один шар из "a" и четыре "b", обозначив их прописными буквами: Aaaaa BBBBbbbbbb
Если проба 2 положительна, проверим шар A (проба 3). Если он радиоактивен, мы просто ищем 1 из 14. Это еще 4 пробы, итого 7. Если же нет, то имеем один среди aaaa, один - среди BBBB. Оба шара ищутся за две пробы, и в итоге те же 7.
Если проба 2 отрицательна, мы ищем два шара в наборе aaaa bbbbbb, держа в уме, что среди "a" как минимум один радиоактивен.
Для пробы 3 берем один "a" и два "b", повторяя обозначения, Aaaa BBbbbb
Если проба 3 положительна, проверим пару BB. Если результат отрицательный, шар A радиоактивен автоматически, и мы ищем второй среди aaa bbbb - на это уйдет еще три пробы, итого 6. При положительном результате мы делаем вывод, что один шар в этой паре (4-я проба найдет его), другой шар - в наборе Aaaa, и две пробы покажут его. Итого снова 6.
Если проба 3 отрицательна, мы снова урезаем количество подопытных шаров: aaa bbbb.
Убедимся, что у нас есть запас. Либо искомая пара a+a (три варианта), либо a+b (12 вариантов) - 15 комбинаций, то есть возможность выбрать за 4 хода еще остается.
Для пробы 4 возьмем по одному шару каждого "типа": Aaa Bbbb.
Положительность пробы 4: проверим пробой №5 шары aa. Если результат отрицательный, шар A - радиоактивен, а другой шар - в группе Bbbb, еще два опыта найдут его, всего 7. Если положительный, то в этой паре один шар, а другой - в паре AB. По одной пробе на каждую пару - и мы закончили поиск за 7 попыток.
Отрицательность пробы 4 означает, что искомые шары в наборе aa bbb.
Теперь проверим два шара "b"(aa BBb) пробой №5.
Если она положительна, то один шар в паре aa, другой - в BB. Шестая и седьмая пробы находят каждый.
Если же пятая проба отрицательна, у нас останется набор из трех шаров, мы даже забываем про их маркировку, потому что проверив два из них пробами №№6 и 7, мы либо обнаружим оба искомых шара, либо найдем один, и другой автоматически кажется тем, который мы отложили.
Таким образом, вот так сумбурно, но доказано, что 2 из 15 вычисляются за 7 проб.
P.S. Помнится, "авторское" решение подразумевало нумерацию шаров с последующим выкладыванием их в детектор в разных комбинациях - причем без оглядки на предыдущие измерения. Но подобрать комбинации заново у меня не получилось. (вероятно, так оно нагляднее было бы, но решение есть решение)
-
Вот писал эту простыню полвечера (а сочинял еще дольше), а потом в метро торкнуло на простейшее решение - его и приведу. Опять же для истории.
Получается разговор сам с собой, но уж что получается...
1. Пронумеруем шары, и в первые три измерения возьмем:
1-2-3-4-5
1-6-7-8-9
1-10-11-12-13
Если все три пробы были положительные, то шар 1 точно радиоактивен и нам надо найти второй среди 14. Это легко сделать за 4 попытки дихотомией. Всего будет 7.
Если ни одна - то радиоактивны шары 14 и 15, и поиск закончен.
Если ровно две (без ограничения общностей положим, что первая и вторая), то ясно, что шар 1 - чистый, иначе бы и третья была положительной. Тогда один шар в четверке 2-3-4-5, второй - 6-7-8-9. Каждый ищется за две пробы, всего будет те же 7.
Если только одна (пусть первая), то имеем две возможности: оба шара в наборе 2-3-4-5, либо в этом наборе один шар, а второй - либо 14, либо 15.
Четвертое измерение: шары 14 и 15. Если проба положительна, пятой вычисляем "грязный" шар, а еще двумя - ищем один шар из четверки 2-3-4-5. Если отрицательна, то оба шара с этой четверке, проверив последовательно шары 2, 3 и 4 мы либо найдем их оба, либо только один, а следовательно, шар 5 должен быть радиоактивным. И опять семи замеров хватает.
2. На самом деле легко, хотя и кажется сложным.
Очевидно, что нам надо исследовать пары, пока не достигнем срабатывания, которое означает, что мы нашли два "грязных" шара, и можем использовать один, как тестовый. Также очевидно, что надо на первом этапе брать новые пары. Сразу будем наклеивать на них ярлычки с номерами (1А и 1Б, 2А и 2Б и т.д.)
Крайний случай: мы проверили 49 пар, и датчик ни разу не сработал. Это значит, что в каждой из этих пар по одному чистому шару, а другой - радиоактивен. Два непроверенных шара тоже радиоактивны, незачем тратить лишний ход. Следующими 49 измерениями мы, используя один из них, разложим шары в парах: зная статус шара 1А, мы автоматически знаем и 1Б. На все-про-все уйдет 98 замеров.
Другой крайний случай: мы сразу нашли два "грязных" шара. Можно, конечно, просто перебрать все, кроме одного, и узнать их - за 98 ходов - но лучше универсализировать. Назовем пулом все шары, которые еще не разделены. Чем меньше шаров в пуле, тем ближе финиш.
Берем новую пару. Допустим, она сработала - значит, оба "грязные". Положим их в ящик с надписью "грязные". За один ход из пула мы убрали два шара - неплохой результат!
Допустим, что не сработала. Либо они оба чистые, либо только один. Берем один из этой пары и измерим совместно с определенно "грязным". Если это проба положительна, значит, нам попалась пара разных шаров, и мы даже знаем, какие они. "Грязный" кладем все в тот же ящик, а чистый - в ящик "чистые". За два хода из пула вышло два шара, или 1 за ход. Но если эта вторая проба отрицательна, то мы наверняка только знаем, что этот шар чист (кладем в ящик), а второй... нетривиально поступим - вернем его в пул (!). За два хода из пула вышел один шар, то есть 0,5 за ход. Медленно, да. Если бы мы измерили и этот шар, было бы 2/3, но мы не сможем тут ускориться. Ведь дальше мы берем новую пару и замыкаем цикл. Лучше, как выясняется, безжалостно возвращать.
Пусть дело у нас продвигается максимально медленно: мы находим только чистые шары. Но когда мы найдем 48 из них (за 96 ходов), в пуле останется один. А это значит, что отрицательная проба новой пары позволяет нам гарантированно выяснить, что мы взяли пару разных и никак иначе, следующим ходом различить их, а все оставшиеся в пуле автоматически "грязные".
Дело продвигается максимально медленно, так? Получается, мы проделали 97 измерений и имеем в пуле 49 "грязных" и 1 чистый. Еще 23 хода тратим на выявление пар "грязных".
Спустя 120 ходов в пуле останется набор ГГГЧ.
121-й ход: либо ГГ (+), либо ГЧ (-). Так мы нашли пару "грязных" (она либо в датчике, либо еще у пуле), положим ее в ящик к собратьям. Остается набор ГЧ
122-м ходом мы выявим статус произвольного из пары, второй автоматически известен.
Итого 122 хода.
Это был крайний вариант, хотя и нетривиально решенный (и не так быстро, как было бы можно)
А промежуточные? Нам на помощь придут те самые ярлычки.
Вот нашли мы два радиоактивных шара на 15-м ходу. Сделаем сначала вид, что мы забыли про 14 предыдущих. Дальше нам надо выбрать пару, измерить ее и далее по алгоритму выше. Но мы только что наизмеряли 14 пар! От перестановки ничего не поменялось - мы можем считать, что сначала выбрали эти два радиоактивных шара, а потом нам 14 раз подряд попались пары с отрицательной пробой. То есть снова решение за 122 хода. Это и есть ответ.
3. Обобщение второй задачи при условии, что радиоактивных шаров больше, чем чистых, совсем несложное. Пусть K радиоактивных и M чистых (K>M).
Тогда та же схема требует 1+2*(M-1)+[(K-4)/2]+2=2M+[K/2]-1 (квадратные скобки - округление до целого в меньшую сторону - сработает при любой четности) ходов максимум. В целом, ответ никогда не превышает 5N/4.
Если K<=M, процесс может затянуться, пока мы ищем "грязную" пару. При K=M, как можно убедиться, всего три дополнительных хода, но при дальнейшей увеличении разницы все сложнее и сложнее.
-
Ну, это что-то уже из разряда олимпиады по математике. Ты про козу и капусту давай :)
-
Привет!
Давно знаю эту задачу и её решение с тремя первыми измерениями вида
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 в каждой группе)
-
Я прошу прощения, что пропустил сообщение в личке и не понял, что это было приглашение к обсуждению:
меня всегда интересовал вопрос можно ли разбить шары на 7 групп, измерить каждую, получить код в двоичном диапазоне 0000000-1111111 (128 комбинаций), чтобы можно было сопоставить каждой один из 105 вариантов размещений 2 из 15.
Да, возможно это и было то "авторское" решение, на которое я ссылался. Боюсь, что по прошествии лет уже не помню, где именно я повстречал эту задачу, так что найти концы точно не удастся, но эта идея довольно интересна.
По сути, мы составляем большую таблицу - сначала, по строкам, номер измерения, по столбцам - нумерованные шары. В самих клетках таблицы ставим метки, если данный шар в данном измерении участвует. Дальше мы продлеваем таблицу вправо, размечая ее еще на 128 столбцов, так чтобы по вертикали получался вот этот "двоичный код".
И, наконец, если нам удастся пометить эти столбцы так, что хотя бы 105 из них соответствовали ровно одной паре шаров, причем пары не повторяются, то задача решена. Остальные 23 столбца не обязаны соответствовать какой-то уникальной паре, но и обратное не запрещено. На самом деле, это уже будет неважно.
Ну вот, например, из моего же текста выше: найти 2 из 5 за 4 измерения. Табличка получится 4х(5+16), и в правой части нам надо хотя бы 10 столбцов с уникальной парой. Такую табличку можно, для тренировки, набросать на листке.
Предложенная мной выше схема проверки дает левую часть таблички из 4 строк и пяти столбцов, где закрашена диагональ, а пятый столбец - незакрашен. В правой части окажется 6 "невозможных" столбцов - ну, понятно, что в коде может быть только от 1 до 2 единиц, а остальные будут соответствовать какой-то паре. Например, "0100" означает, что искомые шары - 2 и 5.
А если обобщать? Сразу появляются вопросы:
1) Может ли какой-то паре сооветствовать код "0000"? Допустим, что это так, пускай это шары с номерами 1 и 2. Это значит, что их мы не изучаем вообще. Но тогда они неразличимы! Значит, ответ на этот вопрос отрицательный. То есть в правой части таблицы лишь 15 столбцов, а не 16.
2) Насколько различны измерения? Заметим, что при таком подходе порядок измерения не имеет значения. Поэтому заметим: если, например, в первом измерении мы берем все шары подряд с меньшими номерами, то есть помечаем в первой строке левой части таблицы несколько левых клеток подряд, то в следующих строках помеченные клетки пойдут уже вразнобой. Переставим первую строку с какой-нибудь (неважно), а теперь - столбцы, чтобы картинка сохранилась. Соответственно, надо будет как-то попереставлять столбцы и справа. По идее, мы должны перейти к той же самой картинке! Значит, все измерения должны быть равноценны. Хотя это не строгое доказательство, посмотрим дальше. Во всяком случае, это означает, что в рабочем алгоритме все коды с одинаковым количеством единиц будут присутствовать.
Сколько вообще единиц может быть в коде?
В зависимости от количества единиц, кодов с таким количеством может быть (определяется биномиальными коэффициентами):
0 единиц, 4 единицы - по 1 коду
1 единица или 3 - 4 кода
2 единицы - 6 кодов.
Нам нужно 10, поэтому и берем, например, 4 с одной единицей и 6 с двумя. И все замечательно.
А для изначальной задачи?
0/7: 1 код
1/6: 7 кодов
2/5: 21 код
3/4: 35 кодов
"Выбросить" мы можем не более 23 кодов, поэтому коды с 3 и 4 единицами присутствовать должны неизбежно.
Обратим внимание на коды с одной единицей. Пусть "1000000" соответствует паре 1+15. Если бы в первом измерении были оба шара, значит, потом их не использовали оба, и мы их не различим в других комбинациях. Значит, 15 не использовался вовсе, а 1 - в этом самом первом измерении. Тогда использовались, естественно, все шары, хотя бы по разу. Можно ли шар 2 класть в первое измерение? Увы, нет: очевидно, что тогда случаи 1+2 и 2+15 неразличимы. Это значит, что в первом измерении мы положили только шар 1, и больше ничего. Но тогда у нас будет 64 кода для 104 прочих вариантов. А этого мало. Значит, коды с одной единицей - "мусорные".
Повторим список:
2 единицы - 21 код
3 единицы - 35
4 единицы - 35
5 единиц - 21
6 единиц - 7
7 единиц - 1 код.
И выбросить мы теперь может не более 15 кодов. Следовательно, есть хотя бы 6 кодов с двумя единицами и 6 с пятью (соответственно, обязательно есть 20 с тремя и с четырьмя).
Подойдем теперь с другой стороны: каждый шар должен быть использован в уникальном наборе измерений.
0 раз - можно измерить одним способом
1 раз - 7 способами
2 раза - 21
3 раза - 35
4 раза - 35 способами
И у нас 15 шаров... И значит, 7 шаров - а на самом деле, по меньшей мере, 8 - надо будет измерять хотя бы по два раза. Но, заметьте, что если все не больше 2, тогда максимум единиц в коде - четыре. Значит, хотя бы один надо замерить трижды. Ну, так и сделаем: первый шар положим на первые три измерения (это как раз соответствует вышеуказанному алгоритму!) Собственно, если следующие 6 шаров примут участие ровно в двух из следующих четырех измерений, как раз "закроем" эти самые шесть. Но тогда если рассматривать пары из этих 6 шаров, то возникнут повторяющиеся комбинации измерений, так что их надо использовать как-то и в первых трех. Этот узел развязывается легко, если измерения так изучают первые семь шаров:
1) 1-2-7-
2) 1-3-6-
3) 1-4-5-
4) 2-3-4-
5) 2-5-6-
6) 3-5-7-
7) 4-6-7-
Как нетрудно убедиться, каждый шар будет измерен трижды, в разных комбинациях, а любая пара из этих шаров даст уникальную комбинацию из 5 единиц. Ну, например, 2+5 даст "1011110", а 3+6: "0101111". Всего наберется 21 комбинация - то есть все возможные. Остальные должны содержать
Но дальше начинается запутывание...
Вот, начал заполнять таблицу, и потерпел полный провал.
https://docs.google.com/spreadsheets/d/17U9gjOza39pZRDZ4WIn7fVVLvb2P7_-Jr15osgUtPpA/edit?usp=sharing (https://docs.google.com/spreadsheets/d/17U9gjOza39pZRDZ4WIn7fVVLvb2P7_-Jr15osgUtPpA/edit?usp=sharing)
-
Вот как можно проще доказать невозможность такой схемы. Важный момент: мы всегда можем перенумеровать шары и (или) поменять порядок проверки, и результат не изменится. Возможно, изменится таблица соответствия "код - искомая пара", но разрешимости задачи это не изменит. Поэтому мы можем вполне вольно обращаться с номерами шаров и порядком следования нулей и единиц в коде.
1. То, что в коде должно быть по крайней мере две единицы, уже доказано.
Вкратце еще раз: если паре 1+2 соответствует код "0000000", то оба этих шара ни разу не проверялись, и мы не сможем различить пару "1+3" с парой "2+3".
Если паре 1+2 соответствует "1000000", то либо они оба проверены в первом измерении, но тогда, аналогично, пары "1+3", "2+3" неразличимы; либо проверен 1 в первом измерении, а 2 не проверяется вообще. Тогда, если шар 3 проверялся в первом измерении, то мы снова не сможем отличить все те же две пары. Значит, в первом измерении проверялся только шар 1. Но это значит, что коды "1******", где вместо звездочки стоит ноль или единица соответствуют парам, содержащим первый шар (всего их 14), а коды "0******" тогда - 91 паре, не содержащей его. Однако кодов 2^6=64, то есть их не хватает. Противоречие. Значит, ни одной паре не соответсвует код с одной единицей.
2. Пусть шар номер 1 проверялся не менее четырех раз, и пусть это первые 4 измерения. Тогда 14 парам 1+2, 1+3, ..., 1+15 будут соответствовать коды "1111***". Кодов 8, пар - 14. Не хватает. Значит, шары проверялись не более 3 раз. Но тогда шары искомой пары участвовали вкупе не более, чем в 6 измерениях, так что единиц в коде максимум 6.
3. Пусть шар номер 1 проверялся три раза. Тогда 14 парам соответствуют коды вида "111****", где среди звездочек обязательно присутствует хотя бы один ноль. Комбинаций 15, пар - 14, значит, только позволено откинуть только одну комбинацию, все остальные коды обязательно соотвествуют какой-нибудь паре.
В частности, кодов с 6 единицами здесь может быть четыре, следовательно, хотя бы три из них - корректны.
Например, пусть код "1110111" соответствует 1+2, следовательно шар 2 исследовался (помним, что не более трех раз!) в последних трех измерениях.
Коды "1111011" и "1111101" пусть соответствуют парам 1+3 и 1+4, и так мы увидим, в каких измерениях брались шары 3 и 4.
Тогда, получается, что пара "2+3" даст код "0001111", пара 2+4 - его же, и 3+4 - все равно его. То есть мы их не сможем различить. Вывод - ни один шар не использовался в трех (и больше) измерениях. Значит, максимум дважды, из чего следует, что коды могут содержать самое большее 4 единицы.
4. Однако, всех возможных кодов из семи символов, два из которых единица, 21. Кодов с тремя и четырьмя единицами - по 35. Всего набирается только 91 код, а комбинаций пар - 105. Это значит, что кодов не хватит, и "предетерминированного" алгоритма не существует.
P.S. Теоретически, такой алгоритм для 14 шаров не запрещен, вот его бы подобрать?
-
Или вот - вообще в двух строчках. Присвоим каждому из шаров двоичное число, соответствующее его участию в измерениях (единица, если шар меряется, ноль, если нет). Числа, разумеется, должны быть различными. Если семь измерений, то мы рассматриваем числа от 0 до 127.
Если шар радиоактивный, то детектор на данном измерении будет показывать положительный результат, если нет - зависит от остальных шаров. Значит, если мы записываем результат в виде все тех же единиц и нолей, то этот результат равен XOR'у радиоактивных шаров.
Теперь задача сводится к такой: можно ли взять такие 15 различных чисел от 0 до 127 включительно так, чтобы их все их попарные XOR'ы различались между собой?
(заметим, что для "2 из 5 за 4" решение есть, только выбирать надо 5 чисел от 0 до 15, и это, например, 0, 1, 2, 4, 8)
Обощение: какое наибольшее количество различных чисел от 0 до 2n-1 (где n - число измерений) мы можем взять так, чтобы среди попарных XOR'ов не было повторяющихся?
-
Привет. Спасибо за отклик!
Про 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 измерений по нашему алгоритму
-
Нашел еще вариант первых 3 х измерений
он имеет вид
1234
1567
7894
(https://clip2net.com/clip/m0/0b24d-clip-11kb.jpg?nocache=1)
при всех отрицательных исходах получаем задачу "2 из 6 за 4" которая не имеет решения :(
и похоже больше вариантов 3х первых измерений нет. Таким образом задача решаема только при 3х фиксированных измерениях вида "1общий+4", в этом варианте 4е измерение уже обязательно идет с учетом результатов предыдущих. Полностью детерминированного решения не существует, расходимся :)
-
Про XOR не совсем понял
Моя ошибка. Конечно же, "побитовое ИЛИ".
-
А вот как на счет решить задачу "3 шара из 9 за 7 измерений" ?
Вроде бы нашел элегантное решение подобное "2 из 15 за 7" описанное выше (3 первые измерения с 1м общим), но потом понял, что оно к сожалению неверное
Так же нашел красивое решение для "2 из 10 за 6" с 4мя первыми фиксированными измерениями!
см. картинку
(http://i.piccy.info/i9/a94c76e34d82a53b2af7cc74a1aaac63/1619973994/4176/1372542/1_240.jpg) (http://piccy.info/view3/14312992/1c2979fa02a5cb6661b9f7fe29c60694/)(http://i.piccy.info/a3/2021-05-02-16-46/i9-14312992/240x120-r/i.gif) (http://i.piccy.info/a3c/2021-05-02-16-46/i9-14312992/240x120-r)
распределения исходов приложил в txt файле
-
Я дико извиняюсь, но вся эта последовательность может легко решается через матрицу? ну где там в огромных скобках числа раскладываются, а потом всё легко? Я плохо помню, но там как-то всё легко?