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

#### 万精油

• Hero Member
• Posts: 1831
##### 每周一题: 又分巧克力 (7/19/04-7/25/04)
« on: 七月 19, 2004, 12:12:51 am »

１。第一个人第一次不能拿完。
２。从第二次开始，每次所能拿的颗数是从一到两倍于你的对手上一次拿的颗数。

#### 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.

#### 万精油

• Hero Member
• Posts: 1831
##### 每周一题: 又分巧克力 (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答案中的错误在于没有考虑到先前一个人取的数目。

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)必赢

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 »

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 »

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 »

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.