6
$\begingroup$

You are given the first 20 digits of $\pi$: 31415926535897932384. In each move, you can select a contiguous group of digits and increase/decrease them all by the same integer, provided that each resulting digit stays between 0 and 9 inclusive. For example you can increase the first 5 digits by 2, giving you 53637926535897932384. However you cannot decrease the same 5 digits by 2 as that would result in negative digits. Can you bring every digit to 0 in 12 moves? You may need to use a computer. Good luck!

Here is a simpler version of this puzzle: Contiguous shifts in a 10-digit number

$\endgroup$
3
  • $\begingroup$ Do the digits wrap? Eg if I increase 9 by 1 do I get 0, or can I not increase 9 by 1? $\endgroup$
    – Vicky
    Apr 11 at 10:00
  • 1
    $\begingroup$ They don't wrap and you cannot increase 9 by 1. You also cannot decrease 0. $\endgroup$ Apr 11 at 10:29
  • $\begingroup$ I figured the "least moves" version of the puzzle was too hard, so I have specified 12 moves. $\endgroup$ Apr 11 at 11:20
7
$\begingroup$

I found several by hand with 13 steps, then wrote a program... which found hundreds more solutions with 13 steps, and I was beginning to think that maybe there was no solution for 12 and then my program spat-out this:

1 31415926535886822384
2 31415926533666822384
3 31415926644777933384
4 31411526644777933384
5 31411526666999933384
6 31411526666999999984
7 31444859999999999984
8 31111526666666666684
9 33333748888888888884
10 00000448888888888884
11 00000004444444444444
12 00000000000000000000

Edit1: Another solution found by the silly program:

1 [0, 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 8, 6, 8, 2, 2, 3, 8, 4, 0]
2 [0, 3, 1, 4, 1, 1, 5, 2, 6, 5, 3, 5, 8, 8, 6, 8, 2, 2, 3, 8, 4, 0]
3 [0, 3, 1, 4, 1, 1, 5, 2, 6, 5, 3, 3, 6, 6, 6, 8, 2, 2, 3, 8, 4, 0]
4 [0, 3, 1, 4, 1, 1, 5, 2, 6, 5, 5, 5, 8, 8, 8, 8, 2, 2, 3, 8, 4, 0]
5 [0, 3, 1, 4, 1, 1, 5, 2, 6, 5, 5, 5, 8, 8, 8, 8, 8, 8, 9, 8, 4, 0]
6 [0, 3, 1, 4, 4, 4, 8, 5, 9, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 8, 4, 0]
7 [0, 3, 1, 1, 1, 1, 5, 5, 9, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 8, 4, 0]
8 [0, 3, 1, 1, 1, 1, 1, 1, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 4, 0, 0]
9 [0, 3, 1, 1, 1, 1, 1, 1, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 0, 0]
10 [0, 3, 3, 3, 3, 3, 3, 3, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 4, 0, 0]
11 [0, 0, 0, 0, 0, 0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 0, 0]
12 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Edit2: I have my code available. It is written in Java. I tested it against the earlier puzzle (the 10-digit puzzle that was solvable with 4 steps). So you can set the initial string of digits and the number of steps you allow in a solution (at the top of the file) and watch it go if you can manage to run it. Here it is: https://github.com/nastos/StackExchangePuzzles/blob/main/PiDigitPuzzle.java

$\endgroup$
3
  • 1
    $\begingroup$ Nicely done! I was worried that the puzzle is too hard. The solution is different to the ones I have found. I am still not sure if this is optimal. Would you be able to briefly describe how your program works and perhaps share the code? This would be very interesting. $\endgroup$ Apr 11 at 13:25
  • $\begingroup$ The code is stupid. It would be embarrassing to share :P It picks a random pair of positions and checks if it is valid to apply an operation on the contiguous range between them. If not, it randomly picks two positions again and repeats, until 12 moves are made. And then it starts over and repeats. It took millions of iterations to eventually find one solution with 12 steps. I just got another solution after 2.2million attempts again (added into answer) $\endgroup$
    – JimN
    Apr 11 at 13:34
  • $\begingroup$ Thank you for the code. I am somewhat surprised that such a "simple" method works. $\endgroup$ Apr 12 at 0:40
8
$\begingroup$

@JimN has shown it is doable in 12. What remains to be done is

Proof of optimality:

Pad with two auxiliary zeros 0314159265358979323840 and form all differences between adjacent digits. This yields 21 differences:
2 x 1, 2 x -1
2 x 2, 3 x -2
3 x 3, 1 x -3
4 x 3, 2 x -4
1 x 5, 1 x -6, 1 x -7

In the end these differences must all be zero. We can remove two per move but a necessary condition for that is that a pair d,-d of complementary differences exist. We can count and find 7 unbalanced differences in the beginning. Each move removes two differences for good or replaces one or two of them with a new difference. A move can therefore at best
* remove two differences or
* remove four imbalances or
* remove one difference and three imbalances
If we had only 11 moves, to remove 21 differences we would have to 10 x remove 2 differences and 1 x remove 1 difference and 3 imbalances, leaving 4 imbalances unresolved (which, incidentally, is impossible). 12 is therefore optimal.

$\endgroup$
2
$\begingroup$

Here's a "manual" solution.

Let's start by noticing that there are 21 changes between consecutive digits (there are implicit zeroes to the left and the right), and an operation can eliminate at most 2 of them, one at either end of the changed digit string. This means that 11 moves is an absolute lower bound.

So, let's start by finding all the optimal moves, that is, moves that remove two differences at once. There are four such single-digit changes, and three longer ones. (As far as I can see. I calculated all the differences between consecutive digits and looked for a positive and negative jump of the same size, and checked that there are no troublesome digits that would go out of range in between them. Please drop a note if I missed any.)

31415926535897932384
  ^      ^   ^  ^
        5358 (+1)
            9793 (-1)
          589 (-2)

This means that we won't be reaching 11 moves: the differences in the first half won't be resolvable, because out of the 11 moves 10 would need be optimal, and one suboptimal move cannot be enough to resolve the left side. But let's see if three suboptimal moves might be sufficient, that would still allow for a 12-move solution.

Let's start greedily by taking all the four single-digit optimal changes, and then look for any suboptimal moves that create new optimal moves:

31115926555899933384
            999 (-6)
            333333 (+5) (optimal)
        6555 (+3)
      2 (+7) (optimal)
31115999888888888884   

This looks extremely promising: the jump from 5 to 9 matches the jump from 8 to 4.

31115999888888888884   
     99988888888888 (-4)
    5555444444444444 (-4) (oh, wow!)
 1111111 (-1) (the third suboptimal move)
3 (-3)

and we are done!

So the best possible solution is 12 moves.

$\endgroup$
1
  • $\begingroup$ I am impressed that you found this by hand! $\endgroup$ Apr 12 at 0:41
1
$\begingroup$

You can solve the problem via integer linear programming as follows. Let the steps be $S=\{0,\dots,12\}$, let the positions be $P=\{1,\dots,20\}$, and let the digits be $D=\{0,\dots,9\}$. For $p\in P$, let $d_p\in D$ be the digit in position $p$ (that is, $d_1=3,\dots,d_{20}=4$). Let the changes be $C=\{-9,\dots,9\}$. Let the moves be $M=\{i \in P, j \in P: i \le j\} \times C$.

Define integer decision variable $x_{s,p}\in D$ and binary decision variable $y_{s,i,j,c}$. The problem is to minimize $\sum_{p\in P} x_{12,p}$ subject to \begin{align} x_{0,p} &= d_p &&\text{for $p \in P$} \tag1 \\ \sum_{(i,j,c) \in M} y_{s,i,j,c} &= 1 &&\text{for $s \in S \setminus \{0\}$} \tag2 \\ x_{s,p} &= x_{s-1,p} + \sum_{\substack{(i,j,c) \in M:\\ p\in \{i,\dots,j\}}} c y_{s,i,j,c} &&\text{for $s \in S \setminus \{0\}$ and $p\in P$} \tag3\\ \end{align} Constraint $(1)$ fixes the initial values. Constraint $(2)$ selects exactly one move in each step. Constraint $(3)$ implements the selected move in each step.

The original problem is feasible if and only if the optimal objective value is $0$.

$\endgroup$
2
  • $\begingroup$ "The original problem is feasible if and only if the optimal objective value is 0." => I do not understand this and how you deduced it (I'm not familiar with linear programming, though). However, if instead of 0, the original problem was to bring every digit to 4 in 12 moves, then the solutions given by JimN show this is also feasible. $\endgroup$
    – xhienne
    Apr 11 at 19:50
  • $\begingroup$ The objective function is $0$ if and only if $x_{12,p}=0$ for all $p$, that is, if and only if the state after 12 moves is all zero. If the target state were instead all fours, the formulation would need a different objective function. Alternatively, you could omit the objective function and just fix $x_{12,p}=4$ for all $p$. $\endgroup$
    – RobPratt
    Apr 11 at 20:16
0
$\begingroup$

I found some more optimal solutions:

Bold indicates the group of numbers being changed

0. 31415926535897932384
1. 31415926535231332384
2. 31415926535564665684
3. 31411526535564665684
4. 31411526533344665684
5. 31411526644455776684
6. 31411526666677998884
7. 31411522222233554444
8. 33633744444455554444
9. 33633744444444444444
10. 33300444444444444444
11. 33300000000000000000
12. 00000000000000000000

0. 31415926535897932384
1. 31411526535897932384
2. 31411526535567932384
3. 31411526535556822384
4. 31411526557778822384
5. 31411526557778877884
6. 33633748777778877884
7. 33633304333334433440
8. 00333304333334433440
9. 00333304444444433440
10. 00333304444444444440
11. 00000004444444444440
12. 00000000000000000000

0. 31415926535897932384
1. 31415926524786821284
2. 31415926524786887884
3. 31415926635897998884
4. 31415959968897998884
5. 31415515524453554440
6. 31415515524442444440
7. 31415515522222444440
8. 33637737744444444440
9. 00337737744444444440
10. 00337733300000000000
11. 00333333300000000000
12. 00000000000000000000

$\endgroup$
2
  • $\begingroup$ Nice. There is a bold 5 in the first line of the first solution that seems to be confusing me $\endgroup$
    – JimN
    Apr 12 at 3:25
  • 1
    $\begingroup$ oops that shouldn't be bold $\endgroup$ Apr 12 at 3:47

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.