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

http://bbs.emath.ac.cn/thread-5203-1-1.html

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

谢谢诸位。原来有这么广阔的背景。
页: [1]
查看完整版本: 很古老的游戏题