Author |
Topic: Josephus Variation (Read 1161 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Josephus Variation
« on: Jan 9th, 2006, 6:25am » |
 Quote  Modify
|
Josephus is sitting in a huge circle of n people. Every man is numbered starting from 1; Josephus gets the number 500501. The executioner starts to count people as follows: 1, 2, 4, 7, 11, … every time skipping one more. The first man counted twice is the only man who survives.
Prove that Josephus survives for infinitely many n.
I don't know if that's the right place, since I don't know the solution.
|
| « Last Edit: Jan 9th, 2006, 6:26am by Barukh » |
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Josephus Variation
« Reply #1 on: Jan 9th, 2006, 6:46am » |
Quote Modify
|
Sounds obvious to me...
if f(n) = the series 1,2,4,7,11,... for n=1,2,3,..., we have f(n+1) = f(n) + n.
With a circle of f(500501+k)+k, Josephus will be counted in the 1st round:
f(1001)=500501
and he will be the first to be counted after it went once around the circle:
f(500501+k+1) = f(500501+k) + 500501+k = (1 round) + 500501
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Josephus Variation
« Reply #2 on: Jan 9th, 2006, 9:55pm » |
Quote Modify
|
So simple! 
Next time, Josephus was assigned the last number n. Is it still true that he will survive for infinitely many n?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print