combinatorics

[stephanson12]

Hello, is there anyone who can help me solve this question? All little tips are welcome. thank you!


At a party, there isn't a single boy who has danced with every girl, but every girl has
danced with at least 1 boy. Show that there are at least 2 couples Boy-Girl and Boy2-Girl2 who have danced, so that Boy does not dance with Girl2
and Boy2 did not dance with Girl.

 

[Dr.Peterson]

Hello, is there anyone who can help me solve this question? All little tips are welcome. thank you!


At a party, there isn't a single boy who has danced with every girl, but every girl has
danced with at least 1 boy. Show that there are at least 2 couples Boy-Girl and Boy2-Girl2 who have danced, so that Boy does not dance with Girl2
and Boy2 did not dance with Girl.

You call this both "beginning algebra" and "combinatorics", but I don't think it's either. If it's for a class, can you tell us what topic(s) you have been learning, that this might be intended to exercise?

The question strikes me as one involving logic and quantifiers. Or we could think in terms of relations, or graphs. What methods of proof are you familiar with?

In any case, I start questions like this by restating them in more precise ways, perhaps gradually changing the statement of each fact in ways that fit together better in my mind.

• For every boy, there is at least one girl he hasn't danced with.
• For every girl, there is at least one boy she has danced with.
• We want to prove the existence of two boys, B1 and B2, and two girls, G1 and G2, such that (B1, G1) and (B2, G2) are dancing pairs, but (B1, G2) and (B2, G1) are not.

So far, I've given no thought to how to prove it, only how to understand and represent the question. I might next try experiment with small numbers of people to see if I can find a counterexample; I'd be looking for what keeps me from doing do, which might suggest a proof.

Now, what thoughts have you had?

 

[blamocur]

Spoiler: A hint

For every girl randomly pick one boy she danced with.
For each boy [imath]b[/imath] there is a subset [imath]G_b[/imath] of girls for whom [imath]b[/imath] was picked.
These subsets are non-intersecting.Now prove by contradiction: for any two [imath]G_1, G_2[/imath] show that if the statement is not true than boy #1 danced with every girl from [imath]G_2[/imath] and vice versa.