In a card game, each card is associated with a numerical value from 1 to 100, with each card beating less, with one exception: 1 beats 100. The player knows that 100 cards with different values lie in front of him. The dealer who knows the order of these cards can tell the player which card beats the other for any pair of cards he draws. Prove that the dealer can make one hundred such messages, so that after that the player can accurately determine the value of each card.
So we need some way of designating the cards other than the numbers on them. What I'll use are capital letters at the beginning of a trail the dealer will create (not necessarily in order so long as the player can keep track of the commonality between pairs), and lower case at the end. These don't imply they are the 1 end and the 100 end. We need 100, but have only 52; some other designations fill in the middle.
A>B, B>C, C>D, ... u>v, v>w, w>x, x>y, y>z
Only 99 pairs have been demonstrated, but due to the circular nature of the values (though not transitive) we know that z>A, so we have another pair to spare.
Now that one pair doesn't seem enough. Suppose the dealer demonstrates that x>v. Either x is the 100 and w is the 1, or w is the 100 and v is the 1. How can we know which?
Could it be accomplished by leaving out another pair besides z and A? If he left out D and E as well? Then we'd have two strings: E through z and A through D. It doesn't matter which comes first as it's a circular arrangement. It frees up another revelatory pair. If the dealer shows both x>v and w>u we now know that w is the 100, x is the 99, u is the 2 and v is the 1.
It wouldn't work with only 99 showings allowed, as leaving out another pair to free up the two double-place showings would break the circle into three parts and we wouldn't know the order in which they're placed.
|
|
Posted by Charlie
on 2021-03-04 17:21:15 |
solution
