Карточки с одним общим элементом

[JH]

Купили ребенку настольную игру «Spot it». Интересная штука. Представляет собой набор карточек. На каждой карточке изображено восемь предметов. У любой пары карточек есть один и только один общий элемент. Задача игроков (их может быть от двух человек) – как можно быстрее найти у вновь открываемой карточки общий элемент со своей текущей карточкой. Кто быстрее нашел – тот и забирает (забранная карточка становится его текущей карточкой). Очень увлекательная игра. Но меня заинтересовала комбинаторная сторона этого дела. Сколько в принципе можно сделать таких карточек из восьми элементов (да так, что у любых двух карточек будет один и только один общий элемент), сколько всего элементов нужно будет задействовать и т.д. Хочу выяснить, оптимальный ли набор карточек в игре и можно ли было сделать большее количество.

[JH]

Для примера отсканировал шесть карточек (увеличенное изображение по клику):

[Akmal Bafoev]

N элементов на карточке, N+1 карточек.

[JH]

Сообщение от Akmal Bafoev

N элементов на карточке, N+1 карточек.

Всего карточек в наборе 55, все удовлетворяют условию. Я хочу узнать, можно ли больше.

[Evgeniy Sklyarevskiy]

Сообщение от Akmal Bafoev

N элементов на карточке, N+1 карточек.

и всего связей между ними (то есть элементов) N*(N+1)/2 = 36, откуда тогда 55 не ясно, где ошибка?

[JH]

Сообщение от Evgeniy Sklyarevskiy

и всего связей между ними (то есть элементов) N*(N+1)/2 = 36, откуда тогда 55 не ясно, где ошибка?

Там все сложнее. Нужно учитывать, что не должно быть двух таких карточек, которые имеют больше одного общего элемента.

[Nadir Zaitov]

А сколько различных элементов есть? В этом вопрос.
Например, если 15 - то только 15 карточек. (меньше 15 элементов нельзя - иначе не выполнится условие уникальности 8 элементов на карточке и ровно одним общем с другой карточкой)

[Akmal Bafoev]

в начале я не совсем правильно понял условие

элементов должно быть M=2N-1.
тогда максимально возможное количество карточек получается С(N,M) = (о, ужас!) 6435

[Georgick]

Сообщение от Akmal Bafoev

в начале я не совсем правильно понял условие

элементов должно быть M=2N-1.
тогда максимально возможное количество карточек получается С(N,M) = (о, ужас!) 6435

сомнительно

для случая, если на карточке только два элемента карточек будет 3

для трёх элементов - 7
для четырёх - 10

я предложил бы подобрать формулу, проверить на первом шаге. Далее доказать, что она верна и на N+1 шаге через справедливость на N-шаге, т.е методом мат. индукции

[JH]

Сообщение от Akmal Bafoev

элементов должно быть M=2N-1.

При таком количестве элементов ты даже третью карточку не сформируешь так, чтобы она отвечала условию (один, и только один общий элемент с каждой из двух первых карточек)