Waste less time on Facebook — follow Brilliant.
×

Please Help!

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, 7 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Also It can be solved using Circular Linked List, do you want the solution using it?

Harshvardhan Mehta - 2 years, 7 months ago

Log in to reply

Happy belated birthday wishes!

Raghav Vaidyanathan - 2 years, 7 months ago

Log in to reply

Thanks a lot..!! \(\ddot\smile\)

Harshvardhan Mehta - 2 years, 7 months ago

Log in to reply

@Harshvardhan Mehta Oh I am late! Still Belated Happy B'day!! Good luck for JEE!

Pranjal Jain - 2 years, 7 months ago

Log in to reply

@Pranjal Jain @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, 7 months ago

Log in to reply

@Harshvardhan Mehta 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.

Pranjal Jain - 2 years, 7 months ago

Log in to reply

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.

Ishan Dasgupta Samarendra - 2 years, 7 months ago

Log in to reply

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..

Harshvardhan Mehta - 2 years, 7 months ago

Log in to reply

Comment deleted May 25, 2016

Log in to reply

@Ishan Dasgupta Samarendra 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.

Harshvardhan Mehta - 2 years, 7 months ago

Log in to reply

Comment deleted May 25, 2016

Log in to reply

@Ishan Dasgupta Samarendra Are you in ISC board?

Kishlaya Jaiswal - 2 years, 7 months ago

Log in to reply

@Kishlaya Jaiswal Unfortunately no. CBSE. I was under the ICSE system till Class 4 when I shifted to Delhi.

Ishan Dasgupta Samarendra - 2 years, 7 months ago

Log in to reply

@Ishan Dasgupta Samarendra Why did you say "Unfortunately". I guess CBSE board is better than other boards in India.

Kishlaya Jaiswal - 2 years, 7 months ago

Log in to reply

@Kishlaya Jaiswal 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.

Ishan Dasgupta Samarendra - 2 years, 7 months ago

Log in to reply

@Ishan Dasgupta Samarendra Yeah ,sometimes even I too regret not getting admitted to an ISC or ICSE school .

Azhaghu Roopesh M - 2 years, 7 months ago

Log in to reply

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

Azhaghu Roopesh M - 2 years, 7 months ago

Log in to reply

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..!!

Harshvardhan Mehta - 2 years, 7 months ago

Log in to reply

@Harshvardhan Mehta 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

Azhaghu Roopesh M - 2 years, 7 months ago

Log in to reply

@Azhaghu Roopesh M Yeah its alright..!! Well thats the spirit..

Harshvardhan Mehta - 2 years, 7 months ago

Log in to reply

@Harshvardhan Mehta 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 :)

Azhaghu Roopesh M - 2 years, 7 months ago

Log in to reply

@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

Harshvardhan Mehta - 2 years, 7 months ago

Log in to reply

Thanks very much!

Ishan Dasgupta Samarendra - 2 years, 7 months ago

Log in to reply

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..??

Harshvardhan Mehta - 2 years, 7 months ago

Log in to reply

It's tomorrow right ? Best of Luck !

Azhaghu Roopesh M - 2 years, 7 months ago

Log in to reply

@Azhaghu Roopesh M Yeah. Thanks very much and all the very best to you too!

Ishan Dasgupta Samarendra - 2 years, 7 months ago

Log in to reply

@Azhaghu Roopesh M Best of Luck to both of you for tomorrow's exam \(\ddot \smile\)

Kishlaya Jaiswal - 2 years, 7 months ago

Log in to reply

@Kishlaya Jaiswal 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 .

Azhaghu Roopesh M - 2 years, 7 months ago

Log in to reply

@Simran Malik

So are you going to post a question inspired from the Josephus problem ?

Azhaghu Roopesh M - 2 years, 7 months ago

Log in to reply

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.

Ishan Dasgupta Samarendra - 2 years, 7 months ago

Log 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, 7 months ago

Log in to reply

Hint: If there are \( 2^n \) people left, who wins?

Calvin Lin Staff - 2 years, 7 months ago

Log 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, 7 months ago

Log in to reply

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...