На танцы пришло 10 юношей и 12 девушек. Сколько есть вариантов составить из них пары на вечер так чтобы каждый танцевал с нечётным количеством партнёров.

задан 30 Сен '19 0:41

10|600 символов нужно символов осталось
0

Я понял условие так, что мы для каждой пары юноша-девушка предписываем, должны ли они станцевать. При этом каждый танцует с нечётным числом партнёров.

Рассмотрим один такой план: пусть юноши от 1 до 9 танцуют с одной девушкой, имеющей тот же номер, что и сам юноша, а 10-й танцует с тремя: 10-й, 11-й и 12-й. Рассмотрим какой-то другой план, где условие нечётности соблюдено. В обоих случаях речь идёт о подграфе в полном двудольном графе.

Введём понятие суммы подграфов по модулю 2. Берём объединение рёбер, и затем удаляем пересечение. Легко видеть, что сумма двух подграфов с условием нечётности степеней всех вершин есть подграф с условием чётности степеней. Обратно: если A -- построенный выше подграф, а B пробегает все подграфы с условием чётности, то A+B пробегает все подграфы с условием нечётности.

Тем самым, задача свелась к подсчёту случаев, когда каждый танцует с чётным числом партнёров. Загадаем для всех девушек кроме 12-й множество юношей, с которыми она должна станцевать. Подмножеств всего 2^10, и из них ровно половина имеет чётное число элементов. Это даёт 2^9 способов для каждой из 11 девушек, а всего получается 2^99 вариантов. Каждый из них продолжается до нужного плана единственным способом. А именно, если юноша танцует с нечётным числом девушек из числа первых 11, то предписываем ему танцевать с 12-й. При этом степени всех вершин кроме одной становятся чётными. Последняя вершина (для 12-й девушки) также будет иметь чётную степень, так как сумма степеней всех вершин чётна (лемма о рукопожатиях). Итого ответ 2^99.

ссылка

отвечен 30 Сен '19 1:10

А если в качестве графа А взять другой нечетный граф. Например, где с тремя танцует пятый парень. Разве это не будет другое множество вариантов?

(13 Окт '19 19:24) Дина123

@Дина123: если мы возьмём другой представитель нечётного графа, то после прибавления множества всех чётных мы снова получим множество всех нечётных. То есть от выбора представителей эта конструкция не зависит. Важно только, чтобы хотя бы один такой представитель был.

(13 Окт '19 20:08) falcao

@falcao почему A+B пробегает именно все подграфы с условием нечетности? Как это можно строго показать?

(13 Окт '19 22:51) Bazalt

@Evgeny Kondr...: если мы складываем по модулю 2 два подграфа, то все рёбра, исходящие из одной вершины, складываются по модулю 2. Чётное плюс нечётное даёт нечётное. Поэтому A+B будет нечётным. Тот факт, что при этом получается любой нечётный подграф, следует из того, что уравнение A+B=C для нечётного подграфа C имеет решение A=B+C. Это сумма двух нечётных подграфов, она чётна, поэтому входит в состав подграфов вида A+B, где A пробегает все чётные.

Это всё следует из самых общих соображений в духе теории групп, но здесь приходится рассуждать на более "кустарном" языке, с тем же смыслом.

(13 Окт '19 23:44) falcao

Спасибо большое за разъяснение! Почти стало понятно) А какое четное решение например нужно править к исходному А, чтобы получить то же самое А?

(14 Окт '19 13:49) Дина123

@Дина123: чтобы из A получить A, нужно прибавить пустой подграф, в котором нет рёбер. Он чётен (степени всех вершин равны 0, то есть они чётны).

(14 Окт '19 15:00) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,462
×624

задан
30 Сен '19 0:41

показан
464 раза

обновлен
14 Окт '19 15:00

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

по почте:

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

по RSS:

Ответы

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

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