Author Topic: 每周一题: 又分巧克力 (7/19/04-7/25/04)  (Read 17542 times)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
每周一题: 又分巧克力 (7/19/04-7/25/04)
« on: 七月 19, 2004, 12:12:51 am »
上周的智力游戏,有人觉得没有意思。我觉得相当不错。几乎相当于做数学题。在有
限的条件和限制下,要达到目标,做各种各样的组合。我把这个网址寄给我在外度
暑假的儿子,他居然玩得很投入。每天晚上打电话来都说他现在玩到了第几关,哪
一关比较麻烦等等。考虑到他白天要上夏令营,晚上剩下的有限时间,他可以看电
视或玩别的电子游戏,他却肯花时间在这上面,可见这个游戏是老少咸宜。另一个
与此类似的智力游戏是SOKOBAN。没有玩过的朋友可以去找来玩一下,很有
意思。我记不得网址是什么了(好几年以前的事了)。不过在GOOGLE上找一
下一定能找到。

这几天又有人出分巧克力的题目,看来这巧克力还很吸引人。我们这周再出一个分
巧克力的题目。

本周问题:

桌上有一堆巧克力豆(M&M)。你和对手轮流拿。谁拿到最后一颗算
谁胜。条件是:
1。第一个人第一次不能拿完。
2。从第二次开始,每次所能拿的颗数是从一到两倍于你的对手上一次拿的颗数。
比如你的对手上次拿了4颗,那么你就可以拿1颗到8颗里的任意颗数。

我们的问题是在什么条件下(初始颗数)先拿的人可以肯定赢,他的拿法是什么?

packman

  • Full Member
  • ***
  • Posts: 226
每周一题: 又分巧克力 (7/19/04-7/25/04)
« Reply #1 on: 七月 19, 2004, 12:51:07 pm »
The online computer game is interesting, but takes too much time.
I was a fan of SOKOBAN, too. When my father visited me couple years ago. He was deeply into it as well. During the time of his stay, we finished all 99 (or 100?) levels. He even wrote down all the solutions.
Before I post my solution, Mr.Puzzle, can you post your answer to the ants problem?

Here's my solution of this week's M&M problem:
We have to think "When will I lose?" if I have this many M&Ms to start with. Here are the numbers:
2: I can't take all of them. I can only pick one, and the opponent pick the last one. I lose.
3: If I pick one, the opponent picks 2, and vise versa. I lose.
4: I WIN. I pick one and leave the opponent 3, then see above.
5: I lose. If I pick one, that leave the opponent 4, a winning number. If I pick two, the opponent takes the rest 3.
6,7: I WIN. I leave opponent 5 by picking one or two.
8: I lose. If I pick 3 or more, he takes all. Else, he leaves me 5, a losing number.
9,10,11: I WIN, I can leave him 8.
12: I lose. If I pick 4 or more, he takes all. Else, he leaves me 8, a losing number.
.... and on and on.....

So the losing numbers are: 2, 3, 5, 8, 12, 18, 27, 41, 62, 93, ....
or A<n> = ceiling of A<n-1> * 1.5

Besides these starting numbers, I can win by taking down the numbers to the previous "losing number". Then the opponent will neither be able to take all of the rest to win, nor can he take the number down to another "losing number".

Right, Prof.10K? I will post another M&M problem after I see your answer.
简单==完美

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1830
每周一题: 又分巧克力 (7/19/04-7/25/04)
« Reply #2 on: 七月 19, 2004, 03:36:07 pm »
Your answer is on the right track, but not really correct. I am hoping somebody else will point out your mistake, so that this will not be a two person show.

froid

  • Newbie
  • *
  • Posts: 16
每周一题: 又分巧克力 (7/19/04-7/25/04)
« Reply #3 on: 七月 20, 2004, 04:16:25 am »
packman答案中的错误在于没有考虑到先前一个人取的数目。

比如说,如果开始的数目是12,我先取1颗,则后一个人只能取1或者2颗到达9或10,这样我就一定可以再去2或者1颗将对方逼到8这个losing number上去。所以显然12不是会输的开始局面。

在考虑必输局面时,必须把“前面一手”算作局面的一部分。比如令(>n,m)为“前一手对方拿了超过n颗豆,剩下m颗豆”的局面,而(<=n,m)为“前一手对方拿了少于等于n颗豆,剩下m颗豆”的局面,虽然都剩下了m颗豆,但是这两种局面的“输赢值”是可能完全不同的。比如说得到(>3,8)的局面可以让我一把拿干净,毫无疑问是赢的局面,但是(<=3,8)就是输的局面。所以对每个m,都有一个n,使得(>n,m)是必赢局面而(<=n,m)为必输局面,当然这个n可能为0,这样m颗豆的局面总是必赢局面。

当然还要考虑到“第一次拿”这个特殊的局面,因为从“可以爱拿多少就拿多少”这方面来说,它很象(>n,m),但是从“不许全拿光”这个规矩来讲,它又象(<=n,m),不过如果能把上面的东西弄清楚了,这个特殊局面的问题应该不是太难解决。

下面不考虑“第一次拿”这种情况,所谓局面都是前面已经有人拿过了,“到达”指留给对方的局面。

1) 0为必输局面
2) 1,2必赢(到达1))
3) (<=1,3)是必输局面(不能到达1))
4) (>1,3)必赢(到达1))
5) 4必赢(取走一豆到达3))
6) (<=2,5)必输(不能到达1)或3))
7) (>2,5)必赢(到达1))
8) 6,7必赢(到达6))
9) (<=3,8)必输
10) (>3,8)必赢
这个时候也许会以为(<=4,12),(<=5,17)……会是必输局面,但是看下去就会有意外:
11) 9,10必赢
12) (<=1,11)必输!(因为前面一人只取1颗,使得你无法到达9))
于是后面的推理就变得比较复杂,接下去的几个必输局面是:
(<=1,13),(<=7,15),(<=1,18),(<=2,21)

现在得有一个简单的条件来判断某个具体的局面是否必输局,所以我还是没有完全解决问题。

packman

  • Full Member
  • ***
  • Posts: 226
每周一题: 又分巧克力 (7/19/04-7/25/04)
« Reply #4 on: 七月 20, 2004, 05:38:58 am »
Prof.10K said I was on the right track. 2,3,5,8, boom! ... then I derailed.
The correct "losing" series should be: 2,3,5,8,13,21,34.... the next number is the sum of the previous two.
How to win? OK. e.g. If you leave your opponent at 21, make sure you leave him again at 13 by taking the 14th. But how? Well, you know already how to get the last one if your opponent has 8, right? It is the same strategy to get the 14th if your opponent has 21.... there are "internal losing numbers" between 13 and 21 at 15 (13+2), 16 (13+3) and 18 (13+5).
It is just recursive.

I didn't know what I was thinking earlier. I was stuck at the tip of the horn.
简单==完美

froid

  • Newbie
  • *
  • Posts: 16
每周一题: 又分巧克力 (7/19/04-7/25/04)
« Reply #5 on: 七月 20, 2004, 06:34:52 am »
还是不行。如果对手拿得比较少,你不能保证下次还能留给对方斐波那契序列中的数。而且还可能一下给对方赢了。比方说现在有12颗豆,你拿掉4颗留给我8颗,我就可以一下拿掉8颗取胜。

Quote from: packman
Prof.10K said I was on the right track. 2,3,5,8, boom! ... then I derailed.
The correct "losing" series should be: 2,3,5,8,13,21,34.... the next number is the sum of the previous two.
How to win? OK. e.g. If you leave your opponent at 21, make sure you leave him again at 13 by taking the 14th. But how? Well, you know already how to get the last one if your opponent has 8, right? It is the same strategy to get the 14th if your opponent has 21.... there are "internal losing numbers" between 13 and 21 at 15 (13+2), 16 (13+3) and 18 (13+5).
It is just recursive.

I didn't know what I was thinking earlier. I was stuck at the tip of the horn.

froid

  • Newbie
  • *
  • Posts: 16
每周一题: 又分巧克力 (7/19/04-7/25/04)
« Reply #6 on: 七月 20, 2004, 06:39:40 am »
前面我的推理有点问题,我再想想

froid

  • Newbie
  • *
  • Posts: 16
每周一题: 又分巧克力 (7/19/04-7/25/04)
« Reply #7 on: 七月 20, 2004, 06:42:58 am »
还是有点问题:15和16不可能同时是losing numbers。如果得到16,拿掉一颗就留给对方15了。

我还得从头里一遍思路。

Quote from: packman
Prof.10K said I was on the right track. 2,3,5,8, boom! ... then I derailed.
The correct "losing" series should be: 2,3,5,8,13,21,34.... the next number is the sum of the previous two.
How to win? OK. e.g. If you leave your opponent at 21, make sure you leave him again at 13 by taking the 14th. But how? Well, you know already how to get the last one if your opponent has 8, right? It is the same strategy to get the 14th if your opponent has 21.... there are "internal losing numbers" between 13 and 21 at 15 (13+2), 16 (13+3) and 18 (13+5).
It is just recursive.

I didn't know what I was thinking earlier. I was stuck at the tip of the horn.

froid

  • Newbie
  • *
  • Posts: 16
每周一题: 又分巧克力 (7/19/04-7/25/04)
« Reply #8 on: 七月 20, 2004, 09:06:37 am »
我想通了,这个结论是对的,虽然对赢家的策略的说明有点模糊。

Quote from: packman
Prof.10K said I was on the right track. 2,3,5,8, boom! ... then I derailed.
The correct "losing" series should be: 2,3,5,8,13,21,34.... the next number is the sum of the previous two.
How to win? OK. e.g. If you leave your opponent at 21, make sure you leave him again at 13 by taking the 14th. But how? Well, you know already how to get the last one if your opponent has 8, right? It is the same strategy to get the 14th if your opponent has 21.... there are "internal losing numbers" between 13 and 21 at 15 (13+2), 16 (13+3) and 18 (13+5).
It is just recursive.

I didn't know what I was thinking earlier. I was stuck at the tip of the horn.

packman

  • Full Member
  • ***
  • Posts: 226
每周一题: 又分巧克力 (7/19/04-7/25/04)
« Reply #9 on: 七月 20, 2004, 09:11:01 am »
Yeah, I didn't write clear enough.
Froid, where do you live? Seems you didn't sleep all night.
简单==完美

froid

  • Newbie
  • *
  • Posts: 16
每周一题: 又分巧克力 (7/19/04-7/25/04)
« Reply #10 on: 七月 21, 2004, 07:45:22 am »
我当然睡觉啊,但和你的作息时间不一样,地球村嘛 :lol: 。我在欧洲。

Quote from: packman
Yeah, I didn't write clear enough.
Froid, where do you live? Seems you didn't sleep all night.

方信

  • Newbie
  • *
  • Posts: 15
每周一题: 又分巧克力 (7/19/04-7/25/04)
« Reply #11 on: 七月 25, 2004, 11:49:30 pm »
let f_i indicates the ith Fibonacci number
f_1 = 1,
f_2 = 2,
...
f_i = f_i-1 + f_i-2 where i > 2

it is obvious 1 is a winning number
2 and 3 are losing number for first taker


let n the total number of left overs and n >= 4

decompose n into Fibonacci numbers
n = f_k1 + f_k2 + f_k3 + ... + f_ki
where k1 >= K2 + 2, k2 >= K3 + 2, ... ki >= 1
(proof of the existence and the uniqueness of the decomposition skipped)

Conclusion

as long as n is not a fibonacci number with exception of 1, n is a winning number for the first taker.

The strategy of the first taker is
always take the smallest fibonacci number in the decomposition of the number of left-overs.

The key point of the proof here is that f_k1 > 2* f_k2 and etc....

You can prove that after the first one takes the number, the left over is always bigger than 2* the number the first one taken. Also you can prove that after the second taker takes his turn, the decomposition always contains at least 2 Fibonacci numbers, or the number left over by the second taker will be less than 2* the number he takes when the left overs >= 4.

So it proves that the second taker can never make the number to 0 after he takes his turn.

we can use mathematical induction to prove it, but need to take care of the special case of 1 in the proof though. always troublesome to me.

Prof. 10 K once posted a similar puzzle in Civilwind. It always takes some time to resolve it.