Consider a sequence of integers in arithmetical progression: A, A+B, A+2B, A+3B, ... A+NB.

Systematically pick any two adjacent numbers, and randomly replace them by their sum or difference. Keep at this until only one number remains. Is this number odd or even? What's the largest value this number can attain?

The most that the value can be is just the total of all the numbers in the series.  That's (N+1)(A+NB/2).

The parity of that number depends on the parities of N, A and B.  If N is odd, the result will be even.  If N, A and B are all even, the result is even.  If N and B are even but A odd, the result is odd.

If B is odd and N even, the results depend on the parity of A as well as whether N is a multiple of 4.  If A is even and N is a multiple of 4, the result is even; if N is not a multiple of 4 the result is odd.  If A is odd, it's just the opposite: if N is a multiple of 4, the result is odd; if N is not a multiple of 4 the result is even.

The above assumes that all the random choices of what to do with adjacent numbers were to add.  But the effect of subtraction on parity is the same as the effect of addition on parity, so the same rules apply with regard to the parity (and divisibility by 4) of the variables as given above.

[spelling and grammar corrections]

 

Edited on October 1, 2004, 10:37 am

Posted by Charlie on 2004-10-01 09:22:17