movie question.

100 people standing in a circle in an order 1 to 100. No. 1 has a sword. He kills the next person (i.e. No. 2) and gives the sword to the next (i.e. No. 3). All people do the same until only 1 survives. Who will survive at the last?

bonus- derive the formula for it


The answer is 73.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

circle = Range [ 100 ] ; While [ Length [ circle ] > 1 , circle = Drop [ RotateLeft [ circle ] , 1 ] ] ; circle { 73 } \text{circle}=\text{Range}[100];\text{While}[\text{Length}[\text{circle}]>1,\text{circle}=\text{Drop}[\text{RotateLeft}[\text{circle}],1]];\text{circle}\Rightarrow \{73\}

The following English description, using Google Translate, translates using to both Hindi and Arabic and then return translation to English.

Make a list of 100 numbers.

Repeat the following process until there is only one number remaining: move the first number to the other end of the list (the person lives) and then remove the first number of the list (the person dies).

Show last number.

how it works

arbaz khan - 2 years, 1 month ago

It models the described process until completion. It is a "computer simulation."

Here are the Hindi and Arabic translations of the process description.

100 नंबरों की सूची बनाएं।

निम्नलिखित प्रक्रिया को तब तक दोहराएं जब तक कि केवल एक संख्या शेष न हो: पहले नंबर को सूची के दूसरे छोर पर ले जाएं (व्यक्ति रहता है) और फिर सूची के पहले नंबर को हटा दें (व्यक्ति मर जाता है)।

अंतिम संख्या दिखाएं।

تقديم قائمة من 100 أرقام.

كرر العملية التالية حتى يتبقى رقم واحد فقط: انقل الرقم الأول إلى الطرف الآخر من القائمة (الشخص الذي يعيش) ثم أزل الرقم الأول من القائمة (يموت الشخص).

إظهار الرقم الأخير

A Former Brilliant Member - 2 years, 1 month ago

Log in to reply

google translate? :)

A Former Brilliant Member - 2 years, 1 month ago

Log in to reply

Yes, Google translate -- the English text translates to both of the other languages and back to English. Therefore, I hope that the Hindi and Arabic translations are close enough to be helpful to someone whose English skills are not fluent.

A Former Brilliant Member - 2 years, 1 month ago

First define pair ( N , S ) { 1 , , 100 } × { 1 , 1 } (N,S) \in \{1,\dots,100\} \times \{1,-1\} , where the first element is the number of the remaining individuals, after each round of slay, and S S indicates the first person in the queue who gets the sword. S = 1 S=1 means the first person in the queue gets the sword and S = 1 S=-1 means the second person in the queue gets the sword.

Also we define the parity of N N as p ( N ) = 1 p(N)=1 if the parity is even and p ( N ) = 1 p(N)=-1 when the parity is odd.

Now we set a rule. Given ( N , S ) ( t ) (N,S)(t) , ( N , S ) ( t + 1 ) (N,S)(t+1) is given by

N ( t + 1 ) = { N ( t ) 2 i f p ( N ( t ) ) = 1 , S ( t ) = 1 N ( t ) 2 i f p ( N ( t ) ) = 1 , S ( t ) = 1 N ( t ) 2 i f p ( N ( t ) ) = 1 , S ( t ) = 1 } N(t+1) = \left\{\begin{array}{lr} \frac{N(t)}{2} & if p(N(t))=1, S(t)=1\\ \lfloor \frac{N(t)}{2} \rfloor & if p(N(t))=-1,S(t)=-1\\ \lceil \frac{N(t)}{2} \rceil & if p(N(t))=-1,S(t)=1\\ \end{array}\right\}

S ( t + 1 ) = S ( t ) × p ( N ( t ) ) S(t+1) = S(t)\times p(N(t))

using the rules and pen and paper, we get the following sequence pairs.

( 100 , 1 ) , ( 50 , 1 ) ( 25 , 1 ) ( 13 , 1 ) ( 6 , 1 ) ( 3 , 1 ) ( 2 , 1 ) ( 1 , 1 ) (100,1),(50,1)(25,1)(13,-1)(6,1)(3,1)(2,-1)(1,-1)

every time we have a 1 1 as the starting point, we map a number x { 1 , 2 , , 100 } x \in \{1,2,\dots,100\} to x + 1 2 \frac{x+1}{2} and when we have a 1 -1 as the starting point, we map x { 1 , 2 , , 100 } x \in \{1,2,\dots,100\} to x 2 \frac{x}{2} . mathematically

x + 1 2 + 1 2 + 1 2 2 + 1 2 + 1 2 2 \frac{\frac{\frac{\frac{\frac{x+1}{2}+1}{2}+1}{2^2}+1}{2}+1}{2^2}

The individual who would survive would have a number x x S.T. when it is passed to the map above, the final result would be 1 1 . So, we set it equal to 1 1 and solve it for x x . the result is x = 73 x=73

This is a version of the Josephus problem (the handing round of the sword is equivalent to skipping one person each time).

Chris Lewis - 2 years, 1 month ago

Log in to reply

cool, I did not know the name

A Former Brilliant Member - 2 years, 1 month ago

can you explain it in easier way

arbaz khan - 2 years, 1 month ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...