Nils has a telephone number with eight different digits. He has made 28 cards with statements of the type “The digit a occurs earlier than the digit b in my telephone number” – one for each pair of digits appearing in his number. How many cards can Nils show you without revealing his number
The question doesn't specify if the cards to show are chosen arbitrarily or chosen at random. Therefore, the question be understood two ways:
- How many cards can Nils show you without revealing his number, provided that he can chose which cards he shows first?
The answer to this question is the one given by JonMark Perry:
27 cards (that is, Nils can show all cards except one card relating two consecutive digits).
- How many randomly chosen cards can Nils show and still be sure of not having revealed his number?
6 cards. There are 7 cards relating consecutive digits and the telephone number is not revealed as long as Nils keeps one of them hidden.
Both answers are justified the same way (I'm going to assume that we know that the telephone number has 8 digits):
To fully determine the whole telephone number we need the cards relating any two consecutive digits. Let's assume the telephone number is 12345678.
If we know all cards except for the one relating 1 an 2, we just know that 1 and 2 came before all other digits, but we don't know if 1 comes before 2 or 2 comes before 1. The same would be true for any other pair of digits. Therefore we need at least all the cards relating consecutive digits and 27 cards won't be enough if one of such cards lacks.
If we know the 7 cards relating all consecutive digits, we can order the 8 different digits, and since we know there are only 8 digits, those 8 ordered digits are the whole phone number.
The first question seems to fit better the statement, but the second one might fit better its title - although there is no probability involved in the answer, at least there is a random event.
The answer is:
27. Assume the telephone number is 12345678. The cards read '1 appears before 8', '2 appears before 8', ..., '7 appears before 8'. Now all we know is that 8 is last.. Repeat for the penultimate digit, etc. The 28th card is '1 appears before 2', and this reveals the answer.