The Feline Josephus Problem
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Aaron Williams,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
In the classic Josephus problem, elements 1, 2, ... ,n
are placed in order around a circle and a skip value k is chosen.
The problem proceeds in n rounds, where each round consists of
traveling around the circle from the current position,
and selecting the kth
remaining element to be eliminated from the circle.
After n rounds, every element is eliminated.
Special attention is given to the last surviving element, denote it by j.
We generalize this popular problem by introducing a uniform number of
lives L, so that elements are not eliminated until they have
been selected for the Lth time.
We prove two main results:
1) When n and k are fixed, then j is constant for
all values of L larger than the nth Fibonacci number.
In other words, the last surviving element stabilizes with respect to increasing the number of lives.
2) When n and j are fixed, then there exists a value of
k that allows j to be the last survivor simultaneously
for all values of L.
In other words, certain skip values ensure that a given position is the
last survivor, regardless of the number of lives.
For the first result we give an algorithm for determining j
(and the entire sequence of selections)
that uses O(n^{2}) arithmetic operations.

Files: pdf.

Fifth International Conference on Fun with Algorithms, Ischia Island, Italy.
Lecture Notes in Computer Science, LNCS 6099, 343354.

Submitted to the conference January 22, 2010.

This paper was one of the ones chosen for submission to the journal
Theory of Computing Systems. Submitted there
September 10, 2010. Appears as 50 (2012) 2034.

Please send me a note if
you download one of these files.
It's always nice to know who's reading your papers.

Here is a table of hit sequences: Table.pdf.

Slides from my talk at the FUN conference:
FUN2010_Josephus_Talk.pdf.

Alejandro Erickson's flash program for the feline Josephus problem:
felinejosephus.swf (press
the start button).

Selected citations:
Back to list of publications.