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?

Note: I am assuming that when you replace them by their difference, you are always replacing the absolute value of their difference (so no negative numbers). If this is incorrect, then I’ll have to reevaluate.

The largest value will be when you always sum two adjacent numbers.

Well, if you sum all the 0th through Nth term (so in total you have N+1 terms), you have (N+1)A + N(N+1)B/2. I think the evenness or oddness of this value depends on many things. Let’s see if N, A, B are odd or even, we have 8 combinations.

The sum will always be even when (a) A and B are both even, N doesn’t matter, (b) N and A are odd while B is even. So that’s 3 out of 8 cases.

The sum will always be odd when N and B are even while A is odd. So that’s 1 out of 8 cases.

Now come the tricky cases. When B is odd, the only way for N(N+1)B/2 to be even is if N(N+1)/2 is even. This can only happen when either N or N+1 is divisible by 4. Always, either N or N+1 is even and the other is odd. In that case, the one that is even has a 50:50 chance of being divisible by 4. So when B is odd, we will always have a 50:50 chance of having N(N+1)B/2 be even, regardless of what N is.

What does that mean for the full sum? Well, depending on the evenness or oddness of (N+1)A, in each of the cases where B is odd, the sum has a 50:50 chance of being even or odd. So that basically means that for these remaining 4 cases, "2" out of "4" of them are odd, and "2" out of "4" of them are even.

So 5/8 of the time, the answer will be even, 3/8 it will be odd.

A more detailed layout follows:

(N, A, B) Result of full Sum
(E, E, E) Even
(E, E, O) if N mod 4 = 0, then Even, else Odd
(E, O, E) Odd
(E, O, O) if N mod 4 = 0, then Odd, else Even
(O, E, E) Even
(O, E, O) if (N+1) mod 4 = 0, then Even, else Odd
(O, O, E) Even
(O, O, O) if (N+1) mod 4 = 0, then Even, else Odd

I don’t know how to prove if the results would be the same or not depending on random "sum or difference" decisions. I have a feeling they are, but like I said, no clue to how to prove… I will now peruse Charlie’s answer and prepare to say "ahhhhh"

Posted by nikki on 2004-10-01 11:37:33