Выборки по три из n (один общий элемент у пары)

[muhammet]

Имеется конечное множество $n$. Вопрос: Сколько выборок из $n$ по три можно сделать таких, чтобы любые две выборки имели только один общий член?

[gris]

Имеется в виду — ровно один общий член?
То есть для n=5 это будет 123 145 — две выборки. Случай 234 125 как бы изоморфен предыдущему и в расчёт не входит. Или надо его учитывать? Считаются ли пары выборок, не имеющих ни одного общего члена? Наверное нет.

Для n=6 123 145 246 356 — 4 выборки.

В общем, для каждого n вполне можно посчитать вручную. Когда-нибудь это закончится.

[Sonic86]

Если совсем будет непонятно как делать, то можете задачу свести к задаче поиска максимального независимого множества в графе, которая, в свою очередь, сводится к задаче булева линейного программирования размерности $\binom{n}{3}$ (получится регулярный граф специального вида со степенью вершин $3(n-3)$). Из нее можно получить тривиальную оценку для числа подмножеств $k \leq \frac{\binom{n}{3}}{2}$, но она очень грубая.

Это если условие задачи понимать как "пересечение любой пары подмножеств содержит не более одного элемента"...

-- Сб апр 09, 2011 22:10:11 --

Можете использовать жадный алгоритм для оценки снизу числа $k$: пишем упорядоченные тройки в массив и проходим по ним и включаем во множество $M$, если тройка не пересекается с уже существующими, иначе - не включаем. В итоге $k \geq |M|$.
Можно отсюда попытаться сделать приближенную оценку сверху. Пусть мы включаем в $M$ множество $A$, включающее текущую вершину $j$, причем для всех $i<j$ не может быть $i,j \in A$, поскольку множество, содержащее эти вершины может быть в $M$. Тогда в $A$ могут быть включены лишь вершины из списка $j+1,...,n$ - не более $\frac{n-j}{2}$ пар, а значит не более $\frac{n-j}{2}$ множеств $A$, откуда $k_n \leq \sum\limits_{j=1}^n \frac{n-j}{2} = \frac{n(n-1)}{4}$.

-- Сб апр 09, 2011 22:12:34 --

Например, для $n=3,...,8$ у меня вышло $k_n=1,1,2,4,6,7$, а значения оценки $1,3,5,7,10,14$

[VAL]

muhammet в сообщении #432860 писал(а):

Имеется конечное множество n. Вопрос: Сколько выборок из n по три можно сделать таких, чтобы любые две выборки имели только один общий член?

Что значит "конечное множество n"?
Сколько элементов в этом множестве?

Полагаю, что все же имелось в виду не множество n, а множество из n элементов.
В этом случае Ваш вопрос относится к теории блок-схем. Прочитать про блок-схемы (не в информатическом, а в комбинаторном смысле этого термина) можно в книжке М.Холл "Комбинаторика".

Я погорячился. Это не блок-схемы. Там каждый элемент обязан принадлежать фиксированному числу блоков.

(Но книжку почитать все равно полезно )

[gris]

Попробовал графически изобразить это дело и решил посмотреть в OEIS. Похожую последовательность обнаружил. Это The orchard-planting problem. Только не уверен — действительно ли она и задача ТС изоморфны.
Очень интересно. Только я по-другому рисовал.
И, по-моему, это совсем не то:-(

[VAL]

Sonic86 в сообщении #432903 писал(а):

Это если условие задачи понимать как "пересечение любой пары подмножеств содержит не более одного элемента"...

При всей странности условия (это я опять про "множество n") там вроде бы ясно написано "только один общий элемент", а не "не более одного общего элемента". Хотя ТС виднее...

Цитата:

Например, для $n=3,...,8$ у меня вышло $k_n=1,1,2,4,6,7$, а значения оценки $1,3,5,7,10,14$

А разве при $n=7$ не годятся тройки $(1,2,3),(1,4,5),(1,6,7),(2,4,6),(2,5,7),(3,4,7),(3,5,6)$? Или я чего-то проморгал?

-- 09 апр 2011, 21:33 --

gris в сообщении #432983 писал(а):

Попробовал графически изобразить это дело и доисовался до случая $n=12$ и решил посмотреть в OEIS. Правда я ошибся в 10 шариках, но тем не менее последовательность обнаружил. Это The orchard-planting problem. Только не уверен — действительно ли она и задача ТС изоморфны.

У меня другая последовательность получается. У Sonic86 - третья. Интересно, какую имел в виду ТС?

[gris]

Вот моё графическое видение и то, что у Вольфрама (справа).
Я считал, что ровно один общий элемент у каждой пары. Слово "только" какое-то нестрогое.



Задача мне понравилась, хотя она, наверное, очень хорошо известна в любой формулировке.
Или это не одно и то же с The orchard-planting problem?

[Sonic86]

VAL писал(а):

При всей странности условия (это я опять про "множество n") там вроде бы ясно написано "только один общий элемент", а не "не более одного общего элемента". Хотя ТС виднее...

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

VAL писал(а):

А разве при $n=7$ не годятся тройки $(1,2,3),(1,4,5),(1,6,7),(2,4,6),(2,5,7),(3,4,7),(3,5,6)$? Или я чего-то проморгал?

Проморгал я значит, торопился

Последовательность в OEIS я тоже нашел, но orchard гугл не переводит + там еще какие-то деревья упоминались, поэтому видимо это не то (только если каким-то сложным образом)

[VAL]

Если допустить, что тройки могут не пересекаться, то для n, сравнимых с 1 и 3 по модулю 6, ответ будут давать системы троек Штейнера (все таки блок-схемы). Для них число троек подсчитывается элементарно $\frac{n(n-1)}6$.

[muhammet]

VAL в сообщении #433021 писал(а):

Для них число троек подсчитывается элементарно $\frac{n(n-1)}6$.

Спасибо.
У меня вывод этой формулы был такой:
Первый элемент выбирается n способами.
Второй элемент выбирается n-1 способами.
Третий элемент можно выбрать только одним способом, иначе в двух выборках два первых будут одинаковы.
Все делиться на 6, чтобы исключить повторы.
Но эта формула работает для n=3,5,7 ... Можно ли считать, что для других n количество выборок будет строго меньше, чем посчитано по этой формуле?

[VAL]

muhammet в сообщении #433560 писал(а):

VAL в сообщении #433021 писал(а):

Для них число троек подсчитывается элементарно $\frac{n(n-1)}6$.

Но эта формула работает для n=3,5,7 ...

Для 3 и 7 понятно. Это, как раз, числа сравнимые с 3 и 1 по модулю 6. А каким образом у Вас для 5 эта формула работает? Во-первых, там ответ целым не будет. А во-вторых, даже если взять целую часть, получится завышенное число троек.

Цитата:

Можно ли считать, что для других n количество выборок будет строго меньше, чем посчитано по этой формуле?

Сначала уточните условие (Вас ведь просили об этом все, кто заинтересовался Вашей задачей). Ответ $\frac{n(n-1)}6$ получается только в предположении, что тройки должны иметь не более одного общего элемента (а у Вас написано "только один общий элемент"), и только для n, сравнимых с 1 и 3 по модулю 6. Для остальных n вышеприведенная формула может служить заведомо(?) завышенной оценкой.

[Sonic86]

Я не очень разбираюсь, но как-то странно, что число легко считается только по нескольким классам вычетов, а по остальным классам - нет. Можно как минимум попробовать вычислить отклонения от обобщенной формулы эмпирически и попробовать понять зависимость в прочих случаях хотя бы грубо.

[VAL]

Sonic86 в сообщении #433581 писал(а):

Я не очень разбираюсь, но как-то странно, что число легко считается только по нескольким классам вычетов, а по остальным классам - нет. Можно как минимум попробовать вычислить отклонения от обобщенной формулы эмпирически и попробовать понять зависимость в прочих случаях хотя бы грубо.

А что странного?

Для $n=6k+1$ и $n=6k+3$ существуют штейнеровские системы троек (любые два элемента определяют ровно одну тройку). для остальных $n$ штейнеровских систем троек не существует. Это известный факт. Доказательство можно найти у Холла.

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

А насчет отклонения... При малых $n$, не сравнимых 1 и 3 по модулю 6, $\left{\lfloor}\frac{n(n-1)}{6}\right{\rfloor}$ дает ответ, превышающий правильный ровно на 1. Может, так и при других будет...

[Sonic86]

VAL писал(а):

А что странного?

Я имел ввиду только саму формулу $\frac{n(n-1)}{6}$, а не штейнеровские тройки. Для остальных классов вычетов просто может быть что-то похожее:

VAL писал(а):

При малых $n$, не сравнимых 1 и 3 по модулю 6, $\left{\lfloor}\frac{n(n-1)}{6}\right{\rfloor}$ дает ответ, превышающий правильный ровно на 1. Может, так и при других будет...

[muhammet]

VAL в сообщении #433590 писал(а):

Для $n=6k+1$ и $n=6k+3$ существуют штейнеровские системы троек (любые два элемента определяют ровно одну тройку). для остальных $n$ штейнеровских систем троек не существует. Это известный факт. Доказательство можно найти у Холла.

Спасибо (конечно имелось в виду не более одного общего элемента).