Question

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 1

Answer :-

This proposition will take at most 4 days to end

At whatever point a young lady is serenaded by at least one suitors, she won't be accessible from following day for other people. So as to expand the quantity of days of this proposition, we have to remember that just a single young lady is drawn nearer by all remaining young men in multi day.

for example All remaining young men have same most favorite young lady. Just a single couple shapes every day.

Exhibit alongside solidness / unstable defense:

Let the boy picked at sequential days are said to be A, B, C, D. Also, young ladies drew nearer at Day n is said Gn. for example a, b, c, d continuously.

Day 1: All four young men remain under the gallery of an equivalent young lady, a. One couple will be framed, and it will be a stable matching, as the young lady will pick her most loved among all young men and chose kid as of now has the young lady as her top choice.

Day 2: All 3 remaining young men will remain under the overhang of an another young lady, b. Again a couple will be framed, it probably won't be a stable matching. Steadiness of this matching relies upon the young lady's top choice. In the event that this young lady enjoys the person picked on day 1 superior to her most loved suiter, this matching will be an insecure one, else it will be a steady blending.

Day 3: Remaining 2 young men will remain under the gallery of another young lady c. Again a couple will be framed. It probably won't be a stable matching. Security of this blending relies upon the young lady's top choice. In the event that this young lady enjoys the folks picked on day 1 or day 2 superior to her most loved suiter, this matching will be a temperamental one, else it will be a steady blending.

Day 4: Last outstanding kid will remain under the gallery of the final young lady, d. Last couple will be framed. It probably won't be a stable matching. Steadiness of this blending additionally relies upon the young lady's top pick. In the event that this young lady prefers the folks picked on day 1, day 2 or day 3 superior to her just suiter, this blending will be a precarious one, else it will be a steady matching.