1

Could you please check my solution for this problem from the Colorado Mathematics Olympiad. I'm new to mathematics problems and I'd like to know if it has any flaw or if it could be improved.

"Twenty-three people of positive integral weight decide to play football. They select one person as ref- eree and then split up into two 11-person teams of equal total weight. It turns out that no matter who is the referee this can always be done. Prove that all 23 people have equal weight."

My solution: Pick any person, call it R who will be acting referee and have weight equal to X. Split the rest 22 into groups A and B of equal weight (by hypothesis) and keep these teams fixed throughout the solution. Now exchange R with a member of group A, say A(1). The newly formed group A still has weight equal to group B which means that A(1) and R must have the same weight, because if otherwise say A(1) was heavier than R then group A must have been lighter than B or if A(1) was lighter then group A would have been heavier, so the weight of A(1) is equal to the weight of R namely X. But in the same way we could choose any member of group A, so every member of group A has weight equal to X. Now we repeat this procedure with R as referee and exchanging with members of group B and obtain that every member of group B also have weight equal to X. So all 23 persons have the same weight.

Thank you in advance for the response(s).

Csiki Szabi
  • 11
  • 2
  • 1
    That is not correct. The question only gives you after exchanging some players between A(1) and B you can form equal weights A(2) and B(2), not that A(1) and B automatically have equal weights. – user10354138 Oct 12 '23 at 10:30
  • Oh I see now. Basically my fixing of the teams is not allowed. Thanks for pointing it out! – Csiki Szabi Oct 12 '23 at 11:18
  • 1
    As @user10354138 said above, this is too simple. The problem description says 'that can be done', which only means that for any choice of $R$ there exists some partition of the remaining set into two equinumerous and equal weight teams. It does not imply, however, any of those partitions must retain one of the resulting teams. – CiaPan Oct 12 '23 at 11:22

1 Answers1

1

Others already explained the problem in your logic. Let me discuss a few possible strategies to attack a problem like this. Do keep in mind that well designed contest problems are often elusive, and an initially promising looking line of attack need not work. In that case and you need to think of a different one.

One thing that immediately calls for extra attention is that strange number of exactly 23 people. We know that it is the number of players on a football field plus the ref, but a common strategy in solving contest problems is to try a simpler case first. Such a strange number may be a red herring, and/or we may anyway learn something essential by looking at a smaller number instead. What if we had only three people at the party, and the goal is the same. Appoint a ref, and assume that the remaining two can be partitioned into two equal weight teams. This is clearly impossible unless all three weigh the same amount. For if two persons have distinct weights, and we assigned the third person to be the ref, there's nothing we can do.

But in the question there were 23 people. Unless a special property of the number 23 is the key to the problem, we could generalize and try to prove that no matter how many people there are (as long as their number is odd), the only occasion when the partitioning into equal weight teams succeeds as prescribed is when they all have the same weight. 3 people was easy, so 5 people is the next case. Hmm. Next case? Induction with 3 people as the base case? I leave it to you to ponder. Just in case it doesn't lead anywhere let's think of something else.

Another thing that caught my eye in the problem description is the emphasis that the weights are integers. Then the total weights of the teams are also integers, and the total weight of the 22 people playing in two equal weight teams must be an even number of lbs. Is it possible to select the ref in such a way that the total weight of the remaining 22 people is odd? If so, then we are in business! Say, if there is an odd number of people with odd weight, and at least one person with an even weight, we run into exactly this problem by selecting a ref with an even weight. But what if there are an even number of people with odd weight? Then we can have all of them eat a big Colorado burger to gain one pound, and that will correct things (do you see why?). The only occasion when a trip to a burger stand won't rectify things is that of all 23 people having weights of the same parity (justify that also). If initially they all have odd weights, then after the burger party they all have an even weight and things didn't improve :-(

So may be this line won't lead us anywhere either? May be there is a way to apply induction here? May be this does not work, and the other approach does lead to an induction? May be neither works, and we need a third approach.

The point of this answer was to describe a thought process necessitated by a problem where no line of attack is apparent. And also to underline the need to flexibly give up on a line that doesn't lead anywhere, as well as try to figure out hidden clues (both the potential approaches above somehow use parity).

Good luck! Train your brain by working on many such problems.

If you continue with the second line of attack, in the inductive step you may want to reduce it to the case, if necessary with the help of the burger stand, where all the weights are even. And then divide all the weights by two to get to a situation where a suitable induction hypothesis kicks in. For full credit you need to justify why all this can be done without loss of generality.

Jyrki Lahtonen
  • 133,153
  • I did check that induction of some kind does work in at least one of the approaches above. It is your job to figure out which approach, and exactly how the induction does work. – Jyrki Lahtonen Oct 13 '23 at 17:15
  • Or, to think of yet another approach :-) – Jyrki Lahtonen Oct 13 '23 at 17:21
  • Wow thank you very much for your wonderful answer, it was a delight to read! I will definitely try the suggested ideas. Also, as a matter of fact first I thinked about the simpler case of just 3 person and that's what got me on the bad track because I got overly excited with the idea of just exchanging and didn't think it through sufficiently. Again thank your for the ideas, they are greatly appreciated! – Csiki Szabi Oct 14 '23 at 18:43