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.
There are C(100,2)=4950 possible pairs, of which the dealer gets to choose 100.
At first glance it seems impossible even if the dealer gives all 4950 pairs. Cards 1 and 2 win in 1 match-up, cards 99 and 100 win in 98 match-up. For all cards n from 2 to 99, n wins in n-1 match-up.
Knowing the number of wins isn't enough, but looking at the two cards that won 1 match-up you can see which beat the other. That would be card 2 and the loser would be card 1. Similarly for the two cards with 98 wins.
Now to trim this down from giving all 4950 match-ups down to only 100.
|
|
Posted by Jer
on 2021-03-04 08:41:37 |
Some thoughts
