好多堆石子

好心情 · 发表于 2005-2-27 12:29:50

桌面上有10堆珠子，每堆的数目分别为a1,a2...a10，每次可以从中拿出一个或3个或拿走一堆。拿最后一一手的人获胜，但最后一把只能拿一个或3个(拿三个只能从同堆中拿)，请你分析胜负并说明理由。

fzy · 发表于 2005-3-2 18:09:20

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?

好心情 · 发表于 2005-3-2 10:49:26

一堆的时候，奇数个先取胜，偶数个后取胜
因此两堆的时候，都是奇数则后取胜，至少一堆是偶数则先取胜
三堆的时候，都是奇数或者两奇一偶则先取胜，
两偶一奇则后取胜，三偶则先取胜
四堆的时候，0或3堆奇数则后取胜，1 2或4堆奇数则后取胜
等等，10堆的时候，有0 3 6或9堆奇数则后取胜，否则先取胜。
一般地，当奇数堆个数减偶数堆个数被3除余2时后取胜，否则先取胜
fzy® 的答案我还没有时间仔细看,你先看看我的答案

fzy · 发表于 2005-3-1 18:46:34

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.

fzy · 发表于 2005-2-28 18:08:03

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.

		自动登录	找回密码
密码			立即注册

动态微博

好多堆石子

回复：答案

答案

General Strategy

回复：好多堆石子