Win the Contest
This problem is from Grant Fikes.
Every year at the annual Winter Wizard World conference, there is a contest for student teams from each of the wizard training schools. This year each team has five student members, and each member of each team has been given a fair coin (that cannot be hexed to become unfair.) The team members are to play a pairwise matching game with their own team members (not with team members from other schools.) When it is a pair’s turn to play the matching game, one of the players tosses a coin, letting it fall on a smooth marble floor. While the coin is in the air, the other player calls “heads” or “tails.” If the player who calls gets the correct outcome, then that player wins, otherwise the other player wins. Now for the real contest. Exactly one of the members of each team has been placed under a spell so that this player will alternate in winning and losing each time the hexed player plays a match. That is, if the hexed player wins his first match, he will lose his next match, and then win his third match, and so on. No one knows the identity of the hexed player.
The contest will be won by the first team that correctly identifies its hexed player. Any team that gives an incorrect answer is disqualified and cannot win the contest. Find a strategy for identifying the hexed team member.
For the fun of it, can you identify all integer team sizes for which a strategy exists for finding the hexed member? Of course, a team must have at least two members.
Please submit all work for this problem to mathpotw@acu.edu. All submissions are due by 5:00 PM on Thursday. (In this case, Thursday, January 30th.)
Solution to Win the Contest
Correct solutions were submitted by: Wyatt Witemyer.
Let’s denote the team members by A[ ], B[ ], C[ ], D[ ], and E[ ]. When a match is over, we will fill in the space with a W if the player won, and an L if the player lost. So now match A with B and C with D. Without loss of generality, we can label the results as A[W], B[L], C[W], and D[L]. Now pair A[W] with C[W] and B[L] with D[L]. Whoever wins between A and C is not hexed, and whoever loses between B and D is not hexed. Without loss of generality, suppose our hexed team member is in the list {A[L], C[W], E[ ]}. Now pair A[L] with E[ ].
If A loses, then A is not hexed and we have C[W] and E[W] remaining. The loser of a match between these two is the hexed team member.
If A wins, then we are in the condition {A[W], C[W], E[L]}. We now play a match between A and C. The winner is not hexed, and we are left with two players who have lost their last match. A match between these two will prove that the winner is the hexed team member.
The hexed player can be found in at most 7 matches.
The kind of argument used above will apply to any team that has an odd number of members. But what about teams with an even number of members? If there are only two members then, by chance, they could alternate winning and losing. So in that case, there is a chance that the hexed player could not be found for quite a long time. But what if there are four team members A, B, C, and D? As before, pair A with B, and C with D. Without loss of generality let the results be A[W], B[L], C[W], and D[L]. Now pair A[W] with C[W] and B[L] with D[L]. Whoever wins between A and C is not hexed, and whoever loses between B and D is not hexed. Without loss of generality, suppose hexed team member is in the list {A[L], C[W]}. Match A[L] with the player D[L] (known to NOT be hexed). If A loses, then A is not hexed. Otherwise, now match A[W] with C[W] and the hexed member is found.
The same kind of argument works for any team with an even number of members larger than 2.
