很古老的游戏题

manthanein · 发表于 2015-10-12 21:00:46

您需要登录才可以下载或查看，没有账号？欢迎注册

×

将从1到n的正整数依次排列成一个圆。先划去1，然后每中间隔k个，划去相应的正整数，按圆圈依次循环，直到步骤无法继续执行为止。
最终情况如何？
这个问题有无一般结论？

manthanein · 发表于 2015-10-12 21:03:22

补充一下，k+1不是n的约数

manthanein · 发表于 2015-10-12 21:06:15

比如说，n=9，k=1
第一步划去1、3、5、7、9
javascript:;
接着划去2、4、6、8
javascript:;
最终没有正整数剩余

manthanein · 发表于 2015-10-12 21:06:26

比如说，n=9，k=1
第一步划去1、3、5、7、9
javascript:;
接着划去2、4、6、8
javascript:;
最终没有正整数剩余

manthanein · 发表于 2015-10-12 21:16:38

当k+1为n的约数时，步骤只能执行一次
对于n=9，当k=3时，只能删去1、5、9
k=4时，依次删去：1、6、3、9、8，最后剩余7

aimisiyou · 发表于 2015-10-13 01:54:06

约瑟夫数圈问题（n个人围成一圈，从第一位开始按1、2 、3、……m循环报数，凡报1的出圈，求最后一位出圈者原来排在的位置？分析可得到递推关系
$$a_2=2$$
$$a_n=2+(a_{n−1}+m−2)mod(n−1)$$

kastin · 发表于 2015-10-13 09:32:19

manthanein · 发表于 2015-10-13 19:24:09

谢谢诸位。原来有这么广阔的背景。

账号		自动登录	找回密码
密码			欢迎注册

[提问] 很古老的游戏题