wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Detention with Dr. Taxicab
        
(Message started by: FiBsTeR on Nov 2nd, 2007, 2:45pm)
Title: Detention with Dr. Taxicab
Post by FiBsTeR on Nov 2nd, 2007, 2:45pm
John and Adam just landed a Saturday detention with Dr. Taxicab, the crazy math teacher (don't ask what they were doing). When John and Adam got to the detention room at 7:00 AM, they saw, on the giant whiteboard, the numbers 1 through 1729 written out, and a note with the following instructions:

"Each of you will take turns erasing two numbers and replacing them with the positive difference of the two erased numbers. You will continue until only one number remains on the board. John will win if the number remaining is odd, and Adam will win if the number remaining is even."

Assume that John and Adam do not play any strategy (they just want to get out as fast as possible, so they pick random numbers). What is the probability that Adam wins the game?

(Source: BWM)
Title: Re: Detention with Dr. Taxicab
Post by Aryabhatta on Nov 2nd, 2007, 2:50pm
[hide]

Adam can never win.

Total sum parity does not change and is initially odd.

[/hide]
Title: Re: Detention with Dr. Taxicab
Post by gotit on Nov 2nd, 2007, 3:55pm

on 11/02/07 at 14:50:35, Aryabhatta wrote:
[hide]

Adam can never win.

Total sum parity does not change and is initially odd.

[/hide]


[hide]I agree with the answer but I have an alternative explanation. What I observed is that the parity of the number of odd numbers in the set never changes. Let us say that the number of odd numbers is initially n. Now at each step there are three possibilities:
i) Both numbers picked up are even and so is their difference.In this case, the number of odd numbers remain n.
ii) Both numbers are odd and hence the difference is even. In this case, the number of odd numbers decreases by two and hence parity remains same.
iii) One is even and one is odd and hence the difference is odd. So the number of odd numbers remain n.
In the problem, the number of odd numbers is 865 and hence the last number that will be left has to be odd since we cannot have 0 odd numbers left.[/hide]
Title: Re: Detention with Dr. Taxicab
Post by FiBsTeR on Nov 2nd, 2007, 5:54pm
Both correct, although I think the two arguments are too similar to be considered "alternate." [hide]The parity of the sum remains the same because the parity of the number of odd numbers remains the same, right?[/hide] Good explanation, nonetheless!
Title: Re: Detention with Dr. Taxicab
Post by gotit on Nov 3rd, 2007, 8:31am
[quote author=FiBsTeR link=board=riddles_easy;num=1194039906;start=0#3 date=11/02/07 at 17:54:56]Both correct, although I think the two arguments are too similar to be considered "alternate."/quote]

It should have been "elaborate" instead of "alternate". Not very strong in English. :P ;)
Title: Re: Detention with Dr. Taxicab
Post by inquisitive on Dec 14th, 2007, 4:52am
please clear my confusion.


Say in the end you have 2 odd numbers remaining and 1 even.....Then the difference that remains is even
bcoz odd-odd=even
and even-even=even
Title: Re: Detention with Dr. Taxicab
Post by pex on Dec 14th, 2007, 4:57am

on 12/14/07 at 04:52:48, inquisitive wrote:
please clear my confusion.

Say in the end you have 2 odd numbers remaining and 1 even...

The proofs above show that this cannot happen.
Title: Re: Detention with Dr. Taxicab
Post by rmsgrey on Dec 14th, 2007, 3:59pm

on 12/14/07 at 04:52:48, inquisitive wrote:
please clear my confusion.


Say in the end you have 2 odd numbers remaining and 1 even.....Then the difference that remains is even
bcoz odd-odd=even
and even-even=even


At any moment, you have some number, a, of odd numbers and some number, b, of even numbers left.

If you pick two odd numbers, you then have (a-2) odd numbers and (b+1) even numbers.
If you pick two even numbers, you then have (a) odd numbers and (b-1) even numbers.
If you pick one odd and one even number, you then again have (a) odd numbers and (b-1) even numbers.

Since the number of odd numbers remaining only ever changes by decreasing by two, you can never change from an odd number of odd numbers remaining to an even number of odd numbers remaining, nor vice versa.

For example, there are 18 possible ways the game could play out starting with four numbers (6 possible initial pairs, and 3 choices of second pair for each, which leaves only one choice for third pair). If you pick any four numbers and run through the 18 games, you'll find that the answers all come out even or all come out odd, depending on how many odd numbers you started with.
Title: Re: Detention with Dr. Taxicab
Post by Hippo on Dec 17th, 2007, 12:39pm

on 11/02/07 at 14:50:35, Aryabhatta wrote:
[hide]

Adam can never win.

Total sum parity does not change and is initially odd.

[/hide]


Why others try to find more complicated arguments when the first one is so easy? ...
Title: Re: Detention with Dr. Taxicab
Post by towr on Dec 17th, 2007, 2:05pm

on 12/17/07 at 12:39:33, Hippo wrote:
Why others try to find more complicated arguments when the first one is so easy? ...
Some people try to find an answer before they look at the ones that are already there. And then if it hasn't been mentioned (and sometimes if it has), they share their thought.
Title: Re: Detention with Dr. Taxicab
Post by FiBsTeR on Dec 17th, 2007, 4:56pm

on 12/17/07 at 12:39:33, Hippo wrote:
Why others try to find more complicated arguments when the first one is so easy? ...


Can you elaborate which argument you are referring to? It seems that all of the above posts are talking about the same thing, namely the fact that the parity of the sum never changes.
Title: Re: Detention with Dr. Taxicab
Post by Hippo on Dec 18th, 2007, 12:35am

on 12/17/07 at 14:05:19, towr wrote:
Some people try to find an answer before they look at the ones that are already there. And then if it hasn't been mentioned (and sometimes if it has), they share their thought.


I usually try to figure the solution myself, but before posting I scan written solutions ... . I just want to say ... good solution, the following are not as nice.


on 12/17/07 at 16:56:19, FiBsTeR wrote:
Can you elaborate which argument you are referring to? It seems that all of the above posts are talking about the same thing, namely the fact that the parity of the sum never changes.


Parity of sum never changes is much simpler argument than parity of odd numbers never changes. The proof of the first does not require to study several cases ...

Parity of sum does not change as the parity of diference of the erased numbers is the same as the sum of parities of the two erased numbers. (And the sum is associative and commutative ;) )

Or parity does not change by negation.
Sum is associative and commutative and the operation just negates some arguments and adds parentesis to the expression for the "parity sum".
Title: Re: Detention with Dr. Taxicab
Post by inquisitive on Dec 19th, 2007, 2:22am
Thanks for explaining rmsgrey.  :)


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board