First of all, if you played around with it a bit, you probably determined that for any starting N, only one final M was ever possible. As far as I am concerned, that fact was in of itself neat enough to make this puzzle pretty cool, but lets look at it a bit more.
First, if you just split N into N-1 and 1, and then N-1 into N-2 and 1 and just keep splitting off 1 all the way down, then you end with having written N-1, N-2, N-3,..., 2, 1 on board two, so the total sum is N(N-1)/2. Thus, if for any N there is only one possible value of M, that value must be N(N-1)/2. Note a particular edge case, that of N is 1, we take the value of M to be zero, later we will see that this is important for consistency.
Alright, so let us conjecture the solution to the puzzle:
When N is the starting value, then N(N-1)/2 is the unique final value of M.
Initially I wanted to prove this by induction, and one almost can, but actually to do it properly you need to break out strong induction, which I will talk briefly about first.
Induction is used if you want to prove some statement S(n) for all natural numbers n (and for the purpose of this post, the naturals start at 1 (and it pains me to write that)). You prove the statement is true by first showing that S(1) is true, and then showing that S(k-1) implies S(k) for k>1, good stuff, and the intuition behind it is pretty obvious for anybody who would actually read this blog.
For strong induction, you instead prove S(n) by proving S(1) and then show that [S(j) for all j less than k] implies S(k) for k>1. Intuitively, its not really any different from regular induction, the assumption is technically a bit different, but it still works. Naturally, one can reformulate any induction proof as a strong induction proof, as the strong induction assumption of [S(j) for all j less than k] is a stronger assumption than S(k-1), but there are some strong induction proofs that cannot be recast as regular induction, since you needed the stronger assumption. Strong induction is also used for proving statements about the ordinals, since some of those are not successors to other ones.
Anyway, let us prove our earlier conjecture by strong induction. It is easy to see that it holds for small N (I'm not sure about proving it for N=1, but lets just start with 2 or something). Now, assume that it is true for all j less than k for some k. Lets say that k is written on the board and calculate the possible values of M. We break k into p and k-p, for some p less than k. We then write p(k-p) on board 2, and are left with p and k-p on board 1. Naturally breaking up p results in us writing numbers summing to p(p-1)/2 on board 2 (by strong induction assumption) and breaking up k-p results in us writing numbers summing up to (k-p)(k-p-1)/2 onto board 2. Note that if p=1 or p=k-1, then having a 1 on board one does not result in any additional numbers on board 2, good.
So, on board 2, we have p(k-p) and a bunch of other numbers that sum to p(p-1)/2 and (k-p)(k-p-1)/2. Adding those up, we get k(k-1)/2 for any choice of p, proving the conjecture.
On the xkcd forums, somebody posted a much simpler solution than mine, and its cool enough that I will give it here.
Consider that we have N people in a room, and breaking N up into p and N-p is splitting people up into smaller groups. Before we split people up, they all shake hands with the people in the other group and say goodbye. For example, when we split 8 into 5 and 3, the 5 people each shake hands with the 3 people, so there are 15 handshakes. Board 2 is just keeping track of handshakes. The steps halt when everybody has been fully divided up and everybody must have said goodbye to everybody else. How many handshakes were there? There must have been N choose 2 of them, which is N(N-1)/2.
