9
$\begingroup$

Alice and Bob have each a number (not greater than 30) of cards numbered sequentially 1 onwards. Alice can easily reorder her cards and place them on a table one after the other so that no two cards which lie next to each other have a digit in common. On the other hand Bob, who has just one card more than Alice, has no way of placing his cards on a table likewise (no two cards lying next to each other with a shared digit), however he tries.

How many numbered cards does Alice have?

$\endgroup$
8
$\begingroup$

I think that Alice must have

$17$ cards

Reasoning

In the first $18$ cards, that Bob will have, $10$ of those will contain the digit '$1$'. For any ordering, if we divide the cards into $9$ consecutive pairs, by the Pigeonhole Principle, there will be at least one pair which contain two cards showing the digit '$1$'. Hence, Bob will never be able to find a configuration that works.

On the other hand, Alice just needs to ensure all cards containing the digit '$1$' appear in the odd numbered positions and ensure no two cards which differ by $10$ are next to each other. For example, she could order them as follows, $$ 1, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15, 8, 16, 9, 17$$

$\endgroup$
  • 1
    $\begingroup$ In the range given, the answer is unique and it is fairly straight forward to check so. The next possible number of cards Alice could have is 162, as confirmed by Freddy Barrera. $\endgroup$ – Bernardo Recamán Santos Oct 28 '18 at 13:25
  • $\begingroup$ Had it been Alice with one more card than Bob, and again, she able to place the cards as required but Bob unable to do so, then the number of Alice's cards would be 23. $\endgroup$ – Bernardo Recamán Santos Nov 27 '18 at 1:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.