задачка

[Dandan]

задача не нова, мож кто и знает
Какое максимальное количество различных подмножеств n-элементного множества можно выбрать так, чтобы любые два из них имели ровно 1 общий элемент
Чему равно это число понять не трудно, только доказать это не так просто, хотя есть относительно короткое решение

[Capella]

количество = $n$?

Причём количество подмножеств будет таким: одно одноэлементное подмножество $\{ x_0 \}$ и $n-1$ двухэлементных множеств $\{ x_0, x_j\}, j \ne 0, j \in \{1, ..., n-1\}$

Добавлено спустя 18 минут 54 секунды:

Доказать нужно лишь, что наибольшее количество непересекающихся подмножеств будет сведено к одноэлементным множествам, по моему это очевидно.

[Genrih]

Capella писал(а):

количество = $n$?

По-моему не совсем так. Слишком как-то очевидно.
А множества вида: $\{ x_0, x_1, x_2 \}, \{x_0, x_1, x_3\}, ..., \{x_0, x_1, x_{n-1}\} , \{x_0, x_2, x_3\}, ... , \{x_0, x_2, x_{n-1}\}, ... \{x_0, ... , x_{n-1}\}$ ? .
Посчитать? - там что-то с "без повторений" (не могу посчитать ) .

[Capella]

Genrih писал(а):

Capella писал(а):

количество = $n$?

По-моему не совсем так. Слишком как-то очевидно.
А множества вида: $\{ x_0, x_1, x_2 \}, \{x_0, x_1, x_3\}, ..., \{x_0, x_1, x_{n-1}\} , \{x_0, x_2, x_3\}, ... , \{x_0, x_2, x_{n-1}\}, ... \{x_0, ... , x_{n-1}\}$ ? .
Посчитать? - там что-то с "без повторений" (не могу посчитать ) .

У тебя уже не ровно один элемент совпадает, а целых два - $x_0, x_1$

[RIP]

Capella
А как это дело свести к непересекающимся подмножествам?

Можно решать аналогично этой задаче.
Пусть выбраны подмножества $M_1,\ldots,M_k\subset\{x_1,\ldots,x_n\}$, $m_j=\#M_j$. Составим матрицу (кажись, это называется матрицей инцидентности) $A_{n\times k}$:

$$a_{ij}=\begin{cases}1,&x_i\in M_j;\\0,&x_i\notin M_j.\end{cases}$$

Далее, рассмотрим матрицу $B_{k\times k}=A^TA$. Тогда

$$b_{ij}=\#(M_i\cap M_j)=\begin{cases}1,&i\ne j;\\m_i,&i=j.\end{cases}$$

Поскольку все $m_i\geqslant2$, кроме, возможно, одного (которое может равняться 1), то матрица $B$ (строго) положительно определённая, в частности, невырожденная, т.е. её ранг равен $k$. С другой стороны, её ранг не превосходит ранга $A$, значит, не превосходит $n$.

[Capella]

RIP

С матрицей красивое решение, только, по моему, лучше рассмотреть
$M_1,\ldots,M_k \subset \{x_1,\ldots,x_{n-1}\}$, т.е. множество без общего элемента. Это будет более полезно при такой формулировке задачи:

Dandan писал(а):

Какое максимальное количество различных подмножеств $n$-элементного множества можно выбрать так, чтобы любые два из них имели ровно $k$ общих элементов

Ответ: $n-k+1$

[RIP]

Capella
Проблема в том, что в условии не сказано, что общий элемент для любых двух подмножеств один и тот же. Например, при $n=3$ и множеств $\{1;2\},\{1,3\},\{2;3\}$ такой элемент не найдётся.

[Dandan]

или, например, {1;2}, {1;3}, {1;4}, {2;3;4} при n = 4

[Capella]

Ну и что, надо взять более большое $n$, а если $n=3$, то и я тоже имею три множества $\{1\}, \{1,2\},\{1,3\}$
А вот $n= 4$ - какии подмножества возможны?!

Добавлено спустя 57 секунд:

Dandan

Вот именно, при $n=4$ и я имею 4 множества

[RIP]

Capella писал(а):

Это будет более полезно при такой формулировке задачи:

Dandan писал(а):

Какое максимальное количество различных подмножеств $n$-элементного множества можно выбрать так, чтобы любые два из них имели ровно $k$ общих элементов

Ответ: $n-k+1$

При $k>1$ в общем случае ответ неверен. Он, очевидно, верен при $n=k,k+1$, но, например, при $n=k+2$ можно взять $n$ множеств $M_j=\{1;2;\ldots;n\}\setminus\{j\}$. Вот интересно, а каков всё-таки ответ?

[Capella]

RIP писал(а):

Capella писал(а):

Ответ: $n-k+1$

При $k>1$ в общем случае ответ неверен.

Не знаю, пока остаюсь при своём мнении. Там всё зависит от пересечений, вероятно надо посмотреть более подробно на числах (причём при достаточно большом $n$ относительно $k$). Например для $n = 3$ и $k = 2$ ответ верен, например одно из правильных решений: $\{1,2\}, \{1,2,3\}$ и формула работает - $3 - 2 + 1 = 2$
Интересно проверить для $n = 5, k = 3$ и $n = 10, k = 3$

Добавлено спустя 18 минут 32 секунды:

Мне кажется мы ещё как то по разному понимаем условие. У меня складывается впечатление, что Вы делаете вот такой вариант:
1 группа: {12}, {123}
2 группа: {13}, {123}
3 группа: {23}, {123}
Отсюда делается вывод, что подмножеств 4: {12},{23},{13},{123}
Но ведь тогда не выполнятеся условие, что у любых двух подмножеств количество одинаковых элементов k. Ключевое слово здесь "любые", оно должно быть отнесено ко всем 4 подмножествам.

[Capella]

Наконец-то у меня дошли руки подсчитать вручную случай $n=5, k=3$ и действительно там получается больше. Я тоже пока общую формулу не знаю Надо будет подумать