Введение

Игра-головоломка в реальном времени с карточками

инфобокс карточная игра
| Правила =
| название = Set (Сет)
| тип = Реальное время
| изображение = Set game cards.png
| подпись = Три карты из колоды Set. Каждая из этих карт имеет уникальное количество, символ, заливку и цвет, и таким образом представляет собой "сет".
| игроки = 1+
| возраст = 6 лет+ Каждая возможная комбинация признаков (например, карта с тремя полосатыми зелеными ромбами) встречается в колоде ровно один раз.

Геймплей

В игре, определенные комбинации из трех карт называются "набором". Для каждой из четырех категорий признаков – цвета, количества, формы и заполнения – три карты должны демонстрировать этот признак либо а) полностью одинаково, либо б) полностью различно. Иными словами: для каждого признака три карты не должны иметь ситуации, когда две карты показывают одну вариацию признака, а оставшаяся карта – другую. Например, три красных ромба сплошным заполнением, два зеленых завитка сплошным заполнением и один фиолетовый овал сплошным заполнением образуют набор, потому что заполнение у всех трех карт одинаковое, а количество, цвет и форма у трех карт – все разные. Для любого набора количество постоянных признаков (одинаковых на всех трех картах) и количество различающихся признаков (разных на всех трех картах) может быть следующим: все 4 признака различаются; или 1 признак постоянен и 3 различаются; или 2 признака постоянны и 2 различаются; или 3 признака постоянны и 1 различается. (Все 4 признака постоянны означали бы, что три карты в наборе идентичны, что невозможно, так как в колоде Set нет одинаковых карт.)

История

Игра возникла из системы кодирования, которую разработчик использовала в своей работе генетиком. Формы основаны на формах, представленных в стандарте ISO 5807. В 1991 году игра Set получила награду Mensa Select от American Mensa и заняла 9-е место в конкурсе Deutscher Spiele Preis в 1995 году.

Основные комбинаторики множества

Для любых двух карт существует ровно одна карта, которая образует сет с этими двумя картами. Следовательно, вероятность получения сета из 3 случайно выбранных карт из полной колоды составляет 1/79. Cap-множество – это математическая структура, описывающая расклад карт, в котором невозможно составить ни одного сета. Самая большая группа карт, которую можно собрать вместе, не образуя сет, – 20, что было доказано в 1971 году (cap-множества изучались еще до появления игры). Такая группа называется максимальным cap-множеством. Дональд Кнут обнаружил в 2001 году, что для 81-карточной версии Set существует 682344 таких cap-множества размера 20; при аффинных преобразованиях в 4-мерном конечном пространстве все они сводятся к по сути одному cap-множеству. Существуют уникальные сеты. Вероятность того, что сет будет иметь различных и одинаковых признаков, равна (Примечание: случай, когда d = 0 невозможен, поскольку нет двух идентичных карт). Таким образом, 10% возможных сетов отличаются по одному признаку, 30% – по двум, 40% – по трем и 20% – по всем четырем. Количество различных комбинаций из 12 карт равно . Вероятность отсутствия сета среди 12 карт в начале игры Set составляет 30:1 в первом раунде. Затем эта вероятность быстро снижается, и примерно к 4-му раунду она становится 14:1, а в течение следующих 20 раундов медленно снижается до 13:1. Таким образом, в большинстве раундов вероятность составляет от 14:1 до 13:1. Вероятность отсутствия сета среди 15 карт в игре составляет 88:1. Среднее количество доступных сетов среди 12 карт равно , а среди 15 карт . Однако в реальной игре эти числа меньше. Если бы из колоды было выбрано 26 сетов, то последние три карты обязательно образовали бы еще один, 27-й сет.

Сложность

Используя естественное обобщение понятия множества, в котором число свойств и значений может меняться, было показано, что задача определения существования множества по набору полученных карт является NP-полной.