В тестовой группе имеется $ 7 $ заболевших COVID мышей. Экспериментаторы полагают, что среди $ 7 $ имеющихся у них вакцин, одна или комбинация нескольких излечивает болезнь. Как организовать эксперимент, чтобы «отловить» минимально возможную исцеляющую комбинацию? Дополнительным условием ставится ограничение по времени: болезнь прогрессирует слишком быстро и тестировать лекарства надо сразу на всех особях.

Будем решать задачу в гипотезе, что исцеляет какая-то пара из вакцин. Пронумеруем их $ 1,2,\dots, 7 $. Всевозможных сочетаний из двух лекарств $ C_7^2=21 $, а возможных экспериментов всего $ 7 $. В предположении, что только одна пара лекарств является исцеляющей, вероятность ее обнаружить в результате $ 7 $ экспериментов равна $1/3$. Если теперь организовать следующие комбинации из трех лекарств: $$ \{1,2,3\},\ \{1,4,5\},\ \{1,6,7\},\ \{2,4,6\},\ \{2,5,7\},\ \{3,4,7\},\ \{3,5,6\} \, , $$ то можно гарантировать «локализацию» исцеляющей пары лекарств (если она существует). Любая возможная пара $ \{j,k\} $ входит в одно из подмножеств.

Нет, мы не сможем гарантировано установить точные значения для $ j $ и $ k $, но, по крайней мере, будем знать, что они содержатся в определенной «исцеляющей тройке».

Задача Вулхауса. Определить число сочетаний из $ n $ элементов по $ m $ элементов при дополнительном ограничении, чтобы никакая комбинация из $ q $ элементов, возникающая в одном сочетании, не возникала ни в каком другом сочетании. Ответ: $$ C_{n}^{q}/ C_{m}^{q} \, . $$

Задача Киркмана о 15 школьницах. $ 15 $ школьниц ежедневно, в течении недели, прогуливаются тройками. Распределить их по тройкам на каждый день недели так, чтобы никакая пара девушек не встречалась в одной тройке более одного раза.

Число решений: $ 404\, 756 \, 352\, 000 $, из них только $ 7 $ неизоморфных.

Если обозначить школьниц первыми буквами латинского алфавита, то одно из решений — $$ \begin{array}{c||c|c|c|c|c} 1 & ABJ & CEM & FKL & HIN & DGO \\ 2 & ACH & DEI & FGM & JLN & BKO \\ 3 & ADL & BHM & GIK & CFN & EJO \\ 4 & AEG & BIL & CJK & DMN & FHO \\ 5 & AFI & BCD & GHJ & EKN & LMO \\ 6 & AKM & DFJ & EHL & BGN & CIO \\ 7 & BEF & CGL & DHK & IJM & ANO \end{array} $$

Пусть имеется некоторое конечное множество $ \mathbb V $, количество элементов (также называемых varieties) которого равно $ v $.

Пусть имеется некоторый набор $ \mathbb B $ подмножеств (часто называемых блоками, blocks). Количество подмножеств в $ \mathbb B $ обозначим $ b $.

Блок-схемой (desing) назовем пару $ (\mathbb V, \mathbb B) $.

Правильной блок-схемой (regular design) назовем блок-схему, в которой каждый элемент из $ \mathbb V $ принадлежит ровно $ r $ различным блокам.

Однородной блок-схемой (uniform design) назовем блок-схему, в которой каждый блок содержит одинаковое количество $ k $ элементов.

Сбалансированной блок-схемой (balanced design) назовем блок-схему, в которой каждая пара элементов из $ \mathbb V $ присутствует в одинаковом числе $ \lambda $ блоках

Правильную однородную сбалансированную блок-схему будем называть $$ (b,v,r,k,\lambda) - \mbox{схемой} \, . $$

Пример. В задаче о подопытных мышах предложенное разбиение на подмножества является $ (7,7,3,3,1) $-схемой.

$ (b,v,r,k,\lambda) $ -схема называется

• полной если $ v=k $, в этом случае каждый элемент из $ \mathbb V $ содержится в каждом блоке;
• тривиальной если $ k=1 $, в этом случае каждый блок состоит из единственного элемента.

Случай $ k=2 $ тоже можно считать тривиальным, поскольку каждый блок состоит из $ 2 $ элементов, различных блоков будет $ C_v^2 $, и каждый такой блок надо клонировать $ \lambda $ раз.

Сбалансированная неполная блок-схема (Balanced Incomplete Block Design (BIBD) design) — это $ (b,v,r,k,\lambda) $ -схема при $ k< v $.

Теорема. Если BIBD существует, то справедливы соотношения

$$ \lambda (v-1)=r(k-1),\ bk=vr,\ b \ge v \, . $$

Разрешимой сбалансированной неполной блок-схемой называется такая BIBD-схема, блоки которой могут быть объединены в подмножества (называемыми параллельными классами), каждое из которых формирует разбиение множества $ \mathbb V $. Множество параллельных классов называется разрешением (resolution) схемы. Задача о $ 15 $ школьницах является разрешимой BIBD с $$ v=15,k=3,\lambda=1, r=7, b=35 \, .$$