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. www.ddhw.com 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.www.ddhw.com 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.www.ddhw.com 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. www.ddhw.com
|
哈哈哈哈 O(∩_∩)O哈哈~ 好久不来了，不小心看了一眼自己主页，发现自动关联了自己以往发过的帖，点进这个看了一眼，笑个半死。。。敢情我当初还发过这么搞笑的东西啊，我自己完全不记得了 
雷达卡
发表于 2005-2-27 12:29:50
收藏
分享
支持
反对
置顶卡
千斤顶
楼主