难度：+++
1。有若干堆石子，两人轮流拿，每次从其中一堆中拿一个。拿走的石子可以扔掉，也可以加在后面挨着的一堆上。（如果从第3堆拿一个，拿走的石子可以扔掉，也可以加在第4堆上，即使第4堆当时是空的也可以。如果从最后一堆拿，就只能扔掉了。）拿最后一个的胜。
假设一开始有5堆，每堆一个，先拿有没有必胜策略？有几种？
2。和第1题一样，但是拿走的一个可以加在后面任意一堆上。（如果从第3堆拿一个，一共有7堆，可以加在第4到第7的任意一堆上。）
还是一开始有5堆，每堆一个，先拿有没有必胜策略？有几种？
Both questions: take the one from 1st, 3rd, or 5th pile. |
The strategies for the two problems are different |
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). |
Can only take one from the first pile. |
It helps to spread the game in the 2d plane. Also it is probably easier to solve for the general strategies first. |
Q1. Player 1 should start with 1 stone from either pile 1, pile 3, or pile 5. 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. 2) Player 2 moves 1 stone. Three variations: (0,0,2,1,1) -> (0,0,2,0,2) (0,1,1,0,2) -> (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) Case 2. with 1,1,0,1,1 left. 2 sub-cases. 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. 2) Player 2 moves 1 stone. Three variations: (0,2,0,1,1) -> (0,2,0,0,2) (1,1,0,0,2) -> (0,2,0,0,2) (1,0,1,1,1) -> (0,1,1,1,1) (Case 1) Case 3. with 1,1,1,1,0 left. 2 sub-cases. 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. 2) Player 2 moves 1 stone. Four variations: (1,1,1,0,1) -> (1,1,0,1,1) (Case 2) (1,1,0,2,0) -> (0,2,0,2,0) (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).
Q2. Player can only take 1 stone from the first pile. With (0,1,1,1,1) left, 2 sub-cases: 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). 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). |
Player can only take 1 stone from the 5th pile. With (1,1,1,1,0) left, here are the variations: 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. 2) Player 2 moves 1 stone. 2 sub-cases: a) |
They are (0,2,1,1,1) and (1,1,0,1,2). |
第一题是奇偶性问题。把奇数堆和偶数堆分别加起来，得到两个和。如果有一个是奇数，就拿走一个，让他变成偶数。如果两个都是奇数，就搬一个到下一堆，让两个都变成偶数。如果两个都是偶数，就只能认输了。 对给定的初始条件，奇数堆有3个，偶数堆有两个，应该拿走1，3，或5。 |
第二题可以考虑成二维棋盘上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 ）。 对本题来说，有三种走法： |
| 欢迎光临 珍珠湾ART (http://zzwav.com/) | Powered by Discuz! X3 |