Name That Card
Zane is creating a trick in which a spectator will choose one of N cards at random (without showing Zane which one it is). Zane’s goal is to identify that card. After blindfolding the spectator, he will hold up a group of some of the cards, showing them to the audience, and make a statement about the group of cards that the audience will see is true. Zane will then ask the spectator whether her card is in that group (based only on the statement he made). Zane will then repeat this process with a different group of cards. Assume that the spectator answers truthfully both times.
What is the largest value of N such that Zane can be certain to be able to identify the card the spectator chose after both questions have been answered?
For a different trick, Tyne wants a dramatic way to indicate one card out of the deck; the card could be in any position in the deck. She decides there should be some number of posters on the wall in the background of the performance, and at the time of the big reveal, she will point to one, two or three of the posters in sequence, possibly repeating a poster (or even pointing to the same poster three times). The spectator involved in the trick will then be told to look on the backs of the posters and add up the numbers found there (again, using the same number more than once in the sum if Tyne repeated a poster). The spectator will then look at the card in the position in the deck designated by that sum.
What is the fewest posters Tyne needs, and what numbers should be on their backs, so that she can direct the spectator to any position in the deck from 1 to 52 by appropriately choosing which posters to point to?
|Spread the word:||Tweet|
Solutions to week 98
Upsetting Tournament. Note that an undefeated player or a player who lost all games cannot be involved in an upset. Similarly, a player with only one defeat and a player with only one win can be involved in at most one upset each. Even more, if there are multiple players with only one defeat, they can still only be involved in a single upset among them: one of them may have been defeated by a player with a worse record, but then that one must have beaten all the other players, including all of the others with just one loss, which accounts for their one loss each and means that none of those other players were involved in any upsets. The exact same reasoning shows that all of the players with just one win can only be involved in a single upset among them.
Now we can reason similarly about the players with just two losses. Suppose that one of them beat two players with worse records; then that player beat all the others with two losses, accounting for one of their losses each, so there could be at most one more upset among the players with two losses. On the other hand, if three of them beat one player each with worse records, then two out of the three would have to have beat each of the other players with two losses, accounting for both of those other players’ losses. So in any case, there can be at most three upsets that players with just two losses were involved in. As before, we can also conclude that there can be at most three upsets that players with just two wins were involved in.
But in fact, we can conclude a little more. Counting all of the players with just one or two losses, there can only be three upsets those players are involved in. If there is a player with only one loss, that accounts for one of the losses of all (except perhaps one) of the players with two losses, none of which are upsets, so it reduces the number of upsets the players with two losses are involved in. So the total can never exceed three. Again, there can also be at most three upsets that involve players with just two or one win.
Now look what happens if there are only seven players in the tournament. Besides the players with 0, 1, or 2 losses, and the players with 0, 1, or 2 wins, there are only the players whose records in the round-robin were 3-3. Since no game between two players with 3-3 records can be an upset, every upset either involves a player with 1 or 2 losses, or a player with 1 or 2 wins. Hence, there can be at most six upsets. So there cannot be more upsets than players.
On the other hand, it is not difficult to come up with a possible outcome for an eight-player tournament that includes nine upsets (there are many such possibilities), so a round-robin must have at least eight players to include more upsets than players.
Calm Playoff. Since there are no upsets, the players with the best records must only have lost to each other. Thus, just considering the games among that group, each must have lost at least twice. But since each of those losses is to some other player in the group, each must also have won at least twice in games with other members of the group. Hence, each of the top group of players must have played at least four games with other members of that group. So there must be at least five players with the best record to go on to the playoffs. (You can easily check that there is an outcome, in which the players beat each other in a sort of five-pointed-star pattern, in which each of the top five players goes 2-2 against the other four.)
Links to all of the puzzles and solutions are on the Complete Varsity Math page.
Come back next week for answers and more puzzles.