Hong Kong Preliminary Selection Contest

Question

If a sequence a_1, a_2, , a_n of positive integers (where n is a positive integer) has the property that the last digit of a_k is the same as the first digit of a_k+1 (here k = 1, 2, , n and we define a_n+1 = a_1), then the sequence is said to be a 'dragon sequence'. For example, 414, 208, 82 and 1, 17, 73, 321 are all 'dragon sequences'. At least how many two-digit numbers must be chosen at random to ensure that a 'dragon sequence' can be formed among some of the chosen numbers?

Accepted Answer

If we take any 46 two-digit numbers, then only 44 two-digit numbers are not chosen. Hence we either have one of the 36 pairs

{\overline{A B}, \overline{B A}}

where

1 \leq A < B \leq 9

, or one of the 9 numbers

11, 22, \dots, 99

. In either case, we get a 'dragon sequence' by definition.

Next, suppose we only pick those two-digit numbers whose units digit is smaller than whose tens digit. There are altogether 45 such numbers. If we get a 'dragon sequence' among these numbers, say

{\overline{A_{1} A_{2}}, \overline{A_{2} A_{3}}, \dots, \overline{A_{n} A_{1}}}

, then

A_{1} > A_{2} > \dots > A_{n} > A_{1}

, which is a contradiction. So these 45 numbers contain no 'dragon sequence'. It follows that the answer is 46.