2
$\begingroup$

The numbers from 1 to 1000 are written on a board. You are allowed to select any two numbers, erase them and write their difference on the board. If this process is repeated often enough, there is only one number written on the board.

Is this number always even, always odd or can it be even or odd?

$\endgroup$
1
  • 1
    $\begingroup$ In particular, the solution is covered in the first part of 2012rcampion's answer $\endgroup$
    – hexomino
    Sep 2 at 20:46
6
$\begingroup$

The answer is:

The result is always even.

The proof:

Let L be the number of odd numbers on the board at any step, and note that initially L is even. At each step, either:

- Two odd numbers are selected, in which case two odds are deleted, and an even added;
- Two even numbers are selected, in which case no odds are deleted and one even added;
- One of each is selected, in which case one odd is deleted, and one odd is added.

In any case, the number of odd numbers is always even. Hence, at the last step when only one number is left, the number of odd numbers on the board must be even and less than 1. Hence there are no odd numbers on the board and the result is even.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.