###### Waste less time on Facebook — follow Brilliant.
×

Recently, I had thought of something about the Josephus Problem. How can we find the number(s) a survivor must stand at out of $$n$$ people when the executioner kills every $$k th$$ person when $$n$$ and $$k$$ assume very large values? For example, if there are $$4171998$$ people in a circle and every $$417th$$ person is killed, then at what number should the survivor(s) stand? Please give a non-CS solution which is not too long or hard to work out by hand. Thanks very much!

Note by Ishan Dasgupta Samarendra
2 years, 4 months ago

Sort by:

Also It can be solved using Circular Linked List, do you want the solution using it? · 2 years, 4 months ago

Happy belated birthday wishes! · 2 years, 4 months ago

Thanks a lot..!! $$\ddot\smile$$ · 2 years, 4 months ago

Oh I am late! Still Belated Happy B'day!! Good luck for JEE! · 2 years, 4 months ago

@Pranjal Jain Thanks a lot..!! $$\ddot\smile$$ and yeah I am sorry I am just having some problems with my phone.. So couldnt send you the program btw ca you just tell the question once again here... · 2 years, 4 months ago

Its for displaying the smallest triangular number which has more than 500 divisors Triangular Numbers are 1,1+2,1+2+3,1+2+3+4,....

I end up using python then. · 2 years, 4 months ago

Sorry, but what if every 417th person was killed? I've modified the Note so that one example is there in the introduction itself. How would we solve the question in the Note? Would you change 4171998 (base 10) to something in base 417, perform your operation, and then convert it back to base 10 to get $$j(n)$$? Also, would we not have to change the operation since we are working in another base (perhaps 417)? Thanks a lot. · 2 years, 4 months ago

Thanks a lot..!! $$\ddot\smile$$. By the way we are converting the number for decimal(base 10) to binary(base 2). So the rest procedure would be the same. Any further doubt then please ask.. · 2 years, 4 months ago

Comment deleted May 25, 2016

well give me 2-3 days..... I had solved that problem using C++ so will need to look for a non CS way.. as boards going on need some time. · 2 years, 4 months ago

Comment deleted May 25, 2016

Are you in ISC board? · 2 years, 4 months ago

Unfortunately no. CBSE. I was under the ICSE system till Class 4 when I shifted to Delhi. · 2 years, 4 months ago

Why did you say "Unfortunately". I guess CBSE board is better than other boards in India. · 2 years, 4 months ago

I studied till class 3 in an ICSE school in Calcutta (La Martiniere) and when I came to my CBSE school in Delhi in class 4, I didn't have to study for school till class 6! I remember in class 2 in Calcutta, I was learning HCF and LCM, and in class 5 in Delhi, we were being taught how to divide and then check the division by multiplying the quotient with the divisor! Also, from what I've heard, ISC seems to be at a much higher level academically than any other board. · 2 years, 4 months ago

Yeah ,sometimes even I too regret not getting admitted to an ISC or ICSE school . · 2 years, 4 months ago

Happy belated B'day ! Sorry if I am late in wishing you ! · 2 years, 4 months ago

Thanks a lot..!! $$\ddot\smile$$ By the way you have got a pretty sharp observation.. cool...and you aint that late just 5 days.. :P and yeah where had you disappeared suddenly.. u even lost your streak..!! · 2 years, 4 months ago

Haha yes , thanks :)

It seems the day I went away was your B'day ! Too bad on my part :(

Well, I was busy with some other things and btw streak doesn't matter right now , once JEE gets over , I'll extend my streak till the end of time :D · 2 years, 4 months ago

Yeah its alright..!! Well thats the spirit.. · 2 years, 4 months ago

Now that you've mentioned about the streak , make sure that you guys congratulate @Kartik Sharma in a few days since he'll be completing a year long streak :) · 2 years, 4 months ago

@Simran Malik I found a non CS solution on the net.. but just the problem is that it is a bit too lenthy and time consuming ot understand... anyways here is the link · 2 years, 4 months ago

Thanks very much! · 2 years, 4 months ago

You are most welcome.. $$\ddot \smile$$ and yeah All the best for your exam..!! By the way why do you want a mathematical proof when you can solve it easily by a program..?? · 2 years, 4 months ago

It's tomorrow right ? Best of Luck ! · 2 years, 4 months ago

Yeah. Thanks very much and all the very best to you too! · 2 years, 4 months ago

Best of Luck to both of you for tomorrow's exam $$\ddot \smile$$ · 2 years, 4 months ago

Thanks , it's not a Board's exam tomorrow (the next one's on the 27th) , btw I do have a test at my Coaching class . · 2 years, 4 months ago

So are you going to post a question inspired from the Josephus problem ? · 2 years, 4 months ago

I want to, but the problem is that I don't know how to solve it myself. I can't use a program, and Harshvardhan's method did not work out for me here. I really don't know what to do. · 2 years, 4 months ago

That's a good problem. I'll try to figure out a solution and post it as soon as I get some free time.

And I remember @Maryann Vellanikaran posted a similar problem. So, in the meantime, you may be interested in trying it out. Best of Luck.

Thanks.

Kishlaya Jaiswal · 2 years, 4 months ago

Hint: If there are $$2^n$$ people left, who wins? Staff · 2 years, 4 months ago

@Calvin Lin The first person out of the $$2^n$$ people, isn't it? For every 2nd person being killed out of $$n$$ persons, we can simply do this: the winner will be the person standing at $$2k+1$$ where $$n = 2^m + k , k = n - \text{(largest value of }2^m \text{ below n),} \text{ and } 2^m \text{ is the largest value less than } n$$ But what if every 10th or every 15th person is killed? And further on, for every 417th, and so on, how can we solve it manually? · 2 years, 4 months ago