Так получилось, что за последние полгода мне удалось познакомиться с несколькими простыми (в смысле правил) и в чем-то схожими настольными играми. Первым в этом ряду был «Сет», потом «Барабашка», а уже летом мы играли в «Доббль». Сразу скажу, что все перечисленные игры весьма увлекательные, однако, речь в этом посте пойдет, конечно же, не об этом. Дело в том, что спустя некоторое время (другими словами, наигравшись) меня заинтересовали идеи, лежащие в основе этих игр, и которые оказались тесно связанными именно с комбинаторикой. В данном посте речь пойдет о самой простой (на мой взгляд) игре — «Барабашке», которая, кстати, в оригинальном варианте имеет более благозвучное название «Geistesblitz» (нем. — озарение).

Правила игры

Итак, в чем заключается игра. Имеется 5 предметов, каждый из которых, условно говоря, характеризуется формой и цветом (т.е. двумя категориями) — белый барабашка, красное кресло, синяя книга, зеленая бутылка и серая мышка.



Кроме того, имеется некоторое количество карточек, на каждой из которых изображено два предмета, имеющих разную форму и разный цвет (но из перечисленных выше форм и цветов). На некоторых карточках присутствуют предметы, в точности совпадающие с настоящими предметами. На любой карточке хотя бы у одного предмета цвет не соответствует форме (например, красная бутылка).



Цель игры заключается в том, что для данной карточки как можно быстрее определить предмет, который а) либо присутствует в правильном виде на карточке (совпадает и форма и цвет), б) либо полностью отсутствует (на карточке нет ни формы этого предмета, ни его цвета).



В первом примере у нас имеется белый барабашка, его мы и должны схватить, во втором примере наш выбор — бутылка, потому что на карточке нет бутылки (как формы) и нет зеленого цвета (несложно проверить, что в данном случае бутылка является единственным вариантом, так как отдельные категории всех оставшихся предметов на карточке присутствуют).

Собственно и все правила. Игра сама по себе рассчитана на несколько игроков, каждый играет сам за себя, цель набрать как можно больше карточек (кто первый ухватил правильный предмет, того и карточка). Внимание: не играйте с людьми с длинными ногтями, возможно получение колото-резаных ран!

Число карточек

Первый вопрос, который меня заинтересовал — это сколько различных карточек возможно в данной игре. Чистая комбинаторика! Что приятно, решается эта задача довольно легко. Для начала заметим, что у нас имеется два типа карточек, назовем их правильными (на них имеется нужный предмет) и неправильными (на таких карточек нужного предмета нет). Подсчитаем отдельно количество тех и других.

Начнем с правильных. Первый предмет на правильную карточку можно выбрать пятью способами (из пяти имеющихся предметов). Второй предмет выбирается хитрее — сначала выберем его форму (четыре варианта, одна форма уже занята первым предметом), затем цвет (три варианта, один цвет занят первым предметом, второй занят предметом, форму от которого мы взяли на втором шаге). Таким образом, по правилу произведения, получаем полное число правильных карточек 5*4*3=60.

Неправильные карточки считаются аналогично. Сначала выбираем форму первого предмета (5 вариантов), потом его цвет (4 варианта). Затем выбираем форму второго предмета (3 варианта) и его цвет (2 варианта). Как раз остается один неохваченный выбором предмет — цель данной карточки. Применяем правило произведения, получаем 5*4*3*2=120 вариантов. Но это неверный ответ — набор предметов на карточке неупорядоченный, а мы посчитали количество упорядоченных наборов. Чтобы получить правильный ответ, надо 120 поделить на 2 — число перестановок из двух элементов (карточка «красная бутылка и белое кресло» = карточке «белое кресло и красная бутылка»). Таким образом, получаем 120/2=60 неправильных карточек.

Суммируем (т.е. применяем правило суммы) и получаем ответ: 120 карточек для игры. Считаем карточки в игре — 60 штук. Либо ошибка в расчетах, либо недостача. Несложное расследование показало факт именно недостачи — на каждый из пяти предметов приходится по шесть правильных и шесть неправильных карточек, а должно быть 12 и 12. Причем никакой логики в отборе карточек обнаружить не удалось (скорее всего рандомный выбор).

Обобщение

Переформулируем слегка задачу. Имеется N предметов, каждый из которых описывается k категориями, и имеется Q карточек, на каждой из которых изображено n предметов (в рассмотренном выше случае N=5, k=2, n=2 и Q=120). Имеются ограничения — карточки могут быть правильными (в вышеуказанном смысле) и неправильными. В любом случае, на каждой карточке ни один из kN возможных признаков не повторяется (например, все цвета разные и все формы разные). Кроме того, каждый предмет либо полностью изображается на карточке, либо от него присутствует не более одного признака: например, в «Барабашке» нет карточки с белой бутылкой и красным барабашкой (два признака от одного предмета), т.к. для такой карточки есть два выбора — серая мышка или синяя книга. Единственный и естественный вопрос, который возникает в такой обобщенной постановке — какова связь между переменными N, k, n и Q?

Во-первых, несложно установить, как связаны N, k и n. Рассмотрим неправильные карточки. На каждой такой карточке изображено n предметов, значит на ней присутствует ровно kn признаков, которые определяют kn предметов (все признаки разные, никакие два не принадлежат одному предмету). Так как такой карточке должен соответствовать единственный предмет не вошедший в нее, то получаем необходимое число предметов kn+1. Заметим, что это число позволяет составлять и правильные карточки (на каждой правильной карточке присутствует в том или ином виде 1+(n-1)k предметов). Таким образом, N = kn+1. Нетрудно убедиться, что формула верна для рассмотренного выше случая n=k=2 и N=5. Представим найденную зависимость в виде таблицы (красным цветом выделена ячейка, соответствующая игре «Барабашка»):



Что значат эти числа? Предположим мы хотим создать расширенную (суперсложную) версию игры, в которой на каждой карточке будет n=5 предметов, а каждый предмет будет описываться k=5 категориями. Получаем N=26. Это значит, что по каждой категории нужно будет придумать 26 ее значений (признаков). Т.е. если категория — цвет, то нужно определить 26 хорошо различающихся между собой цветов. Нелегкая задача… Поэтому, возможные расширения игры скорее всего ограничены областью около левого верхнего угла таблицы. Кстати, вроде бы тривиальные случаи n=1 или k=1 также имеют право на жизнь (хотя, скорее всего, в этих случаях главным будет хорошая реакция).

Подсчитаем теперь количество карточек Q в расширенной (параметризованной) версии игры. Применяя вышеописанный прием, находим число правильных карточек N!/k!/(n-1)! и число неправильных карточек N!/n!, складывая и упрощая, получаем результат

.

Формула работает для n=k=2, а также была проверена для меньших значений этих параметров. Правда, в случае n=k=1 она слегка врет, т.к. в этом случае правильная карточка для одного предмета совпадает с неправильной карточкой для другого предмета (т.е. любой выбор будет выигрышным), поэтому результат надо поделить на 2. Во всех остальных случаях такие коллизии не случаются. Для случая n=k=3 формула дает число Q=907200. Если каждая карточка будет толщиной в одну десятую миллиметра, то полная стопка окажется высотой почти в 90 метров!

Реализация случая n=k=3

После того, как я разобрался во всей этой кухне, было решено создать простой прототип-демонстрацию расширенной версии игры для всех значений n и k от 1 до 3. Однако, когда дело дошло собственно до программирования, энтузиазм мой слегка поутих и я решил ограничиться случаем n=k=3 (N=10). Так это всего лишь демонстрация к статье, то было решено не заморачиваться с графикой, а сделать практически текстовую версию игры. Итак, три категории — это буквы (от A до J), цифры (от 0 до 9 — очень удачно, что у нас десятичная система счисления) и спецсимволы (проценты, доллары и т.п.) Таким образом, каждый «предмет» — это набор (неупорядоченный) трех символов (буква+цифра+спецсимвол): A0%, B1$ и т.д. Игра рассчитана на одного игрока, которому дается 100 секунд на угадывание предметов. Правильный выбор предмета прибавляет 1 к счету, неправильный — уменьшает счет на 1 (но только до нуля). Игра реализована на HTML+JS и выложена вот здесь (тестировалась только под хромом). Интерфейс очень простой:



В верхнем ряду показывается карточка с тремя предметами, в нижнем — сами предметы. Надо выбрать из нижнего ряда предмет, который либо есть на карточке (совпадают все три символа), либо предмет, ни одного символа которого на карточке нет. В данном примере правильный выбор — карточка с буквой G. Небольшая обфускация (перемешивание «предметов» и символов в «предметах») используется для усложнения игры. Заметим, что и оригинальная версия «Барабашки» также является обфусцированной — предметы имеют различный размер и по различному располагаются на карточке (кроме того, реальные предметы постоянно перемешиваются самими игроками в процессе игры). Удачи тем, кто рискнет сыграть (мой рекорд пока — порядка 6 угаданных предметов)!

Спасибо всем за внимание!

PS: А при чем же здесь ортогональные полиномы, спросит внимательный читатель. Честно говоря, не знаю! Но если взять формулу для Q и подставить в нее k=2, то получим числовую последовательность, которая начинается вот так: 1, 9, 120, 2100 и т.д. Имеется такой замечательный сайт — словарь целочисленных последовательностей, который позволяет по нескольким элементам последовательности найти саму последовательность (типа игры «Угадай мелодию»). Я вбил туда найденные числа и была найдена единственная последовательность, которая связана как раз с коэффициентами ортогональных полиномов… Проверка показала, что формулы (моя и их) идентичны. Я не поленился, нашел и скачал оригинальную статью, мои числа оказались третьми по старшинству коэффициентами в многочленах, полученных некоторым образом в процессе обратного преобразования Лапласа. К сожалению, какая связь между этими многочленами и «Барабашкой» мне понять так и не удалось…