4. There are 4 boys (A, B, C, D) and 4 girls (a, b, c, d)...

 

Transcribed Image Text:

4. There are 4 boys (A, B, C, D) and 4 girls (a, b, c, d) who want to date. Each boy has a preference list, and so does each girl. A pair of a boy and a girl is called unstable if the boy has another girl he likes better, and so does the girl. For example, if the preference list of A is b> c> a>d and that of a is B > A>D> C, then the pair of A and a is unstable since A likes b better than a, and a likes B better than A. The aim is to find a stable matching of all 4 boys and 4 girls such that there is no unstable pairing. Consider the following proposal : Morning Each girl stands on her balcony. Each boy stands under the balcony of his favorite girl on his list and serenades her. If no girl on his list, he stays home. Afternoon: Each girl who has one or more suitors serenading her asks her favorite suiters out tomorrow. She tells the others she is not available. Evening Each shunned boy crosses the girl on his list. How many days (at most) does the above proposal end? Does it give a stable matching? Explain your answers. 4. There are 4 boys (A, B, C, D) and 4 girls (a, b, c, d) who want to date. Each boy has a preference list, and so does each girl. A pair of a boy and a girl is called unstable if the boy has another girl he likes better, and so does the girl. For example, if the preference list of A is b> c> a>d and that of a is B > A>D> C, then the pair of A and a is unstable since A likes b better than a, and a likes B better than A. The aim is to find a stable matching of all 4 boys and 4 girls such that there is no unstable pairing. Consider the following proposal : Morning Each girl stands on her balcony. Each boy stands under the balcony of his favorite girl on his list and serenades her. If no girl on his list, he stays home. Afternoon: Each girl who has one or more suitors serenading her asks her favorite suiters out tomorrow. She tells the others she is not available. Evening Each shunned boy crosses the girl on his list. How many days (at most) does the above proposal end? Does it give a stable matching? Explain your answers.

Answer rating: 100% (QA)

All this will take at most 24 days Explanation I think that the n... View the full answer