Exercise 8. A digital lock opens as soon as the correct unique combination of 4 digits (which may include repetitions) is entered. For example, if the sequence of digits 000125 is entered, the digital lock will open if the code is either 0001, 0012, or 0125. Little Pierre does not know the code. How many digits at a minimum must he enter to be sure to open the digital lock?
Solution. It is clear that at least 10003 digits are needed, because all 10000 combinations must be tried. Let's show that this number is also sufficient.

Draw 1000 points corresponding to all sequences of 3 digits. Draw an arrow between two points if the last two digits of the first combination match the first two digits of the second combination (and in the same order). For example, there will be an arrow from the point 200 to the point 009 and another from the point 201 to the point 017; between the points 303 and 030 there will be two arrows going in both directions; on the point 777 there will be a loop arrow that returns to its starting point. Thus, each arrow corresponds to a unique possible code.

It is easy to see that there are 10 incoming arrows and 10 outgoing arrows at each point. Indeed, to get an outgoing arrow, for example, one must choose a digit from 0 to 9 to add to the last two digits of the point's number, which gives exactly 10 choices.

It is also easy to see that the graph formed by the points and arrows is connected. Indeed, one can go from a point $abc$ to the point def in three arrows $abc \rightarrow bcd \rightarrow cde \rightarrow$ def.

The well-known Euler's theorem (see, for example, "Eulerian Graph" on Wikipedia) then ensures that all the arrows of the graph can be traversed without passing through the same arrow twice. This traversal will give the desired sequence of 10003 digits: the 3 digits of the starting point must be entered, and then just the last digit of each point in the traversal. The fact that each arrow of the graph is passed exactly once means exactly that each possible 4-digit code will be tried exactly once.