There are n male students and m female students. A male student and a female stu

Question

There are n male students and m female students. A male student and a female student can form a dancing pair if the male student is strictly taller than the female student. Suppose the heights of the n male students are b1, b2, …, bn, and the heights of the m female students are f1, f2, …, fm. We assume each student can participate in at most one dancing pair and we wish to form as many dancing pairs as possible.

Let b1, b2, …, bn be the heights of the n male students and f1, f2, …, fm be the heights of the m female students. Suppose the heights of male students are distinct and have been sorted such that b1 < b2 < … < bn. Moreover, the male student with height bk is taller than at least k female students, 1 k n.

Let b1, b2, …, bn be the heights of the n male students and f1, f2, …, fm be the heights of the m female students. Suppose each male student is taller than at least 3 female students and each female student is shorter than at most 3 male students. Prove that we can form n dancing pairs.

Explanation / Answer

given that n male students with heights ordered in ascending b1,b2,b3....bn and there are m female students with heights f1,f2....fm

Now given that at least 3 female are shorter than a male so the smallest male b1 will get a pair from the three females who are shorter. There are n-1 males and m-1 females again the above statement will be considered

As this process continues till every male is paired .....

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.