$%20$% одноклассников написали списки из $%5$% фильмов, которые им нравятся. Оказалось, что любые два списка имеют не более чем $%m$% одинаковых фильмов. Классный руководитель загрузил все эти фильмы на ноутбук.

Каково минимальное количество фильмов может быть на ноутбуке, если а) $%m=1$%; б) $%m=2$%?

задан 5 Ноя 13:03

1

У меня получилось а) $%21$% фильм; б) не менее $%12$% фильмов, но пример есть только для $%14$% фильмов.

(7 Ноя 23:37) EdwardTurJ

@EdwardTurJ: оценки я получил, а примеры пока что не знаю как строить.

(8 Ноя 18:15) falcao
1

А что, разве covering designs еще здесь не всплывали? https://math.ccrwest.org/gordon/hcd.pdf

(8 Ноя 18:36) knop

Но я совершенно не понял, как получился пример на 14, когда вроде бы классическая (ну, в этой области) оценка равна 20.

(8 Ноя 18:42) knop

@knop: задачи на эту тему бывали, и у меня даже есть скачанная книга с главами о covering designs, но я туда пока не успел заглянуть, чтобы сверить с уже известными фактами.

(8 Ноя 19:26) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
2

$%F$% одноклассников написали списки из $%k$% фильмов. Оказалось, что любые два списка имеют не более чем $%m$% одинаковых фильмов.

Оценим снизу $%n$% - количество фильмов. Пар фильмов не более, чем $%F\cdot C_k^{m+1}$%, а с другой стороны, их $%C_n^{m+1}$%, отсюда $%C_n^{m+1}\geqslant F \cdot C_k^{m+1}$%.

Система Штейнера $%S(t,k,n) $% - это $%n$%-элементное множество $%S$% вместе с набором $%k$%-элементных подмножеств $%S$% (называемых блоками), причём каждое $%t$%-элементное подмножество $%S$% содержится ровно в одном блоке.

Наша система $%N(m,k,n)$% - это $%n$%-элементное множество $%N$% вместе с набором $%k$%-элементных подмножеств $%S$% (называемых блоками), причём каждое $%m+1$%-элементное подмножество $%N$% содержится не более, чем в одном блоке.

Обозначим через $%|S(t,n,k)|$% и $%|N(m,k,n)|$% количество $%k$%-элементных подмножеств в соответствующих системах. Заметим, что если существует система Штейнера $%S(m+1,k,n)$%, то существует наша система $%N(m,k,n)$%, для которой $%|N(m,k,n)|\leqslant\|S(m + 1,k,n)|$%.

а) $%F=20,k=5,m=1$%. Наша система $%N(1,5,n)$%. Из оценки имеем $%n\ge21$%. Существует система Штейнера $%S(2,5,21)$% с $%|S(2,5,21)|=21$% (проективная плоскость порядка 4), поэтому существует система $%N(1,5,21) $%.

alt text

б) $%F=20,k=5,m=2$%. Наша система $%N(2,5,n)$%. Из оценки имеем $%n\ge12$%. Наименьшее $% $%, для которого существует система Штейнера $%S(3,5,n)$% с $%|S(3,5,n)|\ge20$% - это $%n=17$% с $%|S(3,5,17)|=68$%. Если из системы Штейнера $%S(3,5,17)$% удалить блоки с элементами $%15,16,17$%, то получим $%N(2,5,14)$% с $%|N(2,5,14)|=22$%. alt text

ссылка

отвечен 8 Ноя 19:56

изменен 8 Ноя 22:04

А 11 для пункта б) точно мало? А то вот вроде оно есть. https://math.ccrwest.org/cover/show_cover.php?v=11&k=5&t=3

2 3 4 5 6

2 3 7 8 9

1 2 3 10 11

1 7 8 9 11

4 6 7 8 10

1 4 5 6 11

5 6 7 9 10

4 5 8 9 10

1 3 5 9 10

3 5 7 8 11

1 3 4 8 10

3 4 7 9 11

1 3 6 7 10

1 2 4 6 9

3 6 8 9 11

1 2 5 6 8

2 6 7 10 11

2 4 8 10 11

1 2 4 5 7

2 5 9 10 11

(8 Ноя 20:18) knop
1

А, вижу в чем проблема. Да, задача немного отличается от стандартной covering design. Надо подумать, как ее сводить

(8 Ноя 20:21) knop

@knop: тут у второй и пятой снизу группы есть 3 общих элемента: 1, 2, 5.

Если есть 20 пятёрок, то в них входит 200 троек. Если они не повторяются, то набора из 11 фильмов мало, так как C_{11}^3 < 200. А число сочетаний из 12 уже больше.

(8 Ноя 20:44) falcao
1

@EdwardTurJ: а способ нахождения примеров был чисто эмпирический, или он продиктован какими-то соображениями?

(8 Ноя 20:46) falcao
2

для п.1 подходит проективная плоскость 4-го порядка( $%4^2+4+1=21$% точка, каждая прямая проходит ровно через 5 точек )

(8 Ноя 21:02) Sergic Primazon

@falcao: Дописал о примерах.

(8 Ноя 22:05) EdwardTurJ

@EdwardTurJ: спасибо! Теперь многое прояснилось. Пример с проективной плоскостью тут напрашивается -- я просто на числа не посмотрел как следует. А с системами Штейнера это вещь более запутанная -- я этих вещей не помню, то есть такой пример не построил бы, скорее всего.

(8 Ноя 22:39) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×1,005

задан
5 Ноя 13:03

показан
209 раз

обновлен
8 Ноя 22:39

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru