A 9-digit number

We may first list all the possible 2-digit sequence, with cancellation of numbers containing '0' or repeated digits (repeated numbers are cancelled as well):

$12, 18, 24, \cancel{30}, 36, 42, 48, 54, \cancel{60}, \cancel{66}, 72, 78, 84, \cancel{90}, 96$

$\cancel{12}, 21, 28$ , $\fbox{35}$ , $\cancel{42}$ , $\fbox{49}$ , 56, $\fbox{63}$ , $\cancel{70}, \cancel{77}, \cancel{84}, 91, 98.$

From the list, we know that

(i) '7' must be the first digit,

(ii) the sequence $35, 49, 63$ must be selected;

(iii) from (ii), $\fbox{635}$ form a 'block' of the 9-digit number.

If '5' is not the last digit, by (iii), the block $\fbox{635}$ will be extended to $\fbox{6354}$ (as we cant choose 56). This follows by the block $\fbox{63549}$ . Since by (i), 6 is not the first digit of the number, there must be a digit in front of digit 6. Note that there are only three such possibilities, namely 3, 5 and 9. However we can't use any of these because of the block $\fbox{63549}$ . Hence '5' must be the last digit.

Using the previous argument, the block $\fbox{635}$ will be extended to $\fbox{49635}$ . Now we left with the digits 1, 2, 7 and 8. The previous list is now become

$12, 18, 24, \cancel{30}, \cancel{36}, \cancel{42}, \cancel{48}, \cancel{54}, \cancel{60}, \cancel{66}, 72, 78, 84, \cancel{90}$ , $\fbox{96}$

$\cancel{12}, 21, 28$ , $\fbox{35}$ , $\cancel{42}$ , $\fbox{49}$ , $\cancel{56}$ , $\fbox{63}$ , $\cancel{70}, \cancel{77}, \cancel{84}, \cancel{91}, \cancel{98}.$

By (i), the number is either $72**\fbox{49635}$ or $78**\fbox{49635}$ . It is clear that $78**\fbox{49635}$ is impossible, as there is no connection between the digits 8 and 4. So the only possibility is $\fbox{721849635}$ .

We start by creating a directed graph where numbers are the vertices, and a directed edge means we can concatenate the 2 numbers. The goal is to find an eulerian path that goes through all of these vertices.

This is what the graph looks like. The bolded edges indicate that we can travel both ways.

• Vertex 7 has an in-degree of 0. Hence, it must start the sequence. Henceforth, if a vertex has an in-degree of 1, then that edge must exist.
• Vertex 5 has an in-degree of 1. Hence, we must have edge 35.
• Vertex 3 has an in-degree of 1. Hence we must have edge 63. Now, edge 56 is useless, so let's delete it.
• Vertex 6 has an in-degree of 1. Hence we must have edge 96. Now, edge 91 is useless, so let's delete it
• Vertex 9 has an in-degree of 1. Hence we must have edge 49. Now, edge 54, 42 is useless, so let's delete it.
• Vertex 5 has an out-degree of 0. This tells us that it's the last digit. Henceforth, if a vertex has an out-degree of 1, then that edge must exist.

This is what the graph looks like now, with the vertices shifted and edges deleted. The blue edges indicate the ones that we must have.

Let's continue (Use the above graph to visualize what happens):

• Vertex 8 has an out-degree of 1. Hence we must have edge 84. Now, edge 14, 48, 42 is useless, so let's delete it.
• Vertex 1 has an in-degree of 1. Hence we must have edge 21. Now, edge 28 is useless, so let's delete it.
• Vertex 2 has an in-degree of 1. Hence we must have edge 72. Now, edge 78 is useless, so let's delete it.
• Vertex 1 has an out-degree of 1. Hence we must have edge 18.

Thus, the number is 721849635.