情趣生活
情趣生活 => 灵机一动 => Topic started by: packman on 七月 20, 2004, 09:25:41 am

OK, here's another M&M problem. It's more like a betting game at the corner of the street while the dealer lures the people to play and lose money, if they don't know how to win. If you know the trick, you can become a dealer too, and win some money during the coffee break at work... I will post the answer this Friday.
这回，谁拿最后一颗M&M谁输。
有三种颜色的M&M：红的三颗，黄的五颗，蓝的七颗。两人轮流拿。每次只能pick同一种颜色的，但可以和上次pick的颜色不同，数目不限。
谁拿最后一颗M&M谁输。No matter what color. 我告诉你先拿的肯定赢。问：该怎么赢？

This is the classic of all Nim like problem. In fact, I think this is the earliest version. All the other variations are derived from this version.
For this particular problem, (3,5,7) is just interesting enough to put on a coffee table, and easy enough to do it in mind. If there are more M&M's on the table, figuring out all the b***** pattern in head can be quite hard, I tried it for bigger number once (with my son), and got mixed up two steps into the game.
Anyway, this is a good puzzle, I hope other people like it.
I used ***** in the above paragraph so that it will not spoil other people's fun of solving this puzzle.

先拿掉一颗黄的，剩下红3黄4蓝7。
如果对方拿不多于3颗的蓝或红，则拿同样颗数的红或蓝，静观其变。
直到，如果对方拿过后你可以一举拿成任何的123或111或XX0组合，就赢了。

123, 111 and xxo are the final winning combinations. But how do you get there?
What I am asking are the intermediate winning combinations, all of them.

The winning combinations are:(doesn't matter what color)
0xx
111
123
145
246
357
........
You can add more numbers to the previous winning combo to make a new one, but it is harder and harder, as Prof.10K pointed out earlier.

From your answer I can see that you do not know the general answer to this question. Given starting point (a,b,c), what is the general winning strategy. e.g. if the start condition is (100,200,300), what do you do? When I said it is hard, I meant it is hard to do it in head, but it is not hard to do it on a piece of paper or by a computer program.
BTW, 357 is not a winning combination (if 111 is).

Sorry, I posted wrong. Should be like this:
To ensure winning, you have to leave your opponent to one of these combinations:
0xx
111
123
145
246
So, 357 is what I want to start with.
I never thought of more than that. Prof.10k, please give us a lecture.

Sorry, I posted wrong. Should be like this:
To ensure winning, you have to leave your opponent to one of these combinations:
0xx
111
123
145
246
So, 357 is what I want to start with.
I never thought of more than that. Prof.10k, please give us a lecture.

这个网页
http://web.usna.navy.mil/~wdj/book/node10.html
在古狗上找"Nim sum"可以找到一大堆。
另外“拿最后一颗胜”和“拿最后一颗输”的策略只在最后几步有区别。

That's a great link, it explain the Nim Sum better than I can (at least more detailed than I would). This saves me some explaination. Thanks.
Now, I can reveal that the b***** in my previous post in this thread means binary.