Reducing $\pi$ to zero

Question

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

Answer 1

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

Answer 2

@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.

Answer 3

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.

Answer 4

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$.

Answer 5

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