There are 2910 people each numbered from 1 to 2910 and sitting around a round table in clock-wise fashion.?

Question

There are 2910 people each numbered from 1 to 2910 and sitting around a round table in clock-wise fashion.

(a) 29 people are selected randomly, what's the probability that no two of the persons selected are consecutive i.e. |num(i) -num(j)|=>2 where (i !=j) and i and j are among the 29 guys selected and num(i) is the number of the seat where (i) is sitting.

(b) while all were pondering over the part (a), suddenly the guy numbered 1 took his hidden pistol and shoot the guy next to him in anti clock wise fashion i.e. 2910 and gave the pistol to 2909. in turn

2909 shoots 2908 and this way this anti-clockwise killing goes on till the last guy remains alive.

1. Who is that last guy who survived?

2. Provide a detailed method clarifying each step and justifying any

assumption you took!

3. can you write a pseudo code or a real code which will take the

number (N) the number of ppl sitting around the round table as input argument and output the (S) the identification number of the guy who survived with the anti-clock-wise alternate killing.

4. It would be nice if you can have the robust test cases to test out

your code.

5. Plz clarify the Time complexity and the space complexity of your

code/algorithm used therein.

Answer 1

a) After selecting the first person, there are only 2910 - 3 = 2907 seats left to choose from, and so on. Therefore, the number of valid possibilities seems to be
... 2910 x 2907 x 2904 x ... x 2826,
out of the total number
... 2910 x 2909 x 2908 x ... x 2882.

Dividing these two gives
... P = 2910/2910 x 2907/2909 x 2904/2908 x ... x 2826/2882,
and my computer wants me to believe that this is 75.35%.

b) Let N be the number of participants, and 2^p be the smallest power of 2 greater than or equal to N. Then the number of the survivor is
... S = 2^p + 1 - N.

In this case, N = 2910 and p = 12, so that 2^p = 4096, and
... S = 4096 + 1 - 2910 = 2187.

Proof: when you get the gun, you'd better hope that the number of people alive is even. Otherwise, the next time the gun gets around you will be shot. However, if the number is even, the gun is back at you, and the number of survivors is halved; it should still be even.

The conclusion is that the ultimate survivor is the person who gets the gun every time the number of survivors is a power of 2.

Let 2^q be the smallest power less than or equal to the original number of people, N. The ultimate survivor gets the gun when there are only 2^q people left; therefore, N - 2^q people must have been killed already.

After the first killing, the gun was with person number N - 1; after the second killing, with person N - 3; generally, after the k-th killing, the gun was with person N + 1 - 2k.

Therefore, the survivor, who gets the gun after the (N - 2^q)-th killing, has position
... S = N + 1 - 2(N - 2^q) = 1 - N + 2*(2^q)
and defining p = 1+q,
... S = 2^p + 1 - N.

Answer 2

(a) The number of ways of selecting k objects, no two consecutive, from n objects arrayed in a line is C(n-k+1, k). The number of ways of selecting k objects from n without restriction is C(n,k). So the probability that no two will be consecutive is C(n-k+1, k) / C(n,k). For n = 2910, k = 29, the probability is 0.7544597291.
(b) Look up "Josephus Problem" on Wikipedia.

Answer 3

Well. I had to travel through time anti-clockwise to the year 2010 to get this answer. Circumbulation of The Kaaba 'Tawaf' or cicumbulation (the ritual encircling of the Kaaba) starts from the Hajar Aswad - the Black Stone. The circumambulator, if possible, may kiss the stone or may direct his hand towards it saying, "In the name of Allah, Allah is great." He must circle the Kaaba seven times with the Kaaba to his left (in anti-clockwise direction). On examination, it will be found that the entire universe which is in constant circular or elliptical rotation, is in actual fact moving in the pattern as the Tawaf. The electrons of an atom revolve around its nucleus in the same manner as making Tawaf, in an anti-clockwise direction. The ovum, prior to fertilisation actually taking place, surrounded by sperms, turns remarkably in anti-clockwise direction, thereby resembling the Tawaf. Considering the globe as a whole, it could be found that the earth has two movements. It rotates on its own axis in 24 hours causing day and night. The various seasons of the year are due to the earth's simultaneous revolution around the sun in 365 days. It is really astonishing to note that the earth, in both these movements, rotates anti-clockwise. The entire universe from the atom to the galaxies is in constant circular rotation like a circumambulator who encircles the Kaaba in the anti-clockwise direction. All objects in the universe, atoms, moon, stars, electrical current, galaxies, etc. are rotating in the same way. Moreover, the angles encircle the heavenly Baitul Ma'mur in an ever-lasting Tawaf. In the same way, the Kaaba in Makkah is never free from circumbulators. "Know that the world has come to an end when no soul will circlembulate the holy Kaaba."

Answer 4

(a) no idea
(b)1. the last person to suvive is 2907th guy of the lot
2. hey all i did was make a circle numbere it 1 to 9 clockwise and did as u asked in para (b)
3.can't
4. can't (since its piure hypithesis with the probability of being 2909% wrong)
5.can't (how come time and space got involved? i thought it was just one big murdering round table conference

Answer 5

I'm using a script and I'm getting 1187 for part b. That's the seating number of the last guy alive.

dutchprof's answer should also be 1187, but he wrote 2187 by mistake. His formula is correct.

Answer 6

Interesting question!!!!! beyond my level, but i tried a few smaller samples to see if i can see a pattern on who is the last guy who survives.
It turns out the guy before last will give the gun to his killer!!!hmmmm
will you give the gun to someone who will kill you?
that is funny.