Теорема Холла (Hall's marriage theorem)

[bayah]

Теорема гласит:
"Если у любых $k$ юношей $(1 \leq k \leq n)$ имеется не меннее $k$ знакомых девушек, то их можно так поженить, что каждому юноше достанется по знакомой девушке."

Тут доказательство:
https://www.mccme.ru/s43/math/uroki/2009_2010/9mat_0910/spec/59_hall_lect.pdf
Как-то сложно мне кажется.

Разве нельзя так, например:

Рассмотрим случай, когда у $k$ юношей ровно $k$ знакомых девушки.
Покажем как сопоставить каждому юноше по знакомой девушке.
Выберем произвольного первого юношу. По условию ( для $k = 1$) у него есть одна знакомая девушка. Получается пара которую можно поженить.
Теперь возьмем второго юношу. Теперь ($k = 2$). У них вместе с первым ровно $2$ занкомых дувушки. Если даже у второго юноше среди знакомых девушка первого - то остается еще одна. То есть двоих тоже можно поженить. И так рассуждение можно продолжить далее до $n$.

В случае если у $k$ юношей более чем $k$ знакомых девушки, то это только добавляет возможностей сосатвить пары.

Что не так в таком доказательстве?

[grizzly]

bayah в сообщении #1320578 писал(а):

Если даже у второго юноше среди знакомых девушка первого - то остается еще одна.

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

[bayah]

grizzly в сообщении #1320593 писал(а):

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

Мм... Ну да, может. Это я не верно, да. Даже в случае если две девушки обе девушки только второго юноши то тоже не верно, так как тогда получается что у первого нет девушки.

Тогда так:
Так как первого юношу мы выбираем произвольно, то условие, что у $k$ юношей есть $k$ девушек верно для любого из юношей. То есть когда мы берем второго юношу в добавок к первому, то для него справедливо то же рассуждение что и для первого - то есть для него одного так же есть одна знакомая. Таким образом для них двоих две девушки не могут быть все девушками первого или второго. Одна непременно второго, а другая - второго.

[grizzly]

bayah в сообщении #1320617 писал(а):

Тогда так:...

Рассуждение не очень, но для случая $n=2$ я с натяжкой мог бы его засчитать. Теперь попытайтесь очень аккуратно перейти к случаю $n=3$ и дальше -- потому как голословное "и т.д." совсем не выглядит очевидным.

-- 17.06.2018, 18:21 --

(Оффтоп)

bayah в сообщении #1320617 писал(а):

Одна непременно второго, а другая - второго.

Чем-то напомнило момент из "По семейным обстоятельствам":
-- Одна живёт на Ки'евской, а другая -- на Киевской.
-- На одной улице, получается?
-- Как 'аз на 'азных!

Сорри, не удержался

[provincialka]

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

[bayah]

grizzly в сообщении #1320624 писал(а):

Одна непременно второго, а другая - второго.

Ну ды)
Одна непременно первого, а другая - второго.

grizzly в сообщении #1320624 писал(а):

Рассуждение не очень, но для случая $n=2$ я с натяжкой мог бы его засчитать. Теперь попытайтесь очень аккуратно перейти к случаю $n=3$ и дальше -- потому как голословное "и т.д." совсем не выглядит очевидным.

Так, ну дальше добавляем третьего юношу. И так как для любых двух юношей есть разные девушки, то они есть и для любых двух юношей из этих трех. А это значит что и у каждого из них своя девушка.
Далее для случая $n+1$ рассуждаем так же. Так как для случая $n$ верно, что у каждого из $n$ юношей своя девушка, то это верно для всех возможных случаев выбрать $n$ юношей из $n+1$. Но тогда и для $n+1$ юноши верно что у каждого из них своя девушка.

[grizzly]

bayah в сообщении #1320649 писал(а):

И так как для любых двух юношей есть разные девушки, то они есть и для любых двух юношей из этих трех. А это значит что и у каждого из них своя девушка.

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

Если Вы собираетесь латать своё "доказательство" под каждый контрпример, который я буду приводить, увольте. Ваше рассуждение можно спасти и для $n=3$ и даже дальше, но количество текста в аккуратном доказательстве Вашим способом будет расти по экспоненте.

[mihaild]

provincialka в сообщении #1320640 писал(а):

Можно ли составлять пары начиная с произвольной, или надо учитывать всю структуру знакомств?

Не каждая возможная пара участвует в каком-то наибольшем паросочетании. Например, если у нас есть ребра $(a_1, b_1), (a_1, b_2), (a_2, b_1)$ (и всё), то пару $(a_1, b_1)$ брать нельзя. Или вопрос не про это?

[provincialka]

mihaild
Про это, конечно! Но вроде ТС уже отказался от составления паросочетания "наращиванием"... Правда, я не очень поняла, чем он его заменил!

[bayah]

grizzly в сообщении #1320651 писал(а):

Посмотрите на рисунок 1 по Вашей ссылке -- там для любых двух юношей есть пара разных девушек, но сосватать всех нельзя.

При переходе от $2$ к $3$ я, конечно, еще учитываю и то что для $3$ юношей есть $3$ девушки.
В примере по ссылке, для любых двух - есть, а для трех - уже нет (Kai, Piter, Edmund).
То есть, так как любых двух парней можно переженить и в частности можно пережинить любых двух парней из трех, то добавляя условие для трех парней ( что они знают как минимум трех дувушек) женим любого из парней который знаком с третьей девушкой, остаются двое - которых поженить можно.

[grizzly]

Вы используете кусочно-непрерывную логику, а этого делать нельзя.

bayah в сообщении #1320717 писал(а):

То есть, так как любых двух парней можно переженить и в частности можно пережинить любых двух парней из трех, то добавляя условие для трех парней ( что они знают как минимум трех дувушек) женим любого из парней который знаком с третьей девушкой, остаются двое - которых поженить можно.

Выше mihaild объяснял на примере, почему нельзя просто взять и поженить "любого из парней который знаком с третьей девушкой". Потому что оставшиеся две пары парней и девушек вовсе не обязаны удовлетворять условию задачи для $n=2$. Так просто здесь индукцию применить не получится.

[bayah]

grizzly в сообщении #1320728 писал(а):

Выше mihaild объяснял на примере, почему нельзя просто взять и поженить "любого из парней который знаком с третьей девушкой". Потому что оставшиеся две пары парней и девушек вовсе не обязаны удовлетворять условию задачи для $n=2$. Так просто здесь индукцию применить не получится.

Ну да, любого не получится, но тогда заменим "любого" на "найдется такой что"?)

[mihaild]

bayah в сообщении #1320774 писал(а):

Ну да, любого не получится, но тогда заменим "любого" на "найдется такой что"?)

А почему найдется?

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