I have the following problem:
Alice writes the numbers $1, 2, 3, 4, 5, 6, \ldots, n$ on a blackboard. Bob selects two of these numbers, erases both of them, and writes down their sum on the blackboard. For example, if Bob chose the numbers 3 and 4, the blackboard would contain the numbers $1, 2, 5, 6, 7, 7, 8, \ldots, n\quad$ ($3$ and $4$ are removed from the list and $7$ is appended to the list)
Bob continues until there is only one number left on the board. What are the possible values of that number in terms of $n$?
I have tried using brute force on this problem with smaller values of $n$, and I seem to obtain that the number left on the blackboard is $\dfrac{n(n + 1)}{2}$. However, I cannot rigorously prove this, and I do not know if there are other possible values for the number. I would appreciate your help with this problem. Thank you!
Best Answer
Notice that the sum of numbers on the black board do not change after each turn.
For example, when consider the numbers $1,2,3,4$. If we erase $3$ and $4$ and replace it with $7$ then the remaining numbers will be $1,2,7$. Notice that the sum of numbers is same for both cases.
So the last number will be the sum of all numbers on the board at the beginning.