0
$\begingroup$

Start with positive integers: $1, 7, 11, 15, ..., 4n - 1$. In one move you may replace any two integers by their difference. Prove that an even integer will be left after $4n - 2$ steps.

I said, let $x_n$ be the $nth$ term of the sequence and I saw that for $n \ge 2$ it is:

$x_{n+1} - x_n = 4$ and $x_{n + 2} - x_n = 8$ and more generally, for a distance of $k$,

$x_{n + k} - x_{n} = 4k$.

To begin, take $11, 7$ you replace $11$ and $7$ with a number $11 - 7 = 4$. Hence,

$$S' = 1, 4, ... , 15, ... 4n - 1$$

After $1$ move, there is $1$ even number.

Take now, $23, 15$ you replace $23$ & $15$ with the difference, $23 - 15 = 8.$

$$S'' = 1, 4, ... , 8, 19, ... , 4n - 1$$

After two steps that are $4$ less odd numbers and $2$ more even numbers.

Suppose the sequence started with $4n - 1 = m$ odd numbers. Then, with $2$ steps there are $m - 4$ odd numbers and $2$ even.

Take now, $35, 19$. you replace it with $35 - 19 = 16$ Thus,

$$S''' = 1, 4, ..., 8, 16, 27, ..., 4n - 1$$

Now, after $3$ moves, there are $3$ even numbers and $m - 6$ odd numbers.

Meaning after $4n - 2$ moves there will be, $4n - 2$ even and,

$$m - 4n + 2 = 4n - 1 - 4n + 2 = 1$$ Odd number leftover. From the previous statement showing that the other numbers are all even $\ge 1$.

Is it an accurate proof?

$\endgroup$
  • 2
    $\begingroup$ For the record, do you really intend the list of numbers to begin with a one? If the general term of the initial list is $4n-1$ and for $n=1$ would that not imply that it begins with a $3$? $\endgroup$ – JMoravitz Apr 29 '15 at 17:45
  • $\begingroup$ Also, as for the content of your proof, this seems to be proof by example, which is not proof at all. You don't seem to have accounted for the fact that you could have chosen an odd number and an even number (which was previously created) to have an even number destroyed and an odd number created. $\endgroup$ – JMoravitz Apr 29 '15 at 17:48
  • $\begingroup$ Final question for clarification for now, you say "replace any two integers by their difference." Do both entries get filled by the difference? Or does our list decrease in size by one? If the list decreases in size, considering there are only $n$ entries in the list to start with, how could you do $4n-2$ steps total? (after the $n-1^{st}$ step, there would only be one entry left). $\endgroup$ – JMoravitz Apr 29 '15 at 17:59
1
$\begingroup$

Let $S_k = \text{Sum of terms left in the sequence after k moves}$. Then $S_0 = \sum_{i=1}^{n}(4i - 1) = 2n(n+1)-n = n(2n+1)$.

Further each move replaces $x,y$ by $x-y$ and $S_{k+1} = S_k-x-y+x-y = S_k -2y$.

Clearly, the parity(evenness/oddness) of $S_i$ does not change from odd to odd and $S_n = $ final term in sequence. The final term is odd if $n(2n+1)$ is and even otherwise.

$\endgroup$
  • $\begingroup$ You probably mean $n(2n+1)$. $\endgroup$ – Yves Daoust Apr 29 '15 at 18:40
  • $\begingroup$ Thanks for the correction. $\endgroup$ – Asvin Apr 29 '15 at 18:48
  • $\begingroup$ You didn't fix everywhere. $\endgroup$ – Yves Daoust Apr 30 '15 at 8:13
0
$\begingroup$

Assuming the rules of the game are that when selecting two numbers in the list, both entries are destroyed and replaced by two entries equal to the difference between them. Furthermore you are allowed to select any two numbers (even those which are equal or had been selected before). For example: 3,7,11,15: Pick first and second $\mapsto$ 4,4,11,15. (otherwise the statement of the problem makes no sense as otherwise the game has a finite length strictly less than $n$ and could not run for $4n-2$ steps).

Let $e$ be the number of entries that are even numbers, and $o$ be the number of entries that are odd numbers (duplicates allowed). We have that $e+o=n$. At the beginning of the first turn we have $o=n, e=0$

On each turn you have the option of one of three things:

  • Pick two even numbers (only allowed if $e\geq 2$). Their difference is even, and therefore $e$ and $o$ remain the same.
  • Pick an even and an odd number (only allowed if $e\geq 1$ and $o\geq 1$). Their difference is odd, and therefore $e$ decreases by one and $o$ increases by one.
  • Pick two odd numbers (only allowed if $o\geq 2$). Their difference is even, and therefore $e$ increases by two and $o$ decreases by two.

If after our $4n-2$ steps our list is comprised entirely of odd integers, that means that we had picked the second option twice as often as the third option.

We ask ourselves if this is possible. Indeed, it is. Let $a$ be the number of times we use option 1, $b$ be the number of times we use option 2, and $c$ be the number of times we use option 3. Then we could use $b=2, c=1, a=(4n-2)-3=4n-5$.

Example:

$\begin{array}{cccc|c} 3 & 7 & 11 & 15 & \text{pick first and second}\\ 4 & 4 & 11 & 15 & \text{pick first and second}\\ 4 & 4 & 11 & 15 & \text{pick first and second}\\ \vdots&\text{a total of}~4n-5=11~\text{times}\\ 4 & 4 & 11 & 15 & \text{pick first and third}\\ 7 & 4 & 7 & 15 & \text{pick second and fourth}\\ 7 & 11 & 7 & 11 & \text{end}\end{array}$

Thus the claim is false and you are not guaranteed to end with any evens in the list (though it is certainly possible to).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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