Urn and slips of papers question

[seisai]

Hello, I need help with my question. Thank you :]

Consider an urn containing 1996 slips of papers numbered from 1 to 1996. A procedure consists of three steps:

1. Take two slips from the urn.
2. Write down the absolute value of the difference of the numbers on the slips of step1 on a new slip of paper.
3. Discard the two slips in step1 and replace them with the slip in step2 into the urn.

Repeating the procedure until only one slip of paper is left in the urn, prove that the number on this slip is even.

[stapel_eliz]

I think maybe you can proceed by induction. It is important that the upper limit on the numbers is a multiple of 4, so use the rule n = 4m for some counting number m. Then prove the case for m = 1 by showing cases. Assume the rule for m = k. Then see where you can go with m = k + 1. Strong induction might be helpful....

[wh1t3]

Hey,

know its an old posting, but was working on something similar and came across this. Have solved it, thought i might share for other people that might stumble across this.

Basically my solution is to look at possible cases. When taking 2 slips there are three possible cases. (Here n denotes the number of even valued slips and m the number of odd ones).

case 1: take two even numbers.          ==> n=n-1 m=m
case 2: take an odd and an even number. ==> n=n-1 m=m
case 3: take two odd numbers.           ==> n=n+1 m=m-2

At the start there are 1996 slips, so both n and m are even (1996/2). The only case that leaves an odd number if its the last case that happens is case 2. For this to happen both m and n need to be 1 at the end. So one even and one odd valued slip. However, since at the beginning m is even and we only ever decrease m with 2 (in case 3) m will always stay even and therefore we can never get the situation described above. So the last number will always be even.