LOGIN/REGISTER
Please Wait...
It is currently Sep 02, 2010, 11:29 am
Post new topic Reply to topic  [ 4 posts ]  Share: Facebook
Message
Post Posted: Oct 07, 2009, 3:34 pm • # 1 


There are 2009 boxes numbered from 1 to 2009, some of which contain stones. Two players, A and B, play alternately, starting with A. A move consists in selecting a non-empty box i, taking one or more stones from that box and putting them in box i + 1. If i = 2009, the selected stones are eliminated. The player who removes the last stone wins
a) If there are 2009 stones in the box 2 and the others are empty, find a winning strategy for either player.
b) If there is exactly one stone in each box, find a winning strategy for either player.
 
 
Post Posted: Oct 09, 2009, 7:42 am • # 2 


An odd box is, for example, the box 17, the box 35,...

For the a part, the player B win because he allways can play such that all the stones, after he play, will be in even boxes, and then the player A cannot win, and so like the game is finite, the player B must win.

For the b part, I use the same strategy, it is that the player who can play such that, after the other player plays, the number of boxes odd and nonempty will be odd, and then is at least one, so he cannot lost. I will prove that the player A win.
Let k be the number of odd boxes wich ar nonempty in any moment.
In the begining of the game there are 1005 boxes that are nonempty and odd. The first play of the player A is select one stone of the box 2009. Now k is even. Then the player B can play of two ways:
1- If he select x stones from the box 2y, then in the next play the player A select x stones from the box 2y + 1 (it is easy to see that it allways is possible).
2- If he select 1 stone from the box 2y + 1, then in the next play the player A select 1 stone from the box 2z + 1.
We see that like in the begining there is one stone in each box, after B plays, the number k is allways odd if B played 2 (so z allways exist).
After A plays the number k is even and in each odd box the number of stones is 0 or 1. So the player A allways can play, and then he must win.


Last edited by gilcu3 on Oct 09, 2009, 9:44 am, edited 1 time in total.
 
 
Post Posted: Oct 09, 2009, 9:33 am • # 3 


gilcu3 wrote:
Let k be the number of odd boxes wich ar nonempty in any moment.
In the begining of the game there are 1005 boxes that are nonempty and odd. The first play of the player A is select one stone of the box 2009. Now k is even. Then the player B can play of two ways:
1- If he select x stones from the box 2y, then in the next play the player A select x stones from the box 2y + 1 (it is easy to see that it allways is possible).
if the first play of B is 1., then k is even after the play of A :|
 
 
Post Posted: Oct 09, 2009, 9:41 am • # 4 


Yes, I proved that after each play of A, the number k is even.
 
 
Display posts from previous:  Sort by  

All times are UTC - 8 hours [ DST ]

Share: Facebook

Moderators: MithsApprentice, N.T.TUAN, Peter, darij grinberg, orl, pbornsztein, freemind, Megus, High School Olympiad Moderators

Post new topic Reply to topic  [ 4 posts ] 

Login

Username:   Password:   Log me on automatically each visit  

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum