5
$\begingroup$

You are given a two-digit number. You can replace one of its digits with the sum of its digits modulo 10. For example, if the starting number is 58 then you can change it to 38 or 53. You can continue changing this number provided that you do not repeat a previously created number. This means if you went from 58 to 53 then you cannot go back to 58. Leading zeroes are not allowed.

What is the longest sequence of numbers you can create if you start with the number 10?

Hint:

Think about numbers that cannot be reached. Also think which numbers will get you stuck in a cycle quickly. These two things should give you a good upper bound on the maximum score.

$\endgroup$
3
  • 2
    $\begingroup$ Easy to code, rather tedious otherwise. $\endgroup$ Aug 29 at 5:17
  • 1
    $\begingroup$ Are leading zeroes allowed? $\endgroup$
    – Bass
    Aug 29 at 15:19
  • $\begingroup$ no leading zeroes allowed. $\endgroup$ Aug 29 at 22:10
4
$\begingroup$

Like Daniel in the comments, I also thought this would be easy to code. However, my brute force approach ran out of memory pretty quickly. I tried moving the history to a database, but that's very slow. Here's the best I've found so far:

67 moves [10, 11, 12, 13, 14, 15, 65, 61, 67, 63, 69, 59, 54, 94, 93, 23, 53, 58, 38, 18, 98, 97, 96, 95, 45, 49, 43, 47, 41, 51, 56, 16, 17, 87, 57, 52, 72, 92, 91, 90, 99, 89, 79, 76, 73, 70, 77, 74, 71, 78, 75, 25, 27, 29, 21, 31, 34, 37, 30, 33, 36, 39, 32, 35, 85, 83, 81]

A little more thought, and I realised that I could represent all the possible moves from one number to another as a directed graph. Then the problem becomes finding the longest path in the graph. Bad news: that problem is NP hard for a general graph. It's possible that there's some shortcut I could use for this graph, but I haven't found it yet.

$\endgroup$
9
  • $\begingroup$ You have found the optimal solution. This can be found very quickly with a DFS. However there is a solution that doesn't require a computer. Have a look at the numbers that are missing. $\endgroup$ Aug 30 at 1:04
  • 1
    $\begingroup$ C code: onlinegdb.com/-hu3j1ZDf $\endgroup$ Aug 30 at 3:55
  • $\begingroup$ Nice work @DanielMathias. I am trying to compute the optimal answer for the 3-digit version of this puzzle, but my DFS is taking a very long time. Perhaps you can help? $\endgroup$ Aug 30 at 4:40
  • $\begingroup$ @DonKirkby note that the longest path on a directed acyclic graph (DAG) can be found in linear time. en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs I think this problem can be reduced to a DAG if we cleverly cut some edges. $\endgroup$ Aug 30 at 23:27
  • 1
    $\begingroup$ For 3 digits, 664 is optimal. $\endgroup$
    – RobPratt
    Sep 1 at 2:10
7
+50
$\begingroup$

First, a map: (very minor spoiler)

enter image description here

Second, notice that

replacing a digit with the sum of the two preserves divisibility by 2 and 5, so the reachable numbers are precisely the ones that don't share either factor. (Hence the spoiler)
By inclusion-exclusion, we can confirm that there should be 72 stations (allowing leading zeroes, except this actually doesn't matter as I'll explain below): 10^2 pairs sharing no factors - 5^2 pairs sharing 2 - 2^2 pairs sharing 5 + 1 pair (00) sharing both.
Now, notice that not all 72 stations are reachable - the eight purple stations only lead to the four white ones because their other paths [omitted] lead to themselves. Therefore, only five can be visited (and the fifth only as the last stop). If leading zeros are prohibited, then this is irrelevant - each white station has exactly one purple input and the length is capped at 68 instead of 69.
The last step for a proof of the optimality of @Don Kirkby's answer is to show that all four blue stations cannot be passed* in a single trip - unfortunately, I don't have a justification for that right now.
*Don's route misses 19 - the one leading back to the start.

$\endgroup$
1
  • $\begingroup$ Oh wow that is amazing piece of work! $\endgroup$ Aug 30 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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