What does your intuition tell you about the solution to this problem?

Okay, I’m taking the plunge. Warning . . . I’m awful at math and not great at logic questions that involved some type of “implied” math—and this might be one.

I say that Club A will still win every race. It would seem that in the first match where runners were randomly paired, Club B’s fastest runner lost regardless of whom he/she was racing. Maybe that’s the easy part to which you refer. But it seems that once the fastest on both teams were eliminated that the same logic applies.

I’m sure I’m wrong—I’m taking a chance on participating here, and I thank you for firing up some of my mental pistons this morning, @LostInParadise. Y’all go easy on me.

My intuition tells me to move to the next question lest I have to think about something difficult.

My intuition tells me that Club A must win every race. I am going to quickly explain my logic. If the Nth place club A member is slower than the Nth place club B member (this must be the case if club A was to lose a race), then in random pairing, the Nth place club A member must have been paired with a slower club B member of place greater than N. The club A members with a place greater than N, by definition, are slower than the Nth place of club A, which we have said is slower than the Nth place of club B. All club A members must also be randomly paired with slower club B members of place greater than N. By the pigeonhole principle, there are not enough club B members with place greater than N to be paired with the club A members with place greater than N plus the club A member with place N.

I actually think it is a strength in math (paradoxically) to have hardly any math intuition at all. Math is so often unintuitive and making false assumptions about the correct answer can lure you astray.

My intuition is not telling me much of anything. The only thing my intuition is telling me that the problem is more complex and intricate than what meets the eye, and that I therefore shouldn’t jump to any conclusions. But I’ll try to apply some minimal thought without looking at anyone else’s answers to keep it as intuitive as possible. Here’s my very rambling train of thought while looking at this problem:

First off all, should I assume an equal number of runners on each time?

If team A won every time the first time around, then their slowest runner must be faster than team B’s slowest runner (and possibly, but not necessarily, more members of team B), otherwise everyone in team B would necessarily be fast enough to beat him. Likewise, team B’s fastest runner must be slower than team A’s fastest runner (and possibly others on team A), otherwise no one from team A would have been able to beat him.

If, the first time around, the fastest runner on team B faced off against anyone but the fastest runner on team A, for example, the second fastest, then we know that both the second fastest and the fastest runner on team A are both faster than the fastest runner on team B, and therefore they’re both faster than the entire team B, and they will therefore both win their races in the second round. So we will call the person on team A that the fastest of team B first faced, team A’s “Xth” fastest person, and we know that team A will win at least X races. If X is equal to the number of people on a team (meaning that team B’s fastest runner lost to team A’s slowest runner, and we have no idea if this is the case), then A will win all the races. If X=1, which is the least forgiving assumption for team A as it means that the two fastest competed the first time, then this doesn’t give us any new information. Likewise, if the slowest runner on team A competed against the “Yth” slowest runner on team B, then team A will necessarily win at least Y races too.
Knowing that it is indeed possible for team A to win all the races, I want to try and determine now if it is possible for B to win any races. So I will analyze the least forgiving solution for A, which is when X=1 and Y=1 – that is, the fastest and slowest races faced off the first time. The second time, these two pairs will race again with victories for A. Now, I’m not quite certain about this, but I think we’re still left with the same situation we were dealing with before. Putting aside the two pairs that we’ve already considered, we’re left with a new group – the “average” runners – and again, of that group there is a fastest runner and a slowest runner on each team and I believe we can draw the same conclusions as last time – team A’s fastest and slowest runners will both be victorious, and we can continue this out into infinity. Team A will win every time, I think.

Poor team B.

If the number of runners on each team is different, it is possible to have team B win a race, if the fastest racer on team B was left out of the random pairing by chance, but does race in the second instance. The question does not say that the teams are of different size, in fact, it does not specify the sizes of the teams. If team A had more players than team B, then it would still win every race.

You guys all have better intuition than me. All the A team members win again. I should have mentioned that both teams are the same size. My immediate feeling was that it would be likely for some members of the B team to win

@Mariah , Intuition does play a role in mathematics. It acts as a guide for how to proceed.

@PhiNotPi gave a nice proof for those who can follow it.

Here is a similar proof that is not as compact but is a direct proof. We want to show that in general the nth fastest member of A is faster than the nth member of B, who I will designate as An and Bn. If Bn originally raced against someone slower than An then the result follows. So assume that Bn originally raced against someone faster than An.

What we want to show is that there must be someone slower than An who originally raced against someone faster than Bn, which would give our result. The n-1 members of B who are faster than Bn can only race against n-2 members of A who are faster than An, since we are assuming that Bn raced against one of those who are faster than An. So by the pigeonhole principle, one of the members of B faster than Bn must have raced against An or one of those slower than An.

As a generalization of the idea behind this problem, consider a group of people arranged in rows and columns. The people in each column are asked to arrange themselves by height front to back. Then the people in the rows are asked to arrange themselves by height left to right. After this happens, everyone will still be lined up by height in the columns.

Here’s another “oldie but goodie” that challenges mathematical intuition:

At a random gathering of people, how large must the crowd be for there to be a better than 50% chance of at least two people having the same birthday?

Clearly you need at least 366 people to guarantee this occurrence (pigeonhole principle again) but the answer to the posed question is surprisingly low.

You’d need 367 people to guarantee it (don’t forget February 29th)!

But I’ll have a go at this one. I assume I should ignore the added complexity of leapyears?

@LostInParadise When you say that my proof was nice for those who can follow it, are you saying that it is unclear? It seemed clear to me, but of course I was the one who wrote it. So here is a clarification.

I am going to call the speed of the nth place member of team A A(N)and the same place of team B B(N).

If team A was to lose a race, then B(N) > A(N), for some number N.

Since all races were won in random pairing, A(N) had to be paired with some B(>N) so that he is paired with a slower racer.

By definition A(N) > A(>N), so B(N) > A(>N).

All A(>N)‘s must be paired with the B(>N)‘s, but this leaves no room for racer A(N) to be paired with anyone that is slower than B(N).

Assume people with a Feb 29 birthday celebrate it on Feb 28.

Okay…I think I’m going about this right.

I oriented myself by starting a small list. In a group of two people, there are two relevant possibilities: the two people could be born on two different days, or they could both be born on the same day. In the first, and obviously most likely, instance, it doesn’t matter what day the first person was born, he could be born any day of the year (365/365), and the second person could be born any day except the the first person’s birthday (364/365). In the second case, the second person has to be born on the first person’s birthday (1./365).

2 people: Chances of all different birthdays: (365/365)(364/365). Chances of two of the same birthday: (365/365)(1./365)

To illustrate the pattern to myself a bit better I went on to a second iteration, the case of three people present. They could have all different birthdays, or two people could share a birthday, or they could all have the same birthday. The first option follows my previous example: (365/365)(364/365)(363/365). The second option is more complex, but I think what I’m doing is right. Two people have the same birthday, but one has a different one. So the one person could be any day (365/365), the second has to be a different day (364/365), and the third has to be the same as one of those two days (2./365). Finally, if all three have the same birthday, it matches up with the first example as well: (365/365)(1./365)(1./365). The chance that any two people present is the sum of the last two situations.

3 people: Chances of all different birthdays: (365/365)(364/365)(363/365). Chances of two of the same birthday: (365/365)(364/365)(⅔65) + (365/365)(1./365)(1./365)

So I could calculated the chances that two people will have the same birthday, but it’d be a lot harder than calculating the chances of a group having all different birthdays, which I can see now is straightforward. It is (365!/(365-x)!)/365^x where x is the number of people we’re looking for. This can also be represented as a permutation: 365Px/365^x Since of course, when the chances are 50% that at least two people will share a birthday, the chances are also 50% that nobody will have the same birthday as it is the only other option, so I can get away with only paying attention to the side that is easier to calculate.

Honestly the best way to find x here that I can think of is a bit of guess and check. Wolfram alpha tells me that for x=23 we have a probability of about 49.27% but for x=22 we have a probability of about 52.43%. This is for the probability that it won’t happen, so to have chances over 50% that it will, we need 23 people. Quite a bit lower than I would have expected; it certainly went against my intuition!

Please jump in if you’ve spotted any errors.

23 people is the right answer. Discussion at Wikip.
This was the first program I ever wrote (in 1977) for a programmable calculator, HP-25, to solve this well-known problem.

My intuition tells me to leave this puzzle for the mathematicians here.

@PhiNotPi , I did not intend criticism of your first explanation. It is just that the problem has a certain level of difficulty. Having said that, I do prefer your second explanation.

One last test of intuition, the Coat Check problem. The people going to a fancy restaurant check their coats. Unfortunately, all the tags on the coats somehow get randomly shuffled. If the tags are randomly reassigned, what happens to the probability that nobody gets the right coat as the number of coats increase? If you are familiar with expected value, a much simpler problem is to determine the expected number of people getting the right coat. This gives something of a hint of what happens to the probability.