约瑟夫斯问题

kastin

前不久从百度贴吧看到一个有趣的问题——
据说著名犹太历史学家 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

kastin

葡萄糖 发表于 2014-4-5 13:52
http://bbs.cnool.net/cthread-104451014.html#117620531

这只是最简单的情况，网上有更好的解法。请仔细看问题。

wayne

CSDN上有讨论，记得本论坛5-6年前也有讨论的，现在好像搜不到？
http://bbs.csdn.net/topics/390793174

我写了个Mathematica程序：

1. list = {0, Range[39]};
   
2. While[len = Length[Last[list]]; len > 2, list = {Mod[len + First[list], 3],  Delete[Last[list], List /@Range[3 - First[list], len, 3]]}]; Last[list]

复制代码

n=39,最后会剩下

1. {0, {10, 25}}

复制代码

n=500,即CSDN的数据，最后会剩下

1. {0,{268, 436}}

复制代码

搜了下OEIS:
http://oeis.org/A054995

wayne

1.每报数为1和3的要求自杀，然后由下一个重新报数，直到只剩一个人为止。

1. list={0,Range[39]};
   
2. While[len=Length[Last[list]];len>2,list={Mod[len+First[list],3],Delete[Last[list],List/@Quiet[Flatten[{Range[3-First[list],len,3],Range[Mod[3-First[list],3]+1,len,3]}]]]};Print[list]]

复制代码

{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开始数数

kastin

wayne 发表于 2014-5-25 19:33
0 表示本列表第一个数字编号的人从1开始数数
1 表示本列表第一个数字编号的人从2开始数数
2  ...

用程序解决这类问题是很方便，我本来是想找到笔算的简洁方法的，但是无法找出规律，当然对于最简单的1到3报数，留下报数为1、2的，有简单方法可以笔算出来。但是我还没找到统一的方法。

后来我用matlab编程很快解决这样的问题了，但是还是希望能用普通方法算出答案。