Name
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 ℓ, so that elements are not eliminated until they have been selected for the ℓth time. We prove two main results: 1) When n and k are fixed, then j is constant for all values of ℓ 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 ℓ. 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. “un gatto ha sette vite” |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s00224-011-9343-6 | Theory of Computing Systems - Special Issue: Fun with Algorithms |
Keywords | DocType | Volume |
kth remaining element,current position,last survivor,n round,Feline Josephus Problem,classic Josephus problem,uniform number,value k,popular problem,problem proceed,josephus problem · fibonacci number · chinese remainder theorem · bertrand's postulate · number theory · algorithm,nth Fibonacci number | Journal | 50 |
Issue | ISSN | ISBN |
1 | 1432-4350 | 3-642-13121-2 |
Citations | PageRank | References |
1 | 0.78 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frank Ruskey | 1 | 906 | 116.61 |
| Aaron Williams | 2 | 139 | 20.42 |