桌面上有10堆珠子，每堆的数目分别为a1,a2...a10，每次可以从中拿出一个或3个或拿走一堆。拿最后一一手的人获胜，但最后一把只能拿一个或3个(拿三个只能从同堆中拿)，请你分析胜负并说明理由。
Not 100% sure whether it is correct: Suppose there are K piles among the 10 that have an even number of beads. If it is your turn and K = 0, 4, 6, 8, 10, you lose. Otherwise you win. |
This is an interesting game, quite different from the NIM game, where no restriction exists for the number of beads you can take from one pile. For this game we define a state as the number of piles (N) and how many of the piles have even number of beads (K). A state is a losing state if the current player will lose as long as his opponent does not make a mistake. A state is a winning state if the current player can make a move to produce a losing state. If a state is not a losing state, then it is a winning state. The following is a complete list of losing states. 1. N = 1, K = 1. 2. N = 2, K = 0. 3. N > 1 and is an odd number, K = 2. 4. N > 2 and is even, K = 0, 4, 6, ..., N. So the strategy is to always produce a losing state for your opponent. Here is a proof for the above result. 1. N = 1, K = 1. This means one pile with even number of beads. Obviously you cannot win. 2. N = 2, K = 0. Two piles both odd. Let's call the state (O, O). Then you can produce either (O) or (O, E). And you opponent will give you (E), which is above. 3. Let's consider (O, E, E). Then the possible sequences are a) (O, E, E) -> (E, E) -> (E) b) (O, E, E) -> (O, E) -> (E) c) (O, E, E) -> (O, O, E) -> (O, O) d) (O, E, E) -> (E, E, E) -> (O, E, E) And you always lose. Now we start from the states (O, E, E) and (O, O), and we can prove 3 and 4 using induction. I omitted the proof. If you like, you can fill in youself. |
一堆的时候，奇数个先取胜，偶数个后取胜
|
We are the same up to three. For 4, I have 0或4堆奇数则后取胜，1 2或3堆奇数则先取胜. For 10, I have 有0, 2, 4, 6, 或10堆奇数则后取胜，否则先取胜. I have a proof. Can you give your proof? |
| 欢迎光临 珍珠湾ART (http://zzwav.com/) | Powered by Discuz! X3 |