693
правки
Изменения
→Доказательство корректности
Все мужчины и женщины будут заняты.
|proof=
Предположим, что некоторый мужчина (<tex>A</tex>) не женат по завершении алгоритма. Тогда и некоторая женщина (<tex>a</tex>) незамужняя. По [[#observation2|наблюдению <tex>2</tex>]], <tex>a</tex> не получала предложений. Но <tex>A</tex> сделал предложения всем женщинам, так как он остался не женат. Получаем противоречие. Таким образом, все мужчины заняты.
Аналогичные рассуждения применяем для женщин. Пусть какая-то женщина незамужняя. Значит, есть мужчина, который остался не женат. Но мы доказали, что по завершении алгоритма все мужчины заняты. Снова пришли к противоречию.
