Pick a stone, or two, .... or three

Wacky · 2003-06-24, 00:46

Here is a little two person game to play.

Start with a small pile of stones in the middle. Make that an odd number of stones, for example, 13.
Players alternate turns taking some stones from the pile. They must take either 1, 2, or 3 stones in each turn.
After the last stone is taken, the winner is the player that has an odd number of stones.

question Can either player force a win? If so, what is the winning strategy?

idea What happens if we start with a different (odd) number of stones?

hyh1048576 · 2003-06-24, 09:36

That's EASY!The first one will win no matter how many stone there are.
First,pick one stone or three so that 4k stone are left.Then the 2nd one pick i stones(i=1,2or3).Just follow him until GAME OVER!
I'm sorry I made a terrible mistake :(

Wacky · 2003-06-24, 10:30

Quote:

Originally Posted by hyh1048576

That's EASY!The first one will win no matter how many stone there are.
First,pick one stone or three so that 4k stone are left.Then the 2nd one pick i stones(i=1,2or3).Just follow him until GAME OVER!

Wrong, -- It's not that easy.

If I understand you correctly, there are 13 stones and you take 1.
That leaves 12. I take 3, leaving 9. (Right, Nick?)

It's your turn.

Matthes · 2003-06-24, 10:48

I think the strategy is to force the other player to pick when there are five stones remaining and have a even number of stones. If he picks three, you pick either one or two (whatever makes you odd). If he picks two, you pick either two or three (whatever makes you odd). If he picks one, you pick three and that should make you odd (that is my weakness in this tactic, but i havent thought it through entirely).

Just a thought, Matthes

hyh1048576 · 2003-06-24, 15:02

I got it!!!!!
Suppose the number of stone is n
Actually I prove that when n=5(mod8),the first one will lose the game.Otherwise the first one will win.
PROVE:(by induction to m)
We prove that: if you have picked 2a(a is integer) stones and there are (8m-3) or 8m stones left or you have picked (2a+1) stones and there are (8m-7) or (8m-4) stones left,you will lose the game,otherwise you will win the game.
When m=1,just verify it.
We use (x,O/E) means "x stones are left and an odd/even number of stones have been picked by you".And W/L means "you will win/lost in this position if it's your turn to pick".Realise that (2b+1,O/E) is L iff (2b,O/E),(2b-1,O/E),(2b-2,O/E) are all W,otherwise it's W.And (2b,O/E) is L iff (2b-1,E/O),(2b-2,E/O),(2b-3,E/O) are all W,otherwise,it's W.We can easily prove "when m=k+1, the proposition is correct" if "when m=k, the proposition is correct".
PS: My English is poor and the signs are messy,but I hope every one understand 8)

Wacky · 2003-06-24, 16:11

Quote:

Originally Posted by hyh1048576

I got it!!!!!
Suppose the number of stone is n
Actually I prove that when n=5(mod8),the first one will lose the game.Otherwise the first one will win.
PROVE:(by induction to m)

Spot on this time.

Nick Glover was actually the first to present a solution shortly after I posted the problem.
He sent his solution privately so as to give others a chance to solve it on their own.

2003-06-24, 00:46	#1
Wacky Jun 2003 The Texas Hill Country 3²·11² Posts	Pick a stone, or two, .... or three Here is a little two person game to play. Start with a small pile of stones in the middle. Make that an odd number of stones, for example, 13. Players alternate turns taking some stones from the pile. They must take either 1, 2, or 3 stones in each turn. After the last stone is taken, the winner is the player that has an odd number of stones. question Can either player force a win? If so, what is the winning strategy? idea What happens if we start with a different (odd) number of stones?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Transporting Large Stone Blocks	a1call	Lounge	6	2017-11-02 18:58
PRP:- Pick A Range	Citrix	Prime Sierpinski Project	2	2014-02-16 18:47
Sieve:- Pick A Range	Citrix	Prime Sierpinski Project	40	2010-09-22 20:12
Help me pick a math course.	jasong	Math	9	2005-03-11 21:04
Pick and Choose	Wacky	Puzzles	5	2003-07-16 20:02

2003-06-24, 09:36	#2
hyh1048576 Jun 2003 2⁶ Posts	That's EASY!The first one will win no matter how many stone there are. First,pick one stone or three so that 4k stone are left.Then the 2nd one pick i stones(i=1,2or3).Just follow him until GAME OVER! I'm sorry I made a terrible mistake :(

2003-06-24, 10:48	#4
Matthes May 2003 2³·3 Posts	I think the strategy is to force the other player to pick when there are five stones remaining and have a even number of stones. If he picks three, you pick either one or two (whatever makes you odd). If he picks two, you pick either two or three (whatever makes you odd). If he picks one, you pick three and that should make you odd (that is my weakness in this tactic, but i havent thought it through entirely). Just a thought, Matthes

2003-06-24, 15:02	#5
hyh1048576 Jun 2003 100₈ Posts	I got it!!!!! Suppose the number of stone is n Actually I prove that when n=5(mod8),the first one will lose the game.Otherwise the first one will win. PROVE:(by induction to m) We prove that: if you have picked 2a(a is integer) stones and there are (8m-3) or 8m stones left or you have picked (2a+1) stones and there are (8m-7) or (8m-4) stones left,you will lose the game,otherwise you will win the game. When m=1,just verify it. We use (x,O/E) means "x stones are left and an odd/even number of stones have been picked by you".And W/L means "you will win/lost in this position if it's your turn to pick".Realise that (2b+1,O/E) is L iff (2b,O/E),(2b-1,O/E),(2b-2,O/E) are all W,otherwise it's W.And (2b,O/E) is L iff (2b-1,E/O),(2b-2,E/O),(2b-3,E/O) are all W,otherwise,it's W.We can easily prove "when m=k+1, the proposition is correct" if "when m=k, the proposition is correct". PS: My English is poor and the signs are messy,but I hope every one understand 8)