Splitting Up Numbers

Time to take a break from thesis writing to blog. I won't have much time to blog for the next little while, due to said thesis, but I found a new puzzle recently I really wanted to post. I still intend to post the follow-up to my post from last time about other solutions to the birds on a wire problem, but I don't have the time to give that a full write up right now. Anyway, this puzzle is really weird to word properly, so if you don't get it the first time read the example I give after and then try reading it again. I first learned this puzzle on the forums at xkcd.
There are 2 blackboards, and on the first one a natural number N>1 is written, the second board starts empty. You are going to do a calculation in a series of steps. A step is defined as follows:

If there are no numbers greater than 1 on the first blackboard, stop. Otherwise select one of the numbers greater than 1, call it k. Select two natural numbers i and j smaller than k such that i+j=k. Cross out k from the first black board, and write i and j on the first blackboard. On the second blackboard, write the product i*j. Then do another step.

When you are done doing steps (because all the numbers on the first blackboard are equal to 1), and add up the numbers on the second blackboard, call this sum M.

The puzzle is, given the initial value of N, what are the possible values of M?

Alright, so as example, let us assume N=8. Now, we select a number of the board (there is only 8, so we choose it) and select that i and j are 5 and 3. We cross out 8 and write 5 and 3 on the first blackboard, and write 15 on the second one.

Next step we select 3, crossing it out and writing 1 and 2 on the first blackboard, writing 2 on the second blackboard. On the first board there is now (1,2,5) and on the second one there is (15,2)

Next step we select 5 and cross it out and write 2 and 3 on board one, writing 6 on board two. Board one has (1,2,2,3) board two has (15,2,6)

Next step we select 2, writing 1 and 1 in its place, and write 1 on board two. The boards are (1,1,1,2,3) and (15,2,6,1)

Next select 2, write 1 and 1 in its place, writing 1 on board two. The boards are (1,1,1,1,1,3) and (15,2,6,1,1)

Next select 3, writing 2 and 1 in its place, writing 2 on board two. The boards are (1,1,1,1,1,1,2) and (15,2,6,1,1,2)

Next select 2, writing 1 and 1 in its place, writing 1 on board two. The boards are (1,1,1,1,1,1,1,1) and (15,2,6,1,1,2,1)

Finally we stop, board one has no numbers greater than 1. We calculate M by adding up the numbers on board two, se we see M=28.

So we see that when N=8, it is possible for M to be 28. The puzzle is asking what other values of M are possible for N=8? What about other values of starting N?

No comments: