Post #88

Гипотеза Диница (сейчас теорема Гэлвина) утверждает следующее: На бал пришли n юношей и n девушек, каждая пара юноша-девушка умеет танцевать n из N>n предлагаемых на балу танцев. Тогда можно организовать танцы так, чтобы каждая пара потанцевала хотя бы раз. (Во время каждого танца можно отдыхать, либо танцевать его ровно с одним партнёром противоположного пола.) Доказательство (и в такой формулировке это менее удивительно, чем с латинскими квадратами) использует теорему Гейла — Шепли об устойчивом паросочетании: если у каждого юноши есть упорядоченный список предпочтения девушек и наоборот, то их можно всех поженить так, чтобы не нашлось не состоящей в браке пары, предпочитающей друг друга своим супругам. Сначала зададим базовые предпочтения юношей и девушек: пронумеруем тех и других остатками по модулю n, назовём тайной пары юноша-девушка остаток суммы номеров по модулю n. Пусть каждый юноша предпочитает девушек в порядке возрастания тайны (чем меньше тайна, тем привлекательнее девушка), а каждая девушка — в порядке убывания тайны. Вот бал начался, объявили вальс. Сейчас, конечно, порядок предпочтений изменился: каждому нравятся в первую очередь те партнёры, с которыми получится станцевать вальс, а они — в базовом порядке. Рассмотрим устойчивое паросочетание для таких порядков предпочтений. В нём некоторые пары могут танцевать вальс, они пусть его танцуют, остальные отдыхают. Теперь объявили полонез. Порядок предпочтений такой: в первую очередь нравятся партнёры, с которыми пока не танцевали и с кем получится станцевать полонез. В остальном всё как с вальсом. И так далее для каждого танца. Докажем, что любая пара, скажем, Саша и Наташа, танцевали друг с другом. Обозначим через m их тайну. Если они не танцуют друг с другом один из танцев, которые умеют, то по условию устойчивости это значит, что либо Саша предпочитает Наташе свою партнёршу, либо наоборот. Первое происходит, когда Саша танцует с девушкой, с которой у него тайна меньше m, и с которой он ещё не танцевал до этого, (таких девушек всего m, так что это может произойти не более m раз). Наоборот бывает у Наташи с юношами, с которыми у неё тайна больше m (таких юношей n-m-1). Итак, они могли пропустить не более m+(n-m-1)=n-1 из своих n танцев, поэтому танцевали друг с другом.