All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Games
a version of NIM (Posted on 2016-02-04) Difficulty: 3 of 5
Alice and Bob play a game in which they take turns removing stones from a heap that initially has n stones.
The number of stones removed at each turn must be one less than a prime number. Alice goes first.

The winner is the player who takes the last stone.

Prove that there are infinitely many values of n such that Bob has a winning strategy.

No Solution Yet Submitted by Ady TZIDON    
Rating: 4.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts Mapping out a bit | Comment 2 of 4 |
I had a bit of trouble following Steve's proof so I tried to see how the game behaves fro various n.

Each starting position is either a Win for A or a Lose for A (win for B).
W* means a win in one move (one less than a prime) W with a number indicates how many A should take to reach an L.
0L (if you see 0 on your turn you just lost)
1W*
2W*
3L (can only reach 1 or 2)
4W*
5W-2
6W*
7W-4
8L (can only reach 2, 4, 6, or 7 but not 3)
9W-1
10W*
11L (can only reach 1,5,7,9,10 but not 3 or 8)
12W*
...and so on up to 31 every position is a W...
32L (can't reach 3, 8, or 11)

There aren't many L's.   At first glance it seems they may peter out. 
However, as Steve points out, there will eventually be a position that can't reach 3, 8, 11, or 32 because at some point there just aren't enough primes to choose from to hit one of these targets.

Surprisingly there doesn't seem to be an OEIS entry for the sequence 3,8,11,32


  Posted by Jer on 2016-02-04 20:20:26
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information