Puzzle Remaining Numbers on board. Erase 2 numbers but add the difference

Question

This is the question I get from Geeks For Geeks.

The problem is, given the first $50$ natural numbers, i.e., from $1$ to $50$ which are written on a board. Select two of the numbers on the board, say $a$ and $b$, write the absolute value of their difference $|a - b|$ on the board and then erase both $a$ and $b$. Apply the above operation $49$ times. Determine all possible values of the remaining number that can be obtained in this manner.

Here is the link of the question with the solution. Step $6$ to $8$ are here:

6. Also given that all the numbers on the board are always nonnegative. They are also less than or equal to $50$, since $|a - b|$ is always less than or equal to the maximum of $a$ and $b$ for nonnegative $a$ and $b$. Now, any odd integer from $1$ to $49$, inclusive, can be obtained by applying the puzzle’s operation $49$ times.
7. Let $k$ be such a number. This can be obtained in the first iteration by subtracting $1$ from $k + 1$ as $|1 - (k + 1)| = k$.
8. Then, apply the operation to the pairs of the remaining consecutive integers, $(2, 3), (4, 5), . . . , (k – 1, k), (k + 2, k + 3), . . . , (49, 50)$, to get $24$ ones on the board while erasing the above pairs.

I cannot get what does author mean in step $8$, why choose the number in a way that in order? why not $(2,4),(3,5),(6,9)$ and so on? This is my first question.

Next, if we erase $a$ and $b$ from board, new number added, the author seems not adding that instantly after the erasing of $a$ and $b$. For exp, in step $6$ we obtain a number $k$, so $k$ should be added into the board for next calculation right?

These are my question, thanks in advanced!

Answer 1

The goal is to show that exactly all odd integers between 1 and 49 inclusive can be constructed.

So first, the author shows that only those values could possibly be reached, because the sum of all numbers always remains odd and one can not create integers less than 0 or greater than 50. (steps 1 to 5).

Then he shows that all those values can be reached. To do so, he chooses such a k and exhibits a construction where this k is constructed within the first step via $k = k+1-1$ and never touched again until the very end where he does $k = k-0$. After step 1 he thus has two $k$'s at his disposal : the original one and the one he just obtained. One of them is going to be used up in the pairings, the other one kept until the end.

And as for why he chooses to pair does particular numbers together: well, because he can and because it works. He is free to chooses whatever pairs he likes, so he chooses those which lead him easily to his goal of ending up with a $0$ and a $k$. He first creates a bunch of $1$'s while leaving $k$ alone, creates a bunch of $0$'s out of those $1$'s and then lets all these $0$'s "cancel out", until he's left with only $0$ and the $k$ he saved from step 7.

(I don't know if this deserves to be a full blown answer, I would post it as a comment but don't have the necessary reputation)

Answer 2

In this scenario, it is only possible to end up with an odd final answer. The reason why comes down to what happens during each step.

Given two numbers $A$ and $B$, they are both erased and replaced with $\left|{A-B}\right|$. There are three possible scenarios:

1. Both $A$ and $B$ are even The difference of two even numbers is always even, so you replace two even numbers with one even number.

2. Both $A$ and $B$ are odd The difference of two odd numbers is always even, so you replace two odd numbers with one even number.

3. Either $A$ or $B$ is even, and the other is odd. The difference of an odd and an even is always odd, so you replace one odd and one even number with just an odd one.

With that out of the way, let's look at what happens to the list of numbers after each step. Assume $O$ is the total of odd numbers, and $E$ is the total of even numbers. $E$ decreases by one in the first and third cases, and increases by one in the second case. $O$, on the other hand, doesn't change except in the second case, where it decreases by two. Therefore, if $O$ is originally even, it will always be even, and if $O$ is originally odd, it will always be odd.

Applying this to the original question is simple. Given the numbers $1-50$, there are $25$ odd numbers. As $O$ can only decrease by two, there will always be at least one odd number, and therefore the last number will be odd.

Answer 3

In answer to the OP's questions, it might be easiest to explain things with an explicit example.

Step 6 really just says you can pick any odd number (between $1$ and $49$) as a target value to be left at as the final value. Let's say we pick $k=37$ as the target.

Step 7 says to select $1$ and $38$ for the first subtraction. This leaves us with two copies of the number $37$, so we're left with

$$2,3,4,\ldots36,37,37,39,40,\ldots,49,50$$

Step 8 now tells us, in effect, to pair things off as follows:

$$(2,3),(4,5),\ldots,(36,37),37,(39,40),\ldots,(49,50)$$

and then for each pair do their subtractions, leaving a bunch of $1$'s:

$$1,1,\ldots1,37,1,1,\ldots,1$$

What's crucial here is to realize that you now have an even number of $1$'s ($24$ of them, to be precise). So move all the $1$'s to the front and then pair them off:

$$(1,1),(1,1),\ldots,(1,1),37$$

and now subtract those pairs, leaving a bunch of $0$'s ($12$ of them, to be precise):

$$0,0,\ldots,0,37$$

Finally, just subtract the $0$'s, one at a time, from either each other or from the $37$, until all that's left is the $37$.

Added later: Just for completeness, even though the OP doesn't explicit ask about it, we can show that it's impossible to wind up with any even number as the final result. This is because we start with an odd number of odd numbers ($25$, to be precise, namely $1,3,5,\ldots,49$), but each step leaves the number of odd numbers odd: You either don't change the number of odd numbers (if one of the pair of selected numbers is even), or the number of odd numbers decreases by two (because odd minus odd is even). So you can't get from $25$ odd numbers to $0$ odd numbers. A bit more thought shows this is a general result: If you start with the numbers $1$ to $2n$ (or $2n-1$), you can get to any odd number but no even number if $n$ is odd, and to any even number but no odd numbers if $n$ is even.