Actually You have to give attention to the followings: 1) If we assume that every k-th person will die, then every number that is multiple of k will die after 1st trip. 2) specially when k=2 and n is Even, then "we arrive at a situation similar to what we began with, except that there are only half as many people and their numbers have changed".
*So, we can arrive at a decision that your desired "2" comes from "k" when k=2.* regards, Wasif Hossain Student of Computer Science and Engineering Bangladesh University of Engineering and Technology Dhaka, Bangladesh On Sun, Mar 6, 2011 at 11:22 AM, Satyajit Bhadange < [email protected]> wrote: > my question was > from where did 2 come in RHS in eqn. > 2*f(n/2) - 1... > > coefficient of f(n/2) > > > On Mar 6, 7:54 am, Gustavo Pacianotto Gouveia > <[email protected]> wrote: > > In this case, k = J(n) > > > > The recurrence is : > > > > int f(int n){ > > if(n == 1) return 1; > > if(n&1) return 2*f(n/2) +1; // case its odd > > return 2*f(n/2) -1; // case it's even > > > > } > > > > -- > > but the statement J(2n) = 2J(n) is incorrect, since, J(2n) = 2J(n)-1 > > > > sorry if it wasn't the question.. what was your real doubt? > > --- > > grato, > > > > Gustavo Pacianotto Gouveia > > > > Escola Politécnica da Universidade de São Paulo > > <[email protected]> [email protected] > > [email protected] > > [email protected] > > > > 2011/3/5 Satyajit Bhadange <[email protected]> > > > > > > > > > > > > > > > > > hi, > > > > > I am studying Josephus problem > > > the recurrence relation for same is > > > > > J(1) = 1; > > > J(2n) = 2J(n) - 1, for n >= 1 > > > j(2n + 1) = 2J(n) + 1, for n >= 1 > > > > > how J(2n) = 2J(n) > > > > > on R.H.S side how 2 which is called k is derived.. > > > > > its is given in book that (concrete mathematics) > > > > > J(2n) = newnumber(J(n)), > > > where > > > newnumber( k) = > > > 2k-1. > > > > > what is k..? > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "google-codejam" group. > > > To post to this group, send email to [email protected]. > > > To unsubscribe from this group, send email to > > > [email protected]. > > > For more options, visit this group at > > >http://groups.google.com/group/google-code?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "google-codejam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > > -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
