# Visiting every digit

A clock uses a seven-segment display as following:

Each move involves adding or removing a single segment. Starting with the digit 0, what is the fewest number of moves needed to visit all the remaining 9 digits? No computers please.

The permutation

0 8 6 5 9 * 4 * 1 7 * 3 * 2

requires a total of

13 steps

This is a slight alteration (a partial reversal) of Culver Kwan's excellent find:

0 8 * 2 * 3 * 7 1 * 4 * 9 5 6, which requires 14 steps.

• I confirmed optimality via LP. Commented Jun 24 at 3:24
• What happens when we can choose the starting digit? Commented Jun 24 at 7:19
• Well done, that's correct! Commented Jun 24 at 7:19
• Still optimal if $0$ is not required to be the starting digit. Commented Jun 24 at 12:23

Proof that Daniel Mathias' solution is optimal:

Look at the digits 1, 4 and 7. The only way we can get from one of these digits to anything else in a single step is 1 to 7 (or vice versa). So there must be an extra configuration (i.e. something that isn't a digit) immediately before 4, and before the earlier of 1 and 7. If the last digit is not one of these, there must also be an extra configuration after the latest of 1, 4, 7. These extra configurations all occur at different times.

Now look at 2. It's not one step away from anything, but it's also not two away from any of 1, 4, 7. So there must be an extra configuration before 2, and also after 2 if the last digit is not 2, and these extra configurations must be different to the ones we previously counted.

Since either there are three extra in the first group or two in the second, there are at least four in total.

I constructed

14

With

whoops missed a step between 4 and 9

I think it is optimal?

• You are missing a step between 4 and 9. Commented Jun 24 at 0:55
• @DanielMathias i sillied whoops Commented Jun 24 at 6:19