Urn and slips of papers question  TOPIC_SOLVED

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.

Urn and slips of papers question

Postby seisai on Sun May 10, 2009 1:43 am

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.
seisai
 
Posts: 1
Joined: Sun May 10, 2009 1:27 am

Sponsor

Sponsor
 

Postby stapel_eliz on Mon May 18, 2009 2:54 pm

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....
User avatar
stapel_eliz
 
Posts: 1785
Joined: Mon Dec 08, 2008 4:22 pm

Re: Urn and slips of papers question  TOPIC_SOLVED

Postby wh1t3 on Fri Dec 11, 2009 4:06 pm

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.
wh1t3
 
Posts: 1
Joined: Fri Dec 11, 2009 3:59 pm


Return to Discrete Math