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!

## Comments

Sort by:

TopNewestAlso It can be solved using

Circular Linked List, do you want the solution using it? – Harshvardhan Mehta · 2 years agoLog in to reply

– Raghav Vaidyanathan · 2 years ago

Happy belated birthday wishes!Log in to reply

– Harshvardhan Mehta · 2 years ago

Thanks a lot..!! \(\ddot\smile\)Log in to reply

– Pranjal Jain · 2 years ago

Oh I am late! Still Belated Happy B'day!! Good luck for JEE!Log in to reply

@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... – Harshvardhan Mehta · 2 years ago

Log in to reply

I end up using python then. – Pranjal Jain · 2 years ago

Log in to reply

– Ishan Dasgupta Samarendra · 2 years 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.Log in to reply

decimal(base 10)tobinary(base 2). So the rest procedure would be the same. Any further doubt then please ask.. – Harshvardhan Mehta · 2 years agoLog in to reply

Log in to reply

– Harshvardhan Mehta · 2 years ago

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.Log in to reply

Log in to reply

– Kishlaya Jaiswal · 2 years ago

Are you in ISC board?Log in to reply

– Ishan Dasgupta Samarendra · 2 years ago

Unfortunately no. CBSE. I was under the ICSE system till Class 4 when I shifted to Delhi.Log in to reply

– Kishlaya Jaiswal · 2 years ago

Why did you say "Unfortunately". I guess CBSE board is better than other boards in India.Log in to reply

– Ishan Dasgupta Samarendra · 2 years 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.Log in to reply

– Azhaghu Roopesh M · 2 years ago

Yeah ,sometimes even I too regret not getting admitted to an ISC or ICSE school .Log in to reply

– Azhaghu Roopesh M · 2 years ago

Happy belated B'day ! Sorry if I am late in wishing you !Log in to reply

– Harshvardhan Mehta · 2 years 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..!!Log in to reply

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 – Azhaghu Roopesh M · 2 years ago

Log in to reply

– Harshvardhan Mehta · 2 years ago

Yeah its alright..!! Well thats the spirit..Log in to reply

@Kartik Sharma in a few days since he'll be completing a year long streak :) – Azhaghu Roopesh M · 2 years ago

Now that you've mentioned about the streak , make sure that you guys congratulateLog in to reply

@Simran Malik I found a non

CSsolution 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 – Harshvardhan Mehta · 2 years agoLog in to reply

– Ishan Dasgupta Samarendra · 2 years ago

Thanks very much!Log in to reply

– Harshvardhan Mehta · 2 years 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..??Log in to reply

– Azhaghu Roopesh M · 2 years ago

It's tomorrow right ? Best of Luck !Log in to reply

– Ishan Dasgupta Samarendra · 2 years ago

Yeah. Thanks very much and all the very best to you too!Log in to reply

– Kishlaya Jaiswal · 2 years ago

Best of Luck to both of you for tomorrow's exam \(\ddot \smile\)Log in to reply

– Azhaghu Roopesh M · 2 years 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 .Log in to reply

@Simran Malik

So are you going to post a question inspired from the Josephus problem ? – Azhaghu Roopesh M · 2 years ago

Log in to reply

here. I really don't know what to do. – Ishan Dasgupta Samarendra · 2 years 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 meLog in to reply

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 – Kishlaya Jaiswal · 2 years ago

Log in to reply

Hint:If there are \( 2^n \) people left, who wins? – Calvin Lin Staff · 2 years agoLog in to reply

@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? – Ishan Dasgupta Samarendra · 2 years ago

Log in to reply

@Kishlaya Jaiswal ,@Raghav Vaidyanathan ,@Pranjal Jain ,@Kartik Sharma ,@Krishna Ar ,@Brian Charlesworth sir,@Daniel Liu ,@Agnishom Chattopadhyay ,@Parth Lohomi \(\dots\) – Azhaghu Roopesh M · 2 years ago

Log in to reply