Вспомогательная страница к разделу ((:basics/combinatorics ЭЛЕМЕНТЫ КОМБИНАТОРИКИ)) ==Задача о подопытных мышах== В тестовой группе имеется $ 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 $, но, по крайней мере, будем знать, что они содержатся в определенной "исцеляющей тройке". ==Задача Киркмана о школьницах== **Задача Вулхауса.** Определить число ((:basics/combinatorics#sochetanija сочетаний)) из $ 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{схемой} \, . $$ !!П!! Пример. В задаче о ((#zadacha_o_podopytnyx_myshax подопытных мышах)) предложенное разбиение на подмножества является $ (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 \, .$$ В контексте декластерного массива устройств хранения (дисков), $ \mathbb V $ --- это множество устройств хранения, связанных с контроллером массива, $ v $ --- число этих устройств, и $ k $ число стрипов в страйпе (блоков в chunk group), задаваемое схемой исправления ошибок (в принятых нами обозначениях $ k= \mathfrak G $). ==Как построить?== ==Источники==