Минимальное количество методов.

[an2ancan]

Здравствуйте, помогите разобраться.

Михаил 20 раз решал задачи классификации. В каждой задаче он использовал ансамбль из пяти различных классификаторов, причем никакую пару классификаторов он не применял более одного раза. Каково минимально возможное число известных Михаилу классификаторов?

Мне кажется надо решать через графы. Пусть каждая вершина в графе - это классификатор. Ребро показывает, использовались ли 2 вершины в паре для решения задачи. Каждая решенная задача представляет собой полный подграф из 5 вершин. Значит, нужно подорать граф, состоящмй из 20 подграфов с минимальным количеством вершин. Дальше не знаю.

[vpb]

Да нет, не через графы. Прямо-то решение писать нельзя. Попробуем то же, с уменьшенными параметрами.
Дано, что $X$ --- некоторое множество, $L_1,\ldots,L_6$ --- шесть его подмножеств, причем в каждом 3 элемента. Известно, что любая пара элементов $x,y\in X$ лежит или ровно в одном из подмножеств $L_1,\ldots,L_6$, или вообще ни в одном. Спрашивается, сколько при этом может быть элементов в $X$ (наименьшее возможное число)? Прикиньте так, чисто комбинаторно, поперебирайте различные варианты.

[an2ancan]

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

[vpb]

Жаль. Ну давайте еще проще. Пусть у нас есть всего три тройки, и мы знаем, что каждая пара лежит не более чем в одной тройке. Что тогда можно сказать о том, сколько элементов может быть в $X$?

-- 05.02.2018, 23:53 --

И еще попробуйте доказать такой общий факт. Пусть у нас во множестве $Y$ есть $a$ подмножеств, в каждом из них по $b$ точек, и известно, что каждая точка лежит не более чем в $c$ подмножествах. Тогда $|Y|\geq ab/c$.

[an2ancan]

Простите за долгое отсутствие

vpb в сообщении #1290461 писал(а):

Жаль. Ну давайте еще проще. Пусть у нас есть всего три тройки, и мы знаем, что каждая пара лежит не более чем в одной тройке. Что тогда можно сказать о том, сколько элементов может быть в $X$?

Минимальное количество элементов $X$ - 6. Кажется

vpb в сообщении #1290461 писал(а):

И еще попробуйте доказать такой общий факт. Пусть у нас во множестве $Y$ есть $a$ подмножеств, в каждом из них по $b$ точек, и известно, что каждая точка лежит не более чем в $c$ подмножествах. Тогда $|Y|\geq ab/c$.

Я не уверен, как доказатать это строго, но если пердроложить что каждая точка принадлежит $c$ подмножествам, тогда количество точек равно $ab/c$, и это и есть минимально возможное количество точек

[vpb]

an2ancan
рад что Вы продвигаетесь в решении.

an2ancan в сообщении #1292637 писал(а):

Минимальное количество элементов $X$ - 6. Кажется

Да. А как это доказывается?

an2ancan в сообщении #1292637 писал(а):

Я не уверен, как доказатать это строго, но если пердроложить что каждая точка принадлежит $c$ подмножествам, тогда количество точек равно $ab/c$, и это и есть минимально возможное количество точек

Не знаете, как доказать строго, попробуйте своими словами.

[an2ancan]

vpb в сообщении #1292648 писал(а):

an2ancan в сообщении #1292637

писал(а):
Минимальное количество элементов $X$ - 6. Кажется Да. А как это доказывается?

Ну по формуле включений-исключений:

$\left\lvert X \right\rvert = 3 \cdot 3 - \sum\limits_{i\ne j} (a_i \cap a_j)$

Масксимальное количество пересечений из 3 элементов:

$C_3^2 = 3$

Выходит, что $\left\lvert X \right\rvert = 6$

vpb в сообщении #1292648 писал(а):

Не знаете, как доказать строго, попробуйте своими словами.

vpb в сообщении #1292648 писал(а):

если пердроложить что каждая точка принадлежит $c$ подмножествам, тогда количество точек равно $ab/c$, и это и есть минимально возможное количество точек

[vpb]

an2ancan в сообщении #1292669 писал(а):

Ну по формуле включений-исключений

Да, в данном случае можно так. Однако, формула включений исключений, вообще говоря, дает не равенство, а неравенство (каламбур получился...). В полном виде она выглядит как
$ |\cup_i X_i|=\sum_i|X_i|-\sum_{i<j}|X_i\cap X_j|+\sum_{i<j<k}|X_i\cap X_j\cap X_k|-\ldots $,
что в нашем случае приводит к неравенству
$|X|\geq |L_1\cup L_2\cup L_3|=\sum_i|L_i|-\sum_{i<j}|L_i\cap L_j|+|L_1\cap L_2\cap L_3|$,
откуда $|X|\geq 6$. Однако это рассуждение не доказывает, что конфигурация, для которой $|X|=6$, действительно существует (так что может быть в принципе, что минимальное возможное значение для $|X|$ --- это $7$, $8$, или что-то еще больше). Можете Вы предъявить такую конфигурацию в явном виде?

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

Скажите еще, а Вы какие-нибудь книжки по дискретной математике, комбинаторике и т.д. когда-нибудь читали? Если да, то какие?

[an2ancan]

Ну коогда я читал Виленкина "Комбинаторика". )

vpb в сообщении #1292693 писал(а):

Можете Вы предъявить такую конфигурацию в явном виде?

Боюсь, что нет ( .

[vpb]

Вопрос очень простой (настолько простой, что, как говорится, дальше некуда). Возможно, Вы просто не понимаете, в чем задача? Переформулирую ее другими словами. Рассмотрим множество $X=\{1,2,3,4,5,6\}$. Требуется указать какой-нибудь пример трех подмножеств $L_1, L_2,L_3\subseteq X$ таких, что $|L_1|=|L_2|=|L_3|=3$ и каждое из пересечений $|L_1\cap L_2|$, $|L_1\cap L_3|$, $|L_2\cap L_3|$ содержит не более одной точки.

В Виленкине того, что нужно, увы, нет. Я, возможно, еще кое-что из литературы поищу, что имеет отношение к задаче.

[an2ancan]

Да,простите, я не понял вопроса. Пример такой конфигурации:

$123$
$145$
$356$

[vpb]

Да, правильно. Попробуйте решить аналогичную задачу (т.е., каково минимальное $|X|$) для случая 4-х троек, тоже посредством рассмотрения разных конфигураций (при этом формула включений-исключений, возможно, не понадобится. Она тут, вообще говоря, ни при чем).

[an2ancan]

Тоже 6

$123$
$145$
$356$
$246$

[vpb]

Да, правильно. Теперь рассмотрите случай 5 троек.

[an2ancan]

7 элементов:

$123$
$456$
$147$
$257$
$367$