9
$\begingroup$

A clock uses a seven-segment display as following:

seven-segment digits

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.

$\endgroup$

3 Answers 3

9
$\begingroup$

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.

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

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.

$\endgroup$
6
$\begingroup$

I constructed

14

With

Solution whoops missed a step between 4 and 9

I think it is optimal?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.