wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> Word Problem
        
(Message started by: Radiohead_man on Dec 13^th, 2004, 8:05am)

Title: Word Problem
Post by Radiohead_man on Dec 13^th, 2004, 8:05am

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?

Title: Re: Word Problem
Post by John_Gaughan on Dec 13^th, 2004, 12:26pm

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?

Title: Re: Word Problem
Post by THUDandBLUNDER on Dec 13^th, 2004, 12:45pm

Quote:

Did you mean they do so while placing the signs?

That's how I interpret it.

:[hide]
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?) ;D
[/hide]

Title: Re: Word Problem
Post by John_Gaughan on Dec 13^th, 2004, 9:31pm

on 12/13/04 at 12:45:27, 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.

Title: Re: Word Problem
Post by Grimbal on Dec 14^th, 2004, 4:07am

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.

Title: Re: Word Problem
Post by THUDandBLUNDER on Dec 14^th, 2004, 5:26am

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?

Title: Re: Word Problem
Post by JocK on Dec 14^th, 2004, 1:17pm

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?

Title: Re: Word Problem
Post by Grimbal on Dec 15^th, 2004, 8:48am

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).