Имеется множество из $%2n$% элементов. Рассматриваются всевозможные группы из $%n$% элементов этого множества. Из них нужно выбрать ровно половину групп так, чтобы каждый элемент входил ровно в половину из избранных групп, причём любые две избранные группы должны иметь хотя бы один общий элемент.

Для каких $%n$% это возможно?

задан 4 Ноя 10:41

изменен 4 Ноя 20:00

@EdwardTurJ: мне пока что непонятен смысл оговорки в конце. Выбирается половина всех сочетаний из 2n по n. Каждый элемент должен входить ровно в 1/4 из этого количества. Допустим, что никакие две группы не имеют общего элемента. Тогда всякий элемент входит ровно в одну из групп. Но так не бывает, поскольку число сочетаний не равно 4. Выходит, эта оговорка лишняя? Или я чего-то не понял?

(4 Ноя 18:56) falcao

@falcao: Вашего вопроса не понял. Пример для $%n=3$%:

{1,2,6}; {2,3,6}; {3,4,6}; {4,5,6}; {5,1,6}; {1,2,4}; {1,3,4}; {1,3,5}; {2,3,5}; {2,4,5}.

(4 Ноя 19:20) EdwardTurJ
2

По ссылке доказано, что это возможно в том случае, если $%2n-1$% - простое число. Для других $%n$% там вопрос не исследован https://math.stackexchange.com/questions/2853329/n-element-subsets-of-the-set-1-2-2n

(4 Ноя 19:43) Witold2357

@EdwardTurJ: мой вопрос состоял в следующем. Уберём слова "причём какие-либо две избранные группы должны иметь хотя бы один общий элемент". Что при этом нарушится? Станут ли возможными какие-то тривиальные конструкции этого рода?

(4 Ноя 19:51) falcao

@EdwardTurJ: сейчас я заглянул по ссылке и понял, что любые две избранные группы должны иметь общий элемент. У Вас же стоит квантор существования (какие-либо), что и сбило меня с толку.

(4 Ноя 19:54) falcao
1

@Witold2357: Мне кажется, что построение возможно для любого $%n\ne2^k$%.

@falcao: теперь вопрос понял. Поправил.

(4 Ноя 19:55) EdwardTurJ
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,005
×40

задан
4 Ноя 10:41

показан
83 раза

обновлен
4 Ноя 20:00

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

по почте:

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

по RSS:

Ответы

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

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