11
$\begingroup$

This is based on a discussion with @mousetail.

List the numbers from 1-100 in Roman numerals in the order that minimizes the total sum of the Levenshtein distances between consecutive numbers.

$\endgroup$

1 Answer 1

15
$\begingroup$

The minimum possible total is:

99

This is because

all pairs of numbers have a distance of at least 1

This minimum is achievable using the following pattern to get from

I to V:
I, IV, IX, II, III, VIII, VII, VI, V
which can be reversed to allow for a change of tens numerals at the end of the sequence

The full list looks like (reading left to right, top to bottom)

table

$\endgroup$
3
  • 3
    $\begingroup$ Nice. With a slight change you can make it cyclic. Rot13( Zbir P orgjrra KP naq K. Gura erirefr gur vavgvny V gb I fho-frdhrapr gb pybfr gur qvfgnapr sebz gur svany YI gb gur fgneg.) $\endgroup$
    – fljx
    Jan 26 at 11:55
  • $\begingroup$ An excellent answer $\endgroup$
    – Simd
    Jan 26 at 12:47
  • 2
    $\begingroup$ I wonder if this could be extended to bigger ranges $\endgroup$
    – mousetail
    Jan 26 at 12:50

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.