status
failed

# 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)

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

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

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