何忠德怎么6年没有长大一点 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>TVChinese - 中文电视

何忠德怎么6年没有长大一点

何忠德怎么6年没有长大一点# TVChinese - 中文电视

l*n2014-01-07 08:01

1 楼

前面的帖子说用fibonacci数列，但是没怎么搞明白
两个玩家，一堆石头，假设多于100块, 两人依次拿，最后拿光者赢，规则是
1. 第一个人不能一次拿光所有的
2. 第一次拿了之后，每人每次最多只能拿对方前一次拿的数目的两倍
求先拿者必胜策略, 如果有的话

v*o2014-01-07 08:01

2 楼

省钱.

d*r2014-01-07 08:01

3 楼

是侏儒症吗?

l*o2014-01-07 08:01

4 楼

不知道是不是想错了, 但觉得和fibonacci没有关系. 这些数目先手必输:
1 2 3 5 8 12 18 27 41 62 93 ...
递推关系是 a_{n+1} = ceil(a_n * 1.5).
其他数目先手必胜, 因为可以拿掉相应的数目让对手面临上面的必输情况.
至于为什么, 我也说不太清楚, 我是从1,2,3往上一个一个推的, 然后归纳出来的. 而
且我也不确定是不是正确.

前面的帖子说用fibonacci数列，但是没怎么搞明白
两个玩家，一堆石头，假设多于100块, 两人依次拿，最后拿光者赢，规则是
1. 第一个人不能一次拿光所有的
2. 第一次拿了之后，每人每次最多只能拿对方前一次拿的数目的两倍
求先拿者必胜策略, 如果有的话

【在 l**n 的大作中提到】

: 前面的帖子说用fibonacci数列，但是没怎么搞明白
: 两个玩家，一堆石头，假设多于100块, 两人依次拿，最后拿光者赢，规则是
: 1. 第一个人不能一次拿光所有的
: 2. 第一次拿了之后，每人每次最多只能拿对方前一次拿的数目的两倍
: 求先拿者必胜策略, 如果有的话

y*j2014-01-07 08:01

5 楼

编剧导演集体健忘症。
等着看乳臭未干的弟弟怎么教比他高一头的大姐姐。

j*y2014-01-07 08:01

6 楼

1 2 3 5 8 先手输没错， 12先手怎么输，先拿一个，必然让对手先面对8的情况
事实是，只要起始石头数n不是fib数列，必有拿法可以让对手面对下一个fib < n

【在 l******o 的大作中提到】

: 不知道是不是想错了, 但觉得和fibonacci没有关系. 这些数目先手必输:
: 1 2 3 5 8 12 18 27 41 62 93 ...
: 递推关系是 a_{n+1} = ceil(a_n * 1.5).
: 其他数目先手必胜, 因为可以拿掉相应的数目让对手面临上面的必输情况.
: 至于为什么, 我也说不太清楚, 我是从1,2,3往上一个一个推的, 然后归纳出来的. 而
: 且我也不确定是不是正确.
:
: 前面的帖子说用fibonacci数列，但是没怎么搞明白
: 两个玩家，一堆石头，假设多于100块, 两人依次拿，最后拿光者赢，规则是
: 1. 第一个人不能一次拿光所有的

l*o2014-01-07 08:01

7 楼

哦, 我确实忽略了一个地方. 看来应该是fibonacci没错.

1 2 3 5 8 先手输没错， 12先手怎么输，先拿一个，必然让对手先面对8的情况
事实是，只要起始石头数n不是fib数列，必有拿法可以让对手面对下一个fib < n

【在 j******y 的大作中提到】

: 1 2 3 5 8 先手输没错， 12先手怎么输，先拿一个，必然让对手先面对8的情况
: 事实是，只要起始石头数n不是fib数列，必有拿法可以让对手面对下一个fib < n

l*o2014-01-07 08:01

8 楼

很好奇, 如果把2倍改成3倍, 结果会是怎么样的?

哦, 我确实忽略了一个地方. 看来应该是fibonacci没错.
1 2 3 5 8 先手输没错， 12先手怎么输，先拿一个，必然让对手先面对8的情况
事实是，只要起始石头数n不是fib数列，必有拿法可以让对手面对下一个fib < n

【在 l******o 的大作中提到】

: 哦, 我确实忽略了一个地方. 看来应该是fibonacci没错.
:
: 1 2 3 5 8 先手输没错， 12先手怎么输，先拿一个，必然让对手先面对8的情况
: 事实是，只要起始石头数n不是fib数列，必有拿法可以让对手面对下一个fib < n

g*y2014-01-07 08:01

9 楼

前几个必输的数:
2,3,4
然后接下来必输的数:
6 = 2+4 2,3,4,6
再接下来：
8 = 2+6 2,3,4,6,8
11= 3+8 2,3,4,6,8,11
15= 4+11 2,3,4,6,8,11,15
21= 6+15 2,3,4,6,8,11,15,21
...
for n>=5:
f(n) = f(n-1) + f(n-4);
有没有一个更general的推广，比如2倍改成n倍。。。

【在 l******o 的大作中提到】

: 很好奇, 如果把2倍改成3倍, 结果会是怎么样的?
:
: 哦, 我确实忽略了一个地方. 看来应该是fibonacci没错.
: 1 2 3 5 8 先手输没错， 12先手怎么输，先拿一个，必然让对手先面对8的情况
: 事实是，只要起始石头数n不是fib数列，必有拿法可以让对手面对下一个fib < n

g*y2014-01-07 08:01

10 楼

我第一次做这个题的时候，也是犯了这个错误。
13是必败的，那按照你的递推式下一个必败的数是，13*1.5+1 = 20，就错了
事实上，21才是必输的数。

<=k+(int)((k-1)/2)块石头时，我方拿x-k块石头便必胜了。于是有序列：

s*l2014-01-07 08:01

11 楼

先mark一下, 等一下再来做题

【在 l**n 的大作中提到】

x*y2014-01-07 08:01

12 楼

Yeah, you are right....all the f(n) for n>2 are losers (1 is not considered
here)....First f(3) f(4) f(5) f(6) are all losers,all the other numbers
less than f(6) are winning and then using mathematical induction, assume for
all n>3, f(n) are all losing positions and other non-fabonacci numbers less than f(n) are winning. For any number k between f(n) and f(n+1) (totally f(n-1)-1 numbers
), if k<=f(n)+f(n-2), diretcly move to f(n) (as f(n)=f(n-1)+f(n-2)>2f(n-2),
the opponent can not take all in

【在 j******y 的大作中提到】

n*h2014-01-07 08:01

13 楼

若倍数限制不是2倍，而是k倍，那么必败数列A为：
A(1)=2，A(2)=3，...，A(k)=k+1，之后有
A(.)=A(i)+A(n), for any i such that i=A(n).
当k=2时，A恰巧为fib series.

【在 g*******y 的大作中提到】

: 前几个必输的数:
: 2,3,4
: 然后接下来必输的数:
: 6 = 2+4 2,3,4,6
: 再接下来：
: 8 = 2+6 2,3,4,6,8
: 11= 3+8 2,3,4,6,8,11
: 15= 4+11 2,3,4,6,8,11,15
: 21= 6+15 2,3,4,6,8,11,15,21
: ...