Упражнения с решениями Упражнение с решением 1

Имеется город, в котором n мужчин и n женщин пытаются вступить в брак. У каж- дого мужчины имеется список предпочтений, содержащий оценки всех женщин, а у каждой женщины — список предпочтений с оценками всех мужчин.

Множество всех 2n людей разделено на две категории: хорошие люди и плохие люди. Предположим, для некоторого числа к (1 < к < n - 1) имеются к хороших мужчин и к хороших женщин; следовательно, существует n - к плохих мужчин и n - к плохих женщин.

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

Покажите, что в каждом устойчивом паросочетании каждый хороший мужчина вступает в брак с хорошей женщиной.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Упражнения с решениями Упражнение с решением 1:

  1. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  2. РЕШЕНИЕ
  3. РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
  4. ПРИНЯТИЕ РЕШЕНИЙ
  5. РЕШЕНИЯ КСУ
  6. Не избегайте принятия решений
  7. ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
  8. ЗАДАЧА: РЕШЕНИЕ
  9. Принять решение
  10. Управленческие решения
  11. Решение проблем
  12. КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.
  13. Убеждения и решения
  14. Убеждения и решения
  15. НАЙДИТЕ РЕШЕНИЕ
  16. НАЧНИТЕ С ПРИНЯТИЯ РЕШЕНИЯ
  17. Получение информации и принятие решений
  18. Решение измениться
  19. Решение измениться