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 k-th 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 L-th 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 n-th 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(n2) arithmetic operations.

Back to list of publications.