拿石子游戏

fzy

难度：+++　

1。有若干堆石子，两人轮流拿，每次从其中一堆中拿一个。拿走的石子可以扔掉，也可以加在后面挨着的一堆上。（如果从第3堆拿一个，拿走的石子可以扔掉，也可以加在第4堆上，即使第4堆当时是空的也可以。如果从最后一堆拿，就只能扔掉了。）拿最后一个的胜。

假设一开始有5堆，每堆一个，先拿有没有必胜策略？有几种？

2。和第1题一样，但是拿走的一个可以加在后面任意一堆上。（如果从第3堆拿一个，一共有7堆，可以加在第4到第7的任意一堆上。）

还是一开始有5堆，每堆一个，先拿有没有必胜策略？有几种？

www.ddhw.com

 

sean9991

Both questions: take the one from 1st, 3rd, or 5th pile. www.ddhw.com

fzy

The strategies for the two problems are different www.ddhw.com

sean9991

Yes.  The first one try to make (0,0,2,0,2), (0,2,0,2,0) or (0,2,0,0,2).  The second one, besides above, also try to make (1,0,0,1,0) or (0,1,0,0,1). www.ddhw.com

sean9991

Can only take one from the first pile. www.ddhw.com

fzy

It helps to spread the game in the 2d plane. www.ddhw.com   Also it is probably easier to solve for the general strategies first. www.ddhw.com

sean9991

Q1. Player 1 should start with 1 stone from either pile 1, pile 3, or pile 5.www.ddhw.com Case 1. with 0,1,1,1,1 left. There are 2 sub-cases for player 2. 1) Player 2 takes 1 stone.  Then player will take 1 stone and have the remaining stone in the form of either (0,1,0,1,0) or (0,0,1,0,1).  Player 1 wins.www.ddhw.com           2) Player 2 moves 1 stone. Three variations:www.ddhw.com                    (0,0,2,1,1) -> (0,0,2,0,2)                    (0,1,1,0,2) -> (0,0,2,0,2)www.ddhw.com (0,1,0,2,1) -> (0,1,0,1,2) -> (0,1,0,0,3) -> (0,0,1,0,3) Case 2. with 1,1,0,1,1 left.  2 sub-cases.www.ddhw.com 1) Player 2 takes 1 stone.  Then player will take 1 stone and have the remaining stone in the form of either (0,1,0,1,0) or (1,0,0,0,1).  Player 1 wins.www.ddhw.com           2) Player 2 moves 1 stone. Three variations:                    (0,2,0,1,1) -> (0,2,0,0,2)www.ddhw.com                    (1,1,0,0,2) -> (0,2,0,0,2)www.ddhw.com (1,0,1,1,1) -> (0,1,1,1,1) (Case 1) Case 3. with 1,1,1,1,0 left.  2 sub-cases.www.ddhw.com 1) Player 2 takes 1 stone.  Then player will take 1 stone and have the remaining stone in the form of either (1,0,1,0,0) or (0,1,0,1,0).  Player 1 wins.www.ddhw.com           2) Player 2 moves 1 stone. Four variations:                    (1,1,1,0,1) -> (1,1,0,1,1) (Case 2)www.ddhw.com                    (1,1,0,2,0) -> (0,2,0,2,0)www.ddhw.com                    (0,2,1,1,0) -> (0,2,0,2,0) (1,0,2,1,0) -> (1,0,1,2,0) -> (1,0,0,3,0) -> (0,1,0,3,0).  www.ddhw.com Q2. Player can only take 1 stone from the first pile.  With (0,1,1,1,1) left, 2 sub-cases:www.ddhw.com 1)     Player 2 moves 1 stone.  Then player 1 will move 1 stone, resulting either (0,0,2,0,2) or (0,0,0,2,2).www.ddhw.com 2)     Player 2 takes 1 stone. Then player 1 also takes 1 stone, resulting either (0,1,0,1,0) or (0,0,1,0,1). www.ddhw.com

sean9991

Player can only take 1 stone from the 5th pile.  With (1,1,1,1,0) left, here are the variations:www.ddhw.com 1)     Player 2 takes 1 stone.  Then player 1 will move 1 stone and make it either (1,1,0,0,1) or (0,0,1,1,1).  Player 1 wins.www.ddhw.com 2)     Player 2 moves 1 stone.  2 sub-cases:www.ddhw.com a)

fzy

  There are 3 winning moves each for the 2 problems.

sean9991

They are (0,2,1,1,1) and (1,1,0,1,2). www.ddhw.com

fzy

第一题是奇偶性问题。把奇数堆和偶数堆分别加起来，得到两个和。如果有一个是奇数，就拿走一个，让他变成偶数。如果两个都是奇数，就搬一个到下一堆，让两个都变成偶数。如果两个都是偶数，就只能认输了。 对给定的初始条件，奇数堆有3个，偶数堆有两个，应该拿走1，3，或5。 www.ddhw.com

fzy

第二题可以考虑成二维棋盘上5个棋子，在(1,5), (2,4), (3,3), (4,2), (5,1)。目的是把5个棋子走到边上。这样第二题就变成5堆，每堆分别有1，2，3，4，5个棋子的NIM，其解法要用到二进位数（见　http://www.heidisun.com/qqsh/index.php?topic=146.0 ）。 对本题来说，有三种走法： 1。第一个放到第二堆上，形成 (2,1,1,1) 2。第三个放到第四堆上，形成 (1,1,0,2,1) 3。扔掉第五个，形成 (1,1,1,1,0)。 www.ddhw.com