Variants of the Josephus Problem.
Variants of the Josephus Problem.
Daisuke Minematsu (Osaka University, Osaka Japan), Hiroshi Matsui ( Kwanseigakuin High School, Nishinomiya City Japan), Toshiyuki Yamauchi (Kwanseigakuin High School), Soh Tatsumi (Kwanseigakuin High School), Masakazu Naito (Kwanseigakuin High School) and Takafumi Inoue (Kwanseigakuin High School).
Initialization Code
Section 1. Introduction and the traditional Josephus Problem.
Section 1. Introduction and the traditional Josephus Problem.
According to legend, Josephus was the leader of a group of Jewish rebels who were trapped by the Romans.His subordinates preferred suicide to surrender, so they decided to form a circle and eliminate every other member until no one was left.Josephus wanted to live, so he calculated where to stand and managed to be the last member.If there were n numbers, where did Josephus stand? We denote by J (n) the position of the survivor.
The Josephus function J(n) has the following recursive relations.
J (2 m) = 2 J (m) - 1
J (2 m + 1) = 2 J (m) + 1
These are well known recursive relation.
J (2 m) = 2 J (m) - 1
J (2 m + 1) = 2 J (m) + 1
These are well known recursive relation.
Section 2. A Josephus problem with an intersection.
Section 2. A Josephus problem with an intersection.
In this variant of the Josephus Problem two numbers are to be eliminated at the same time, but two processes of elimination go for different directions. Let n and k be natural numbers. Suppose that there are n-numbers.Then the first process of elimination starts with the 1 st number and the k-th, 2k-th, 3k-th number, ... are to be eliminated.The second process starts with the n - th number, and the (n − k+1) - th, (n − 2k+1) - th, (n-3k+1)th number, ... are to be eliminated.We suppose that the first process comes first and the second process second at every stage. We denote the position of the survivor by JI (n,k).
Example. This is a Mathematica function to calculate JI (n,k). It is based on a very simple algorithm. You can calculate JI (n,k) by JI[n,k].
JI[m_,mm_]:=Block[{t,p,q,u,v,w,pp},If[m>1,w=mm-1;t=Range[m];p=t;q=t;Do[p=RotateLeft[p,w];u=First[p];p=Rest[p];q=Drop[q,Position[q,u][[1]]];If[Length[p]1,Break[],];q=RotateRight[q,w];v=Last[q];q=Drop[q,-1];p=Drop[p,Position[p,v][[1]]];If[Length[q]1,Break[],],{n,1,Ceiling[m/2]}];pp=p[[1]],pp=1];pp];
Example. Here we can show how to use JI (n,k).
JI[256,2]
214
By the above calcualtion we know the following fact.
If we put 256 person in a circle and we eliminate every 2nd person in the Josephus Problem with an intersection, then the 214th person will be the survivor.
If we put 256 person in a circle and we eliminate every 2nd person in the Josephus Problem with an intersection, then the 214th person will be the survivor.
Example. This is a Mathematica Demonstration to show how to eliminate numbers in the Josephus problems with intersection. Note that the number of steps should not be bigger than the number of numbers.
If you choose "demo", you can see how to eliminate numbers.
If you choose "graph", you can see the graphs of these variants.
The horizontal coordinate is for the number of number involved in the game, and the vertical coordinate is for the position of the last number remains. For example by JI(256,2) = 214 we have the point (256, 214) in the graph for k = 2.
If you choose "demo", you can see how to eliminate numbers.
If you choose "graph", you can see the graphs of these variants.
The horizontal coordinate is for the number of number involved in the game, and the vertical coordinate is for the position of the last number remains. For example by JI(256,2) = 214 we have the point (256, 214) in the graph for k = 2.
Remark. If the following Demonstration does not work properly, please activate Initialization Codes at the beginning of this article.
Manipulate[If[hh>nn,hh=nn];Which[se20,pic2[nn,Table[d1[nn,mm-1][[s]],{s,1,proc[nn][[hh,1]]}],Table[d2[nn,mm-1][[u]],{u,1,proc[nn][[hh,2]]}]],se1000,ListPlot[gg[[mm-1]],PlotRange{{0,500},{0,500}},ImageSize{350,350}]],{{se,20,""},{20"demo",1000"graph"},ImageSizeTiny},{{nn,8,"number of players n"},2,20,1,Enabledse===20,Appearance"Labeled",ImageSizeTiny},{{hh,4,"steps (half-stages)"},1,nn,1,Enabledse===20,Appearance"Labeled",ImageSizeTiny},{{mm,2,"k th"},2,9,1,Enabledse===20,Appearance"Labeled",ImageSizeTiny},ControlPlacementLeft]
Example. This is the codes of the AVA applet to show how we eliminate numbers in the Josephus problems with intersection.
Remark. JI (n,k) has an interesting recursive relation when k = 2. We denot JI(n,k) by JI(n).
Theorem A. The recursive relations for JI(n).
(1) JI[8 n] = 4 JI[2 n] - 1 - Floor[ JI[2 n]/(n + 1) ]
(2) JI[8 n + 1] = 8 n + 5 - 4 JI[2 n]
(3) JI[8 n + 2] = 4 JI[2 n] - 3 - Floor[JI[2 n]/(n + 2) ]
(4) JI[8 n + 3] = 8 n + 7 - 4 JI[2 n].
(5) JI[8 n + 4] = 8 n + 8 - 4 JI[2 n + 1] + Floor[JI[2 n + 1]/(n + 2) ]
(6) JI[8 n + 5] = 4 JI[2 n + 1] - 1.
(7) JI[8 n + 6] = 8 n + 10 - 4 JI[2 n + 1] + Floor[JI[2 n + 1]/(n + 2) ]
(8) JI[8 n + 7] = 4 JI[2 n + 1] - 3.
(2) JI[8 n + 1] = 8 n + 5 - 4 JI[2 n]
(3) JI[8 n + 2] = 4 JI[2 n] - 3 - Floor[JI[2 n]/(n + 2) ]
(4) JI[8 n + 3] = 8 n + 7 - 4 JI[2 n].
(5) JI[8 n + 4] = 8 n + 8 - 4 JI[2 n + 1] + Floor[JI[2 n + 1]/(n + 2) ]
(6) JI[8 n + 5] = 4 JI[2 n + 1] - 1.
(7) JI[8 n + 6] = 8 n + 10 - 4 JI[2 n + 1] + Floor[JI[2 n + 1]/(n + 2) ]
(8) JI[8 n + 7] = 4 JI[2 n + 1] - 3.
Example. A Mathematica JIR[n] function to calculate JI(n) that is based on the recursive relations in Theorem A.
JIR[1]=1;JIR[2]=1;JIR[3]=3;JIR[4]=4;JIR[m_]:=JIR[m]=Block[{n,h},h=Mod[m,8];n=(m-h)/8;Which[h0,4JIR[2n]-1-Floor[JIR[2n]/(n+1)],h1,8n+5-4JIR[2n],h2,4JIR[2n]-3-Floor[JIR[2n]/(n+2)],h3,8n+7-4JIR[2n],h4,8n+8-4JIR[2n+1]+Floor[JIR[2n+1]/(n+2)],h5,4JIR[2n+1]-1,h6,8n+10-4JIR[2n+1]+Floor[JIR[2n+1]/(n+2)],h7,4JIR[2n+1]-3]]
Mathematica calculation to prove Theorem A. Here we are going to compare two Mathematica functions JIR[n] and JI[n,k]. By using the above two Mathematica functions we can get the following result. It took me 90 seconds to calculate aa.When we know that two list {JI[m,2], m = 1,2,...500} and {JIR[m], m = 1,2,...500} are identical, we can be sure that the recursive relations in the above theorem is correct.
We have the following conjecture for the function JI (m).
Example. The function JI(m) has the following remarkable property. As to the concrete data of the conjecture, see the following calculation by Mathematica function JIR[n].
Mod[2,JI(m)]={
0 | ifmisevenand 2n 2 2n+1 2 |
1 | otherwise |
Table[Mod[JIR[n],2],{n,1,256}]
{1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0}
Example. We calculated JI(n) using C++ program, and we found out that Conjecture is correct for n = 1,2,...100000. The following is the C++ codes for the calculation.
#include <iostream>
#include <vector>
using namespace std;
int naitoucheck(int player);
int main(void) {
int interbal=1, player=2, endplayer=1000000, times;
vector<bool> players;
while(player <= endplayer) {
players.assign(player,true);
times=0;
int right=player-1, left=0, counter=0;
while(times < player-1) {
if(times%2==0) {
if(left > player-1) left=0;
if(players[left]==true) counter++;
if(counter <= interbal) {left++; continue;}
players[left] = false; counter=0; left++;
} else {
if(right < 0) right=player-1;
if(players[right]==true) counter++;
if(counter <= interbal) {right--; continue;}
players[right] = false; counter=0; right--;
}
times++;
}
int i;
for(i=0; i<player; i++) {
if(players[i]==true) {
break;
}
}
cout << "\r" << player << "-th checking now.";
if((i+1)%2!=naitoucheck(player)) cout << "\r" << player <<
" in the ...th trial we got an exception." << endl;
player++;
}
cout << "\n Finish Confirm." << endl;
return 0;
}
int naitoucheck(int player) {
if(player%2==1) return 1;
int sikii=4;
for(int i=2; i<32; i++) {
if(i%2==0 && player<sikii) {return 1;}
if(i%2==1 && player<sikii) {return 0;}
sikii=sikii*2;
}
return 1;
}
#include <vector>
using namespace std;
int naitoucheck(int player);
int main(void) {
int interbal=1, player=2, endplayer=1000000, times;
vector<bool> players;
while(player <= endplayer) {
players.assign(player,true);
times=0;
int right=player-1, left=0, counter=0;
while(times < player-1) {
if(times%2==0) {
if(left > player-1) left=0;
if(players[left]==true) counter++;
if(counter <= interbal) {left++; continue;}
players[left] = false; counter=0; left++;
} else {
if(right < 0) right=player-1;
if(players[right]==true) counter++;
if(counter <= interbal) {right--; continue;}
players[right] = false; counter=0; right--;
}
times++;
}
int i;
for(i=0; i<player; i++) {
if(players[i]==true) {
break;
}
}
cout << "\r" << player << "-th checking now.";
if((i+1)%2!=naitoucheck(player)) cout << "\r" << player <<
" in the ...th trial we got an exception." << endl;
player++;
}
cout << "\n Finish Confirm." << endl;
return 0;
}
int naitoucheck(int player) {
if(player%2==1) return 1;
int sikii=4;
for(int i=2; i<32; i++) {
if(i%2==0 && player<sikii) {return 1;}
if(i%2==1 && player<sikii) {return 0;}
sikii=sikii*2;
}
return 1;
}
Section 3. Linear Josephus Problems with an intersection.
Section 3. Linear Josephus Problems with an intersection.
This is another variant of the Josephus problem.Let n and k be natural numbers. We put n numbers on a line.Two numbers are to be eliminated at the same time, but two processes of elimination go for different directions.Then the first process of elimination starts with the 1 st number and the k nd, 2k th number, ... are to be eliminated.The second process starts with the n - th number, and the (n − k+1) - th, (n − 2k+1) - th number, ... are to be eliminated.We suppose that the first process comes first and the second process second at every stage.We change the direction when we reach the end of the line.Then we begin removing every second number again.We denote the position of the last number that remains by JLI(n,k).
Example. This is a Mathematica function to calculate JLI(n,k). It is based on a very simple algorithm. You can calculate JLI(n,k) by JLI[n,k].
JLI[n_,mm_]:=Block[{p,q,u,pp,rs},rs=mm-1;If[n>1,p=Join[Range[n],Sort[Table[m,{m,2,n-1}],Greater]];q=Reverse[Join[Reverse[Range[n]],Table[k,{k,2,n-1}]]];Do[Do[u1=First[p];u2=First[RotateLeft[p,1]];If[u1u2,p=RotateLeft[p,2],p=RotateLeft[p,1]],{s,1,rs}];u=First[p];p=Rest[p];If[MemberQ[p,u],p=Delete[p,Position[p,u]],];If[MemberQ[q,u],q=Delete[q,Position[q,u]],];If[Length[Union[p]]1,Break[],];Do[u1=Last[q];u2=Last[RotateRight[q,1]];If[u1u2,q=RotateRight[q,2],q=RotateRight[q,1]],{s,1,rs}];u=Last[q];q=Drop[q,-1];If[MemberQ[q,u],q=Delete[q,Position[q,u]],];If[MemberQ[p,u],p=Delete[p,Position[p,u]],];If[Length[Union[q]]1,Break[],],{t,1,Ceiling[n/2]}];pp=p[[1]],pp=1];pp];
Remark. If the following Demonstration does not work properly, please activate Initialization Codes at the beginning of this article.
Example. This is a Mathematica Demonstration to show how to eliminate numbers in the Linear Josephus problems with intersection
Manipulate[gr2[nn,Table[d12[nn,rs][[s]],{s,1,proc[nn][[hh+1,1]]}],Table[d22[nn,rs][[u]],{u,1,proc[nn][[hh+1,2]]}]],{{rs,1," th player"},1,nn,1,ImageSizeTiny},{{nn,8,"number of players"},2,20,2,ImageSizeTiny},{{hh,0,"number of steps"},0,nn-1,1,ImageSizeTiny},SaveDefinitionsTrue]
Theorem B. The recursive relations for JLI(n) = JLI(n,2).
(1) JLI(8n) = 8n+2-4JLI(2n)+ Floor[ JLI(2n)/(n+1) ].
(2) JLI(8n+1) = 8n+5-4JLI(2n+1).
(3) JLI(8n+2) = 4JLI(2n+1)-3- Floor[ JLI(2n+1)/(n+2) ].
(4) JLI(8n+3) = 8n+7-4JLI(2n+1).
(5) JLI(8n+4) =8n+8-4JLI(2n+2)+ Floor[ JLI(2n+2)/(n+2) ].
(6) JLI(8n+5) = 8n+7-4JLI(2n+1).
(7) JLI(8n+6) = 8n+10-4JLI(2n+2)+ Floor[ (JLI(2n+2)/(n+2)].
(8) JLI(8n+7) = 4JLI(2n+2)-3.
(2) JLI(8n+1) = 8n+5-4JLI(2n+1).
(3) JLI(8n+2) = 4JLI(2n+1)-3- Floor[ JLI(2n+1)/(n+2) ].
(4) JLI(8n+3) = 8n+7-4JLI(2n+1).
(5) JLI(8n+4) =8n+8-4JLI(2n+2)+ Floor[ JLI(2n+2)/(n+2) ].
(6) JLI(8n+5) = 8n+7-4JLI(2n+1).
(7) JLI(8n+6) = 8n+10-4JLI(2n+2)+ Floor[ (JLI(2n+2)/(n+2)].
(8) JLI(8n+7) = 4JLI(2n+2)-3.
Example. This is a Mathematica function JLIR[n] for JLI(n) = JLI(n,2) based on the recursive relations in above theorem. Note that the expression of this function is very similar to that of equations in Theorem B.
Acknowledgement. We would like to thank Mr. Harrison Gray and Dr. Ryohei Miyadera for helping us to prepare this article. Mr. Gray checked our English and Dr. Miyadera helped us when we used Mathematica in this article.