Author |
Topic: Word Problem (Read 4180 times) |
|
Radiohead_man
Junior Member
Gender: 
Posts: 74
|
 |
Word Problem
« on: Dec 13th, 2004, 8:05am » |
 Quote  Modify
|
Twenty numbers (1, 2, 3,..., 20) are written on the blackboard. Two players take turns putting the signs '+' and
'-' in front of any free number. The first player tries to minimize the absoute value of the resulting sum (after twenty signs have been placed). What is the maximum absolute value the second can always achieve?
|
|
 IP Logged |
I'm a reasonable man
get off my case, get off my case.
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
 
Gender:
Posts: 767
|
|
Re: Word Problem
« Reply #1 on: Dec 13th, 2004, 12:26pm » |
Quote Modify
|
How can either player minimize or maximize the sum after they place all the signs? Do they move numbers around? Addition is commutative 
Did you mean they do so while placing the signs?
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Word Problem
« Reply #2 on: Dec 13th, 2004, 12:45pm » |
Quote Modify
|
Quote:| Did you mean they do so while placing the signs? |
|
That's how I interpret it.
:
I think the first pair must be (+1, +20) [or (-1, -20)]
We are now on +21, so perhaps the 1st Player should now choose -19, and then the 2nd Player chooses +18, etc. This method gives a minimax of 12 (and a minimax of n+2 with 2n numbers).
(How long do you think you will be able to bear thinking about it before writing a program?) 
|
| « Last Edit: Dec 15th, 2004, 10:54am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Word Problem
« Reply #3 on: Dec 13th, 2004, 9:31pm » |
Quote Modify
|
on Dec 13th, 2004, 12:45pm, THUDandBLUNDER wrote:| How long do you think you will be able to bear thinking about it before writing a program? |
|
This problem does not lend itself well to a problem. Sure, a brute force approach might work, but that is not very exciting when the real question is in the strategy.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: Word Problem
« Reply #4 on: Dec 14th, 2004, 4:07am » |
Quote Modify
|
If the 2nd player systematically uses up numbers 1 to 10, then his last move is at least of value 10. At worst, the 1st player managed to zero the sum at that point. So the 2nd player can at least achieve 10.
This is a minimum for the maximum asked.
|
|
IP Logged |
|
|
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Word Problem
« Reply #5 on: Dec 14th, 2004, 5:26am » |
Quote Modify
|
Quote:| If the 2nd player systematically uses up numbers 1 to 10, then his last move is at least of value 10. |
|
Sorry, I don't follow this argument.
Quote:| This is a minimum for the maximum asked. |
|
Are we answering the same question?
Do you agree that 12 is a better answer than 10?
If so, how does the 1st Player thwart my minimax of 12?
|
| « Last Edit: Dec 15th, 2004, 5:41am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Word Problem
« Reply #6 on: Dec 14th, 2004, 1:17pm » |
Quote Modify
|
Agree with T&B:
the best player one can do is to start using the number 1 and thereafter the highest available number. In that way, with the numbers 1, 2, .. 2N initially available, he can keep player 2 to a maximum no larger than N+2.
It is clearly disadvantageous for the 'minimizing player' to start. But wat if at the end of the game the first player (who needs to minimize the absolute value of the sum) is allowed to (but does not need to) reverse the sign of the number first selected? With these modified rules, what is the maximum value the 2nd player can achieve?
|
| « Last Edit: Dec 14th, 2004, 1:20pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: Word Problem
« Reply #7 on: Dec 15th, 2004, 8:48am » |
Quote Modify
|
Sorry, T'n'B, I didn't see your hidden text. I wanted to start the discussion and show that the maximizing player can make at least 10. Of course, your result of 12 is better. (But it does not invalidate my minimum).
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print