Я прошу прощения, что пропустил сообщение в личке и не понял, что это было приглашение к обсуждению:
меня всегда интересовал вопрос можно ли разбить шары на 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