wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Josephus Variation
        
(Message started by: Barukh on Jan 9^th, 2006, 6:25am)

Title: Josephus Variation
Post by Barukh on Jan 9^th, 2006, 6:25am

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.

Title: Re: Josephus Variation
Post by Grimbal on Jan 9^th, 2006, 6:46am

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

Title: Re: Josephus Variation
Post by Barukh on Jan 9^th, 2006, 9:55pm

So simple! :D

Next time, Josephus was assigned the last number n. Is it still true that he will survive for infinitely many n?