The Pluses Problem

On his blog, Rational Mathematics Education, Michael Goldenberg mentions this problem by way of one Maria Miller (her blog here.)

How many addition signs should be put between digits of the number 987654321 and where should we put them to get a total of 99?

Michael finished his blog entry with "It would also be great if anyone has other extension ideas for this ... The one I'd suggest right away is: What happens if we change 99 to other values?"

This got me thinking along a slightly different line - what other totals have multiple solutions and could I write a program to find them?

It turns out that there are 209 possible totals (including 987654321), of which 31 can be formed in more than one way. Four totals (153, 171, 180, 189) can be formed in four different ways, seven totals can be formed in three different ways, and the rest in two different ways.

The program to find this is conceptually quite simple... if you can get your head around recursion.

The logic: for a given number, take the first n digits (where n is progressively a number from 1 to the total number of digits), convert to a single value, then with the remainder, do the same thing again.

Programming this in Python ended up being simple, but not before I went down a few blind alleys:

def Chunkit(x,p=[]):
for i in range(len(x)):
   p.append(int(x[:i+1]))
   if i == len(x)-1:
       print p, sum(p)
       print
   else:
       Chunkit(x[i+1:])
   p.pop()
return p

num = raw_input("Enter a number: ")
Chunkit(str(num))

The sticking point was line 9:

p.pop()

At first, it's not obvious why this is necessary, but if you leave it out (as I initially did), you soon see the consequences.

With the program written and working correctly (with a few additions to produce the list of totals and how often they occur), exploring the original problem led to the results given above. It also allowed me to examine different number sequences, such as 123456789, which can be made to total 99 three different ways rather than two. (And totals of 153 and 162 can be made five different ways.) Or 123454321, which can be made to total 97 in eight different ways.

Of course, having posted here what I think is a fairly neat solution (only 13 lines of code), no doubt some script-kiddy will pop up with a four line solution in Ruby or OCaml or whatever is the trendy language this week. But at least I now have another interesting problem to discuss with my students.