Question

I came across an interesting problem in a book:
The integers 1, 2, 3, ..., 100 are written on a blackboard. Each minute, 2 numbers a and b are chosen, erased, and replaced by the number ab+a+b. At the end of the 99th minute, only one number remains. Does this number depend on the choices made at each minute?
So I tried first with 1, 2, ..., 7 and after two different paths, I ended up with 40319 as the last number. So I thought maybe the last number was (n+1)!-1 where n is the number of digits initially. How do I prove this, though?

Answer 1

If you wanted to rigorously prove it, you would need to do it by induction on the number integers. Your answer is correct though. Note that:\[ab+a+b=(a+1)(b+1)-1\]I'll demonstrate the process with 4 random numbers, and it should make the pattern clear. Lets say we started with:\[w,x,y,z\]four random integers. We pick w and x, and replace with (w+1)(x+1)-1:\[(w+1)(x+1)-1,y,z\]Now lets say I pick the new number and y:\[((w+1)(x+1)-1+1)(y+1)-1=(w+1)(x+1)(y+1)-1\]So now i have two numbers left:\[(w+1)(x+1)(y+1)-1,z\]Finally i pick the last two numbers which will leave me with a final answer:\[(w+1)(x+1)(y+1)(z+1)-1\]It should be clear if you are given a list of k integers:\[x_1,x_2,x_3,\ldots ,x_k\]after you perform this process you will end up with:\[(x_1+1)(x_2+1)(x_3+1)\cdots (x_k+1)-1\]In the case your numbers are the first k natural numbers, you do end up with the answer you posted.

Answer 2

So recognizing that ab+a+b=(a+1)(b+1)-1 was pretty much the trick there.

Answer 3

Interestingly enough, this problem is under invariants, so I could also prove that the quantity gotten by adding one to all numbers, multiplying these, then subtracting one is the same at each step and thus an invariant.