Dragon Sequence?

Probability Level 5

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 called a "dragon sequence." Some examples of a "dragon sequence" are $\{414\}, \{858\}, \{208, 82\}, \{157, 731\}, \{569, 931, 175\}, \{1, 17, 73, 321\}.$ 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?

The answer is 46.

1 solution

Alan Yan
Jun 5, 2018

Relevant wiki: Pigeonhole Principle

We can exclude the possibility of drawing $11, 22, ...$ since that will automatically give us a dragon sequence. Consider the family of sets $\{ \{ij, ji\} : 0 \leq i < j \leq 9 \}$ (We include numbers like $04$ even though there is no way we can choose these). There are $45$ such sets, so if we pick $46$ random numbers, we will have two numbers in the same set (furthermore, they will be $\{ij, ji\}$ such that $i, j \neq 0$ ). So, $46$ is enough. An example where $45$ is not enough is to pick all numbers $ab$ such that $9 \geq a > b \geq 0$ .

Hence, the answer is $\boxed{46}$ .

You have forgot the case if one choose 10,20,30,.....90, also. And this numbers are useless for making a dragon sequence.Answer should be 46+9=55. I found it but your answer made it wrong.

Alapan Das - 2 years, 2 months ago

Dragon Sequence?

The answer is 46.

1 solution

1 pending report

Vote up reports you agree with