Author |
Topic: Detention with Dr. Taxicab (Read 1529 times) |
|
FiBsTeR
Senior Riddler
Gender: 
Posts: 581
|
 |
Detention with Dr. Taxicab
« on: Nov 2nd, 2007, 2:45pm » |
 Quote  Modify
|
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)
|
|
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Detention with Dr. Taxicab
« Reply #1 on: Nov 2nd, 2007, 2:50pm » |
Quote Modify
|
Adam can never win.
Total sum parity does not change and is initially odd.
|
|
IP Logged |
|
|
|
gotit
Uberpuzzler
Gender:
Posts: 804
|
|
Re: Detention with Dr. Taxicab
« Reply #2 on: Nov 2nd, 2007, 3:55pm » |
Quote Modify
|
on Nov 2nd, 2007, 2:50pm, Aryabhatta wrote:
Adam can never win.
Total sum parity does not change and is initially odd.
|
|
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.
|
|
IP Logged |
All signatures are false.
|
|
|
FiBsTeR
Senior Riddler
Gender:
Posts: 581
|
|
Re: Detention with Dr. Taxicab
« Reply #3 on: Nov 2nd, 2007, 5:54pm » |
Quote Modify
|
Both correct, although I think the two arguments are too similar to be considered "alternate." The parity of the sum remains the same because the parity of the number of odd numbers remains the same, right? Good explanation, nonetheless!
|
|
IP Logged |
|
|
|
gotit
Uberpuzzler
Gender:
Posts: 804
|
|
Re: Detention with Dr. Taxicab
« Reply #4 on: Nov 3rd, 2007, 8:31am » |
Quote Modify
|
[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.  
|
| « Last Edit: Nov 3rd, 2007, 8:54am by gotit » |
IP Logged |
All signatures are false.
|
|
|
inquisitive
Newbie
Posts: 5
|
|
Re: Detention with Dr. Taxicab
« Reply #5 on: Dec 14th, 2007, 4:52am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Detention with Dr. Taxicab
« Reply #6 on: Dec 14th, 2007, 4:57am » |
Quote Modify
|
on Dec 14th, 2007, 4:52am, 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.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Detention with Dr. Taxicab
« Reply #7 on: Dec 14th, 2007, 3:59pm » |
Quote Modify
|
on Dec 14th, 2007, 4:52am, 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.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Detention with Dr. Taxicab
« Reply #8 on: Dec 17th, 2007, 12:39pm » |
Quote Modify
|
on Nov 2nd, 2007, 2:50pm, Aryabhatta wrote:
Adam can never win.
Total sum parity does not change and is initially odd.
|
|
Why others try to find more complicated arguments when the first one is so easy? ...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Detention with Dr. Taxicab
« Reply #9 on: Dec 17th, 2007, 2:05pm » |
Quote Modify
|
on Dec 17th, 2007, 12:39pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
FiBsTeR
Senior Riddler
Gender:
Posts: 581
|
|
Re: Detention with Dr. Taxicab
« Reply #10 on: Dec 17th, 2007, 4:56pm » |
Quote Modify
|
on Dec 17th, 2007, 12:39pm, 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.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Detention with Dr. Taxicab
« Reply #11 on: Dec 18th, 2007, 12:35am » |
Quote Modify
|
on Dec 17th, 2007, 2:05pm, 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 Dec 17th, 2007, 4:56pm, 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".
|
| « Last Edit: Dec 18th, 2007, 12:43am by Hippo » |
IP Logged |
|
|
|
inquisitive
Newbie
Posts: 5
|
|
Re: Detention with Dr. Taxicab
« Reply #12 on: Dec 19th, 2007, 2:22am » |
Quote Modify
|
Thanks for explaining rmsgrey. 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print