100 pirates

Question:

100 pirates stand in a circle. They start shooting alternately in a cycle such that 1st pirate shoots 2nd, 3rd shoots 4th and so on. They continue in circle till only one pirate is left. Which position should Captain Jack Sparrow stand to survive?

.

.

C

A

P

T

A

I

N

I

N

T

E

R

V

I

E

W

.

.

Solution:

This is not a puzzle at all, this is aptitude/maths question, but has become quite common. You can calculate for a N=100, the 73rd position is safe. For a general N, find largest m such that 2^m < N. Take t = N-2^m. Then the Safe position is 2*t + 1. Please learn this formula. No need to prove it using strong induction.

 

Proof: http://en.wikipedia.org/wiki/Josephus_problem#k.3D2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s