Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose we have a line of 2013 banks that ends with a vault. The bank nearest to the vault has 1 sack of money, the bank second nearest has 2 sacks. The bank farthest away has 2013 sacks.

Jerry corporation and Meyer corporation are hired to take the sacks of money to the vault. In each turn a player can select a bank and take a positive integer number of sacks to the next bank (or directly to the vault if he chose the bank next to the vault). The winner is the company that makes the move that leaves all bags in the vault.

Which player has a winning strategy? Which is the strategy? Can we generalize to $n$ banks?

share|improve this question
    
Why did you post this as math.stackexchange.com/questions/755036/… and then delete it and then post it again? –  Gerry Myerson Apr 16 at 13:45
    
Because yolo swag. No because I accidentaly typed it wrong the first time and that caused it not to get points. –  Bananarama Apr 17 at 0:14
    
So, why didn't you just edit it? –  Gerry Myerson Apr 17 at 1:24
    
I did, but it didn't receive attention. Now it did. –  Bananarama Apr 17 at 5:14
    
Shooting up a movie theater also receives attention. More justification is needed. –  Gerry Myerson Apr 17 at 12:04

1 Answer 1

up vote 2 down vote accepted

Hints: this is an impartial game, so must be Nim. Each bank is a nim heap. The first bank is clearly a heap of the number of bags in it. Even numbered banks don't matter, as the second player can mirror the first player's actions, moving each bag down two positions and ending in the vault.

share|improve this answer
    
So how can I work out who wins? –  Bananarama Apr 17 at 0:23
    
You need to equate each bank to a Nim heap. The problem is to find the size. I gave some big hints, particularly the one about the even banks being zero. Then Nim add them, which is bit wise XOR. If you get zero the second player wins –  Ross Millikan Apr 17 at 1:06
    
I suppose it goes without saying that you will have to read up on Nim to take full advantage of Ross' answer & comment. But Ross has given you a link, so you should be OK on that. Once you've done that, you can post a complete answer, if you like. –  Gerry Myerson Apr 17 at 1:26
1  
I could just tell you the winner. Otherwise I would have to write a whole treatise on Nim, which already exist. The Sprague-Grundy theorem is central to the analysis. There is a nice discussion of this and much more in Winning Ways-‌​a fabulous book. –  Ross Millikan Apr 17 at 4:03
    
Thank you, I got it. –  Bananarama Apr 17 at 14:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.