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\):

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\)¹, 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:

solve 1 = "1" 
solve 2 = "1*2"
solve n = "(-(" ++ solve (n-2) ++ ") + " ++ show (n-1) ++ ") * " ++ show 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\):

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:

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\]