约瑟夫斯问题
前不久从百度贴吧看到一个有趣的问题——据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被人抓到，于是决定了一个自杀方式——41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。
然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
问题
1. 若有 n 个犹太人，加上约瑟夫和他朋友共有 n + 2 个人玩这个死亡游戏，站到如何位置上，才会是剩下的最后两个呢？进一步，假若游戏规则改为每报数为1和3的要求自杀，然后由下一个重新报数，直到只剩一个人为止。Josephus想让自己是最后一个自杀的，把生存的机会留给朋，那他该如何巧妙安排位置呢？
2. 一般地，如果总共n+2人（包括约瑟夫和他朋友），游戏规则为：报数是从1到k，要求报数不是2和k-1的都自杀，然后从下一个开始报数，直到剩下两个人。那么能生还的位置是哪两个呢？
3. 更一般地，如果总共n+2人（包括约瑟夫和他朋友），游戏规则改为：报数是从1到k，要求报数为b+1到k的都自杀，然后从下一个开始报数，直至剩下b个人（这里的b小于k的正整数）。那么能侥幸生还的位置是哪些？
欢迎大家广开思路。
这个问题应该跟整数环有关。
http://bbs.cnool.net/cthread-104451014.html#117620531 葡萄糖 发表于 2014-4-5 13:52
http://bbs.cnool.net/cthread-104451014.html#117620531
这只是最简单的情况，网上有更好的解法。请仔细看问题。 CSDN上有讨论，记得本论坛5-6年前也有讨论的，现在好像搜不到？
http://bbs.csdn.net/topics/390793174
我写了个Mathematica程序：
list = {0, Range};
While]; len > 2, list = {Mod, 3],Delete, List /@Range, len, 3]]}]; Last
n=39,最后会剩下
{0, {10, 25}}
n=500,即CSDN的数据，最后会剩下
{0,{268, 436}}
搜了下OEIS:
http://oeis.org/A054995 1.每报数为1和3的要求自杀，然后由下一个重新报数，直到只剩一个人为止。
list={0,Range};
While];len>2,list={Mod,3],Delete,List/@Quiet,len,3],Range,3]+1,len,3]}]]]};Print]
{0,{2,5,8,11,14,17,20,23,26,29,32,35,38}}
{1,{5,14,23,32}}
{2,{5,32}}‘
0 表示本列表第一个数字编号的人从1开始数数
1 表示本列表第一个数字编号的人从2开始数数
2 表示本列表第一个数字编号的人从3开始数数 wayne 发表于 2014-5-25 19:33
0 表示本列表第一个数字编号的人从1开始数数
1 表示本列表第一个数字编号的人从2开始数数
2...
用程序解决这类问题是很方便，我本来是想找到笔算的简洁方法的，但是无法找出规律，当然对于最简单的1到3报数，留下报数为1、2的，有简单方法可以笔算出来。但是我还没找到统一的方法。
后来我用matlab编程很快解决这样的问题了，但是还是希望能用普通方法算出答案。
页:
[1]