# Solving a Puzzle by Proving it Solvable

A colleague (designer *par excellence* Paul Theobald) introduced me to a
fun mathematical puzzle today.

In this blog post, I’ll show a proof that the puzzle is solvable for all \(n > 0\), and how that proof translates into a simple recursive algorithm to print the solution.

# The Puzzle

Given an integer \(n\), construct an expression which sums to \(n\), subject to these conditions:

- Use only the operations add, subtract, multiply, divide, and negate.
- Use each integer \(i \in {1..n}\) exactly once
- Use each integer in order from left to right

For example, here is a valid solution for \(n = 4\):

\[((1 + 2) - 3) + 4\]

But the below solution is *not* valid, because the integers \(1..n\) are not in
the correct order:

\[((4 + 1) - 3) + 2\]

Solving these is not too hard but not immediately obvious. Here are solutions for \(n < 5\):

\(n\) | Expression |
---|---|

\(1\) | \(1\) |

\(2\) | \(1 \cdot 2\) |

\(3\) | \([(-1) + 2] \cdot 3\) |

\(4\) | \(((1 + 2) - 3) + 4\) |

# Proving for all \(n\)

To prove the puzzle is possible for all \(n\), I’ll use a proof by induction.

We’ve already proved base cases for \(n < 5\), so all that remains is to prove the inductive step. Normally, this means proving that, when there is a solution for \(n\), there must also be one for \(n+1\).

In this case however, I’ll prove that if a solution exists for \(n\), it must also exist for \(n+2\).

That means we’ll need an extra base case for \(n = 2\)^{1}, but that’s OK
because we already have it!

# Proof of Inductive Step

Our goal is to prove that, if a valid solution exists for \(n\), then one must also exist for \(n+2\).

Let’s use \(e_n\) to refer to the valid solution for \(n\). For example, if \(n = 2\), then \(e_n = 1 \cdot 2\).

Note that \(e_n\) refers to a *mathematical expression* - a string of symbols -
rather than *the number it evaluates to*.

Now, to form a valid expression evaluating to \(n+2\), we must use the expression
\(e_n\) and the numbers \(n+1\) and \(n+2\) *in order*.
Because \(e_n\) uses all values \({1..n}\) in order, our new expression will also
be valid.

Now we simply recognise this fact:

\[(-n) + (n+1) = 1\]

And therefore

\[[ (-n) + (n+1) ] * (n+2) = n+2\]

So finally, to form a valid expression \(e_{n+2}\), we simply replace \(n\) by a rule-abiding expression evaluating to \(n\), which is exactly what \(e_n\) is:

\[[ -e_{n} + (n+1) ] * (n+2) = e_{n+2}\]

So we have proven that, given a valid solution for \(n\) called \(e_n\), we can form a valid solution to \(n+2\) called \(e_{n+2}\).

Now we have a complete proof: we gave two base cases and our inductive step, and therefore the puzzle is solvable for all integers \(n > 0\).

# From Induction to Recursion

This proof suggests a simple recursive program that computes the answer for any \(n\). We write a recursive function with two base cases (\(n = 1\) and \(n = 2\)), and the recursive case corresponds directly to the inductive hypothesis:

In Python:

```
def solve(n):
if n == 1:
return "1"
if n == 2:
return "1*2"
return "( -({}) + {} ) * {}".format(solve(n-2), n-1, n)
```

In Haskell:

```
1 = "1"
solve 2 = "1*2"
solve = "(-(" ++ solve (n-2) ++ ") + " ++ show (n-1) ++ ") * " ++ show n solve n
```

(Quick note: beware that in the program, I use \(n\) to refer to the “next” number in the induction, whereas I call this \(n+2\) in the proof)

Note that each call to the function `solve(n)`

returns a string - a rule-abiding
mathematical expression evaluating to \(n\). Here’s the output for \(0 < n < 7\):

\(n\) | Expression |
---|---|

\(1\) | \(1\) |

\(2\) | \(1*2\) |

\(3\) | \((-(1) + 2) * 3\) |

\(4\) | \((-(1*2) + 3) * 4\) |

\(5\) | \((-((-(1) + 2) * 3) + 4) * 5\) |

\(6\) | \((-((-(1*2) + 3) * 4) + 5) * 6\) |

Hopefully it’s clear that everything within the brackets on the left evalutes to \(1\), which is multiplied by the final term on the right (\(n\)).

Neato!

# Failed Attempts

This section contains a couple interesting but not-quite-right solutions I thought worth mentioning. Feel free to stop reading: you’ve had the main course.

## Gauss summation

Finally, if you’re interested, here is my first (failed) attempt at solving this puzzle. The first thing that came to mind when I saw it was Gauss’ summation trick, where numbers in the sequence \(1..n\) are paired up.

However, I only got this to work for \(n\) of the form \(n = 4k + 1, k > 0\).

Gauss (apocraphally) proved that the sum of the first \(n\) integers, \(S_n\) has an exact solution:

\[S_n = \frac{n(n+1)}{2}\]

This is done by pairing each number with its counterpart at the other end of the sequence, and summing these pairs. For example, if \(n = 5\), we have the following pairs:

\(i\) | pair | sum |
---|---|---|

1 | 1+5 | 6 |

2 | 2+4 | 6 |

3 | 3+3 | 6 |

4 | 4+2 | 6 |

5 | 5+1 | 6 |

This is \(5\) sums each equal to \(6\), for a total of \(n(n+1) = 5 \cdot 6 = 30\). However, we’ve used each number from the sequence exactly twice, so we must divide by 2:

\[S_n = 10 = \frac{n(n+1)}{2} = \frac{4 \cdot 5}{2} = 10\]

Back to our puzzle.

Given some \(n = 4k+1, k > 0\), We can use the same trick of pairing numbers to cancel out every term but the last. Consider \(n = 9\):

\[(-1) + 2 + (-3) + 4 + 5 + (-6) + 7 + (-8) + 9 = 9\]

Here we’ve paired up 8 with 1, 7 with 2, and so on. We then pair up the pairs, and negate every other pair so all but the last number cancels to zero.

Rearranging, this is more clear:

\[-(8 + 1) + (7 + 2) - (6 + 3) + (4 + 5) + 9 = 9\]

\[-9 + 9 - 9 + 9 + 9 = 9\]

However, this only works for \(n = 4k + 1\) because you need an even number of pairs to cancel out.

## Exponentiation

William Kamovitch also notes that if exponentiation is allowed, there is a trivial solution available for all \(n\):

\[1^{2 + ... + (n-1)} \cdot n = n\]

We need two base cases for the following reason: Suppose we only have a base case for \(n = 1\). Given a proof that \(n+2\) is solvable if \(n\) is, we have only proven the puzzle solvable for all odd numbers: we can prove \(n = 1\) is solvable, then \(n = 3\), and so on. We have to add the extra base case to make sure we can also “iterate” through the

*even*numbers.↩︎