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

[JH]

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

[JH]

Для примера отсканировал шесть карточек (увеличенное изображение по клику):
http://img-fotki.yandex.ru/get/5708/jhaitov.0/0_62d05_9727bede_M.jpg (http://img-fotki.yandex.ru/get/5708/jhaitov.0/0_62d05_9727bede_XXXL.jpg)

[Akmal Bafoev]

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

[JH]

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

[Evgeniy Sklyarevskiy]

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

[JH]

и всего связей между ними (то есть элементов) N*(N+1)/2 = 36, откуда тогда 55 не ясно, где ошибка?
Там все сложнее. Нужно учитывать, что не должно быть двух таких карточек, которые имеют больше одного общего элемента.

[Nadir Zaitov]

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

[Akmal Bafoev]

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

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

[Georgick]

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

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

сомнительно

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

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

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

[JH]

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

[JH]

Например, если 15 - то только 15 карточек.Элементов намного больше 15. При 15 элементах вы уже третью карточку не сможете сформировать.

[Georgick]

разных элементов, судя по всему, всего 36 = 8+7+6+5+4+3+2+1
вопрос в том - сколько можно из них сделать таких карточек

[Georgick]

разных элементов, судя по всему, всего 36 = 8+7+6+5+4+3+2+1
вопрос в том - сколько можно из них сделать таких карточек

чуть ошибся - всего разных элементов:

8+7+7+7+7+7+7+7 = 57.

или в общем случае, где n - число элементов на карточке

n + (n-1)(n-1) = n^2-n+1

[JH]

ШН, правильны ли подсчеты количества элементов у Georgick-а? Мой мозг упорно отказывается понимать принцип.

И все-таки, сколько можно сделать карточек и какой алгоритм?

[Evgeniy Sklyarevskiy]

8+7+7+7+7+7+7+7 = 57. Игорь, поясните, плз, как это так?

[Alisher Asror]

Если элементы не ограничены, то и карточки могут быть безконечными.

1 2 3 4 5 6 7 8
1 9 10 11 12 13 14 15
1 16 ........................
1...
1
.
.

и.т.д

[Georgick]

ШН, правильны ли подсчеты количества элементов у Georgick-а? Мой мозг упорно отказывается понимать принцип.

И все-таки, сколько можно сделать карточек и какой алгоритм?

57 - это максимальное возможное количество разных элементов. Сколько всего карточек - ещё остается вопрос открытым)

На примере трёх вариантов видно, как получается такая формула числа разных элементов (3+2+2 = 7 в данном случае)

а1, a2, a3
a1, a4, a5
a1, a6, a7

если добавится восьмой элемент, то условие задачи уже не выполнится

[JH]

а1, a2, a3
a1, a4, a5
a1, a6, a7


У меня с тремя элементами на карточку получилось меньше элементов и больше карточек.

1, 2, 3
1, 4, 5
2, 4, 6
3, 5, 6

[Georgick]

У меня с тремя элементами на карточку получилось меньше элементов и больше карточек.

1, 2, 3
1, 4, 5
2, 4, 6
3, 5, 6


для трёх элементов решений - 7
я показал лишь начало выбора

вот полное решение

a1, a2, a3
a1, a4, a5
a1, a6, a7

a2, a4, a6
a2, a5, a7

a3, a5, a6,
a3, a4, a7

[JH]

Если элементы не ограничены, то и карточки могут быть безконечными.

1 2 3 4 5 6 7 8
1 9 10 11 12 13 14 15
1 16 ........................
1...
1
.
.

и.т.д
Ага, и у всех карточек будет один и тот же общий элемент
А надо, чтобы все элементы равномерно были "общими"

[Nadir Zaitov]

Элементов намного больше 15. При 15 элементах вы уже третью карточку не сможете сформировать.Согласен. Сначала написал одна, но потом "черт дернул". Показалось, что общую точку можно менять.

[Shuhrat Ismailov]

ШН, правильны ли подсчеты количества элементов у Georgick-а? Мой мозг упорно отказывается понимать принцип.
И все-таки, сколько можно сделать карточек и какой алгоритм?
В голову приходит лишь формула включений-исключений.
Пусть http://latex.codecogs.com/gif.latex?A_{1},A_{2},...,,A_{n} -конечные множества.
Тогда
http://latex.codecogs.com/gif.latex?\left&space;|&space;\bigcup_{i=1}^{n}A_{i}&space;\right&space;|= \sum_{i=1}^{n}&space;\left&space;|&space;A_{i}&space;\right&space;|-\sum_{i<j}^{n}&space;\left&space;|&space;A_{i}\bigcap&space;A_{j}&space;\right&space;|&plus;\sum_{i<j<k}^{n}&space;\left&space;|&space;A_{i}\bigcap&space;A_{j}\bigcap&space;A_{k}&space;\ri ght&space;|-...&plus;(1)^{n}\left&space;|&space;A_{1}\bigcap&space;A_{2}\bigcap&space;A_{3} ...\bigcap&space;A_{n}&space;\right&space;|
Так как пересечение трех или более карточек пусты, то формула примет вид
http://latex.codecogs.com/gif.latex?\left&space;|&space;\bigcup_{i=1}^{n}A_{i}&space;\right&space;|= \sum_{i=1}^{n}&space;\left&space;|&space;A_{i}&space;\right&space;|-\sum_{i<j}^{n}&space;\left&space;|&space;A_{i}\bigcap&space;A_{j}&space;\right&space;|
Первая сумма равна http://latex.codecogs.com/gif.latex?\8n
Так как http://latex.codecogs.com/gif.latex?\forall i,j \Rightarrow \left | A_{i}\bigcap A_{j} \right |=1
то вторая сумма равна http://latex.codecogs.com/gif.latex?\frac{n(n&plus;1)}{2}
Получаем следующее
Общее количество элементов во всех карточках равно
http://latex.codecogs.com/gif.latex?\8n-\frac{n(n&plus;1)}{2}=\frac{(17-n)n}{2}

[Alisher Asror]

Ага, и у всех карточек будет один и тот же общий элемент
А надо, чтобы все элементы равномерно были "общими"

Если сделать равномерно ( по 8) , то получаем 64 карточек и 449 элементов

[Georgick]

Так как пересечение трех или более карточек пусты, то формула примет вид

не обязательно. У трёх карточек может быть общий элемент - один и тот же.
На примере для трех элементов видно


a1, a2, a3
a1, a4, a5
a1, a6, a7

a2, a4, a6
a2, a5, a7

a3, a5, a6,
a3, a4, a7

Я бы перефразировал так - пересечение (n+1) карточек и более пусты, где n - число элементов на карточке

[Shuhrat Ismailov]

не обязательно. У трёх карточек может быть общий элемент - один и тот же.
Может быть, я плохо картинку JH рассмотрел. К тому же не так понял фразу
При таком количестве элементов ты даже третью карточку не сформируешь так, чтобы она отвечала условию (один, и только один общий элемент с каждой из двух первых карточек

[Nadir Zaitov]

Тогда для трех карточек необходимо 3 + 3*6 = 21 различный элемент.

(3 - попарно одинаковых, по две на карточку,
по 6 - разных во всех 3-х карточках, т.е. не разу не повторяются )

Для четырех карточек должно быть 6 + 4 * 5 = 26 различных элемента, 20 не повторяются

Для пяти карточек должно быть 10 + 5 * 4 = 30 различных элементов, 20 не повторяются

Для шести карточек должно быть 6*(6-1)/2 + 6*3 = 33 различных элемента, 18 не повторяются


Для семи карточек должно быть 7*(7-1)/2 + 7*2 = 35 различных элемента, 14 не повторяются

Для восьми карточек должно быть 8*(8-1)/2 + 8*1 = 33 различных элемента, 8 не повторяются

Для девяти карточек должно быть 9*(9-1)/2 + 9*0 = 41 различных элемента

ТЕПЕРЬ ВОПРОС 10 КАРТОЧЕК. А разве это возможно, что у каждой будет ровно один общий элемент с другой и чтобы все было равномерно?

[JH]

Я уже совсем запутался. Если кто-то захочет провести анализ - выложу все 55 карточек

[Georgick]

(3 - попарно одинаковых, по две на карточку,
по 6 - разных во всех 3-х карточках, т.е. не разу не повторяются )

карточка имеет только один и только один общий элемент с любой другой карточкой.

А разве это возможно, что у каждой будет ровно один общий элемент с другой и чтобы все было равномерно?



можно. Но не обязательно равномерно. Т.е какие-то элементы могут быть чаще общими, чем другие. Для случая n = 4 это уже хорошо видно (В случае n = 3 всё симметрично по вхождениям, просто так совпало)

[Nadir Zaitov]

Я уже совсем запутался. Если кто-то захочет провести анализ - выложу все 55 карточекВыкладывайте. Я тоже хочу сообразить.

[Nadir Zaitov]

a3, a4, a7
a1, a2, a3Эти две, например, не пересекаются или я что-то не понял?

[JH]

a3, a4, a7
a1, a2, a3Эти две, например, не пересекаются или я что-то не понял?

Как не пересекаются? На обеих есть "а3"

[JH]

Вот, все 55 карточек из набора (http://dl.dropbox.com/u/30028164/Spot_It.zip)

[JH]

Сделал чорную работу, см. таблицу (http://dl.dropbox.com/u/30028164/spotit.xlsx)

Получилось:
Всего элементов: 57
Всего карточек: 55

Некоторые элементы встречаются по восемь раз, остальные - по семь.

Меня не покидает подозрение, что набор неоптимален, и что дальнейшая оптимизация возможна.

[Nadir Zaitov]

На примере для трех элементов видно


a1, a2, a3
a1, a4, a5
a1, a6, a7

a2, a4, a6
a2, a5, a7

a3, a5, a6,
a3, a4, a7
Интересное замечание - каждый элемент встречается ровно 3 раза. К чему оно - пока не знаю, но возможно именно поэтому их 7 карточек и получилось

[Nadir Zaitov]

Сделал чорную работу, см. таблицуСсылки почему-то не открываются.

[Alisher Asror]

Меня не покидает подозрение, что набор неоптимален, и что дальнейшая оптимизация возможна.

Задача не конкретная

[Georgick]

Интересное замечание - каждый элемент встречается ровно 3 раза. К чему оно - пока не знаю, но возможно именно поэтому их 7 карточек и получилось

увы, для случая четырёх элементов симметричности уже не наблюдается.

[Nadir Zaitov]

увы, для случая четырёх элементов симметричности уже не наблюдается.Вы сделали перебор возможных карточек?