Prom Partners

A school is arranging a prom party. There are as many girls as there are boys. Everyone has a list or personal preferences on whom they would like to dance with, but obviously some girls and some boys are more popular than others. To avoid cat fights and ewww moments and people ending up not coming to the prom because they have no partner, the school makes the following arrangement.

1. Everyone gets together in the school gym.

2. In alphabetical order, the boys go ask girls to be his partner, in descending order of preference until they find a girl who says "yes" or end up with their current partner.

2a. If the girl asked has no partner or prefers the boy asking to her current partner, she'll say "yes" and the two become partners.

2b. If the girl asked has a partner already and prefers that partner to the boy asking her, she'll say "no" and the boy asks the next person on his list.

3. Once all boys have asked the process repeats over and over again until a time when no swapping takes place anymore.


Questions;

does this system always pair up every boy with a girl?

does it matter if the roles are reversed, that is, girls do the asking?

Originally posted by talzamir
A school is arranging a prom party. There are as many girls as there are boys. Everyone has a list or personal preferences on whom they would like to dance with, but obviously some girls and some boys are more popular than others. To avoid cat fights and ewww moments and people ending up not coming to the prom because they have no partner, the school makes ...[text shortened]... with a girl?

does it matter if the roles are reversed, that is, girls do the asking?

1. I don't get the "end up with their current partner"

If the starting condition is that boys and girls are paired in alphabetical oder I can answer your question:

Yes. Since every boy has a partner, and the question ios only if the partner will be changed. This needs the further condition that a rejected boy is paired with the girl left by the succesful contender.

The outcome is of course independent of the sex.

If the starting condition is "no pairing" we can end up with unattractive boys and unattractive girls who still won't pair, which makes the answer "no", and also here is no difference which sex asks.

The sex question yould be a cultural constant, but this is a much wider discussion.

With three boys and three girls, like this:

Alan: Likes Beatrice first, then Christine, then Alice.
Brad: Likes Beatrice, then Alice, then Christine.
Chris: Likes Alice, then Beatrice, then Christine.

Alice: likes Chris, then Alan, then Brad.
Beatrice: likes Chris, then Brad, then Alan.
Christine: likes Chris, then Alan, then Brad.

First round:
Alan goes to Beatrice. Alan and Beatrice are now a prom couple.
Brad goes to Beatrice. Beatrice likes him more than Alan, and dumps Alan.
Chris goes to Alice. Alice and Chris are now a prom couple.

Results:
Alan alone
Brad and Beatrice
Chris and Alice
Christine is alone.

Round 2.
Alan goes to Beatrice. She says "no" as the prefers her partner Brad.
Alan goes to Christine. They are now a couple.
Brad has his first choice and doesn't change.
Chris has his first choice and doesn't change.

Round 3.
Alan goes to Beatrice. She says "no" as she prefers Brad.
Alan's second choice is Christine, his current partner, so he stays put.
Brad has his first choice so he doesn't go around looking for anyone better.
Chris has his first choice so he stays put too.

No swapping took place on round 3 so the process ends. Everyone has a partner.
* Alan-Christine
* Brad-Beatrice
* Chris-Alice.

So,
* if the boys are in a different order, do the couples form differently?
* do the couples form differently if the girls are the ones who do the asking?
* does this process always end up with everyone getting someone as partner, no matter the preferences of each? if yes, how long can it take? if no, give an example of preferences where the process causes eternal swapping or leaves someone without a partner?

ideal would be a solution for n of each gender.

Originally posted by talzamir
does this system always pair up every boy with a girl?

does it matter if the roles are reversed, that is, girls do the asking?

Of course not, in both cases. It is always possible for there to be a boy whom no girl will say "yes" to, or a girl whom no boy is willing to even ask; and vice versa is equally possible.

Not to mention that there are almost never exactly the same number of boys as there are girls...

Richard

For crying out loud, it's a math problem. Just humor me, will you, groove with it and accept there are n boys and n girls? Of course I could have asked about pairing of elements A1..An and B1..Bn with a matrix of preferences for each, but whatever. If it's a problem that for a prom dance there would be n boys and n girls, fine, let's say that if they don't match up otherwise, then George and Henry will be suitably motivated by the headmaster, and end up called Georgina and Henriette for the duration of the prom. If that doesn't suffice, Arnold the PE teacher joins in too, possibly in a skirt and calling himself Arnoldine, and almost certainly ending up as the least appealing 'girl'. By hook or crook, it is possible to end up with as many boys (or "boys" ) and girls (or "girls" ), n of each.

I don't find it it obvious that some would be left without partners, if the problem is as it was written. Even the most hideous boy will be on every girl's list, though probably in the last place. Ditto for girls. So if John Blutarsky is the first boy in line, showing up a bit drunk in wearing nothing but a toga, and his first choice is Candy the captain of the cheer leader team, then Candy has to accept John. The two are a pair even if he is the last choice on Candy's list, and will keep her as his partner until or unless someone whom Candy finds more appealing asks her to be with him instead of with John. So, as I see it, it is not obvious anyone would be left without a partner; it could be unlikely, or even impossible for that to happen. But is it?

Boys asking vs girls asking:

Alan wants Alice first, Beatrice second.
Bob wants Beatrice first, Alice second.

but

Alice wants Bob first, Alan second.
Beatrice wants Alan first, Bob second.

What happens? If boys ask,

Alan asks Alice. She has no partner so she has to say yes.
Bob asks Beatrice. She has no partner either so she too has to say yes.

And that's where it ends. Alan-Alice, Bob-Beatrice.

But if the girls do the asking, Alice asks Bob, Beatrice asks Alan and the girls are happy and stop asking. So it's Alice-Bob, Beatrice-Alan, not Alan-Alice, Bob-Beatrice.

Is that a rare special case, or is it commonplace for the pairs to differ depending on whether the girls or the boys do the asking?

Does each boy (or girl) contains a list of preferred girls (or boys) n long? If the answer is yes then I believe the answer will be yes to your original question, and I think you wouldn't need to go through the alphabetical process to get 100% pairings. Otherwise it is an issue of constraint management, and those with the most constraints (i.e. smallest number of preferences) must be dealt with using a non-alphabetical manner.

P.S. I don't think your last example is a rare case.

P.P.S. An in answer to your 4 questions in your 2nd post:
1) yes but it depends on the girls preferences
2) yes assuming the boys preferences do not exactly match the girls and they are not inversely paired (see 4 below)
3) yes assuming each person has a list of preferences n long
4) The actual number of rounds will depend on the number of 'bumps' which is dependant on the sequence and preferences. I'm guessing the maximum number of rounds would be n assuming the girls preferences were in contra-alphabetical order, and each girl had the identical list of preferences.
5) I don't believe eternal swapping would be possible because a girl who bumps a boy cannot then change her order of preference (well not in the real world)

Yes, on orders of Arnold (Arnoldine) the PE teacher, each boy lists every girl in a descending order of preference, and each girls lists every boy in a descending order of preference. One can also assume that the girl preferences (and boy preferences) are not identical, though they are likely to correlate quite a bit.

Non-alphabetical.. so the same pairs are formed on matter in which order the boys ask?

As was already pointed out, this is not really a real-world situation. But, say, the whole data is put into a computer which then provides the "best" pairing, there is not much time for people to change their minds. Some might wince, but every boy would be in a situation where if he gets his k'th preference as partner, all the girls he prefers to his partner prefer their current partner to him.

Would this be ideal for all?

Originally posted by talzamir
Even the most hideous boy will be on every girl's list, though probably in the last place. Ditto for girls.

You have led a very sheltered life in high school. I suggest asking the most hideous of your pupils, or perhaps the most popular, whether this assumption is even close to realistic. You might be surprised at the answers.

Richard

Probably wouldn't be as a. there is no such thing as a prom in Finland and b. I am well aware that the assumption is just about as realistic as turning Arnie into Arnoldine. Not that it stopped the people who made the movie _Junior_ back in '94 though perhaps it should've.

It's a logic puzzle. Insisting on realism is imo silly - just enjoy it. It feels like criticizing the lack of realism about the rice promised to the inventor of the chess game, which was 2^64-1 grains. If a single grain of rice has a volume of about 5mm^3 and the chessboard in question measures about 78 cm wide by 78 cm long, the height of the pillar of rice is

(2^64 -1) * 5 / 780^2

which is about 1.5 * 10^14 millimeters. That's 150 million kilometers - a pillar of rice that reaches from the earth to the sun.

I find that fascinating. Not realistic at all, but fun. Ditto for puzzles.

Originally posted by Shallow Blue
You have led a very sheltered life in high school. I suggest asking the most hideous of your pupils, or perhaps the most popular, whether this assumption is even close to realistic. You might be surprised at the answers.

Richard

Criticizing this puzzle for realism is about the same as criticizing chess by saying that knights dont' move realistically.

Originally posted by forkedknight
Criticizing this puzzle for realism is about the same as criticizing chess by saying that knights dont' move realistically.

Not at all. The choices made are the heart of the puzzle. If additional assumptions are made about those choices - such as, "everybody is chosen by at least one person" - those should be stated in the puzzle.
Chess is not about a real battle, it's merely derived from one. Maths puzzles, however, very much are about applying maths to solve real-world problems. This is a good idea, but it does require the setter to state which real-world facts have been simplified. Otherwise, the pupil will come away with a distorted view of how maths applies to the real world - and be disappointed later when he finds out that real board meetings don't allow you to stab every third of your cow-orkers (and believe me, there are meetings where that is a disappointment...).

Richard

Point taken. I should have made it clearer that everyone lists ALL the members of the opposite gender in order of preference. So even if there is someone whom everybody dislikes, that person too is on all the lists of the opposite gender, and will get a partner.

As for the solution.. yes, this process ends up in sorting everyone to have a partner. But it does make a difference whether the boys or the girls do the asking. If boys do the asking, they get the arrangement that is the most favorable for boys and that the girls can live with - with the assumption that no partner at all is someone that they can't live with. If girls do the asking, they get the arrangement that is ideal for girls, and the boys can live with.

e.g.
Alan: A-B-C-D-E Alice: E-D-C-B-A
Bob: A-C-E-B-D Bella: D-B-E-C-A
Charlie: A-B-C-E-D Cathy: E-D-C-B-A
Dan: C-D-A-B-E Doris: E-B-A-D-C
Edward: B-D-A-C-E Eve: E-C-A-D-B

If boys do the asking:
Alan & Doris (4, 3)
Bob & Eve (3, 5)
Charlie & Alice (1, 3)
Dan & Cathy (1, 2)
Edward & Bella (1, 3)

If girls do the asking:
Alan & Eve (5,3)
Bob & Bella (4, 2)
Charlie & Alice (1,3)
Dan & Cathy (1,2)
Edward & Doris (2, 1)

So there is a rather drastic difference. The ones that ask tend to get the partners they like.