Одинокий волк
После применения алгоритма Гейла-Шепли для распределения выпускников медицинских колледжей по больницам, ещё острее встала проблема того, что в провинциальные больницы никто не идёт на практику. Хотя изначально предполагалось, что DAA должен решить эту проблему. Стало интересно, есть ли другие стабильные матчинги, в которых это не так.
На лекции был факт, который мы назвали «Lonely Wolf». Он заключается в том, что если агент остался без пары в одном стабильном матчинге, то он будет один в любом стабильном матчинге. Докажите его.
На лекции был факт, который мы назвали «Lonely Wolf». Он заключается в том, что если агент остался без пары в одном стабильном матчинге, то он будет один в любом стабильном матчинге. Докажите его.
Решение
Доказывать можно например от противного. Пусть где-то есть пара, где-то нет. Тогда нужно посмотреть на пару этого агента в (мэтче, где пара есть). Потом на его партнёра в другом матчинге итд.