Snarkpit Forum Index » General Banter » While it's quiet
While it's quiet
1
Post Reply
Quote
 Re: While it's quiet
Posted by flashman on Mon May 17th at 11:19pm 2004

You have been sentenced to death along with, say, another eleven prisoners.The method of execution is as follows:

Each of you are allocated a number and ordered to stand in a circle - in sequence.

Starting at no.1 and moving clockwise, the executioner shoots every other man in turn until only one is left - he is reprieved.

If you could choose your number, what would it be?
What if there were thirty-seven prisoners?
Or ninety-three?

What if there were X no.

A tenner to the Charity designated by the person who posts the briefest correct answer to the last.



Quote
 Re: While it's quiet
Posted by 7dk2h4md720ih on Mon May 17th at 11:23pm 2004

edit: didn't read properly lol [addsig]



Quote
 Re: While it's quiet
Posted by Leperous on Mon May 17th at 11:24pm 2004

x-1 ?



Quote
 Re: While it's quiet
Posted by Kage_Prototype on Mon May 17th at 11:32pm 2004

I think lep got it. [addsig]



Quote
 Re: While it's quiet
Posted by mazemaster on Mon May 17th at 11:35pm 2004

no, he shoots every EVEN person and keeps going around the circle.



Quote
 Re: While it's quiet
Posted by Leperous on Mon May 17th at 11:39pm 2004

Ok, so you want to be x-1'th if there's an odd number of people, and x'th if there are an even number of people.





Quote
 Re: While it's quiet
Posted by 7dk2h4md720ih on Mon May 17th at 11:45pm 2004

x-1 was my first answer so I was half right I guess. [addsig]



Quote
 Re: While it's quiet
Posted by 7dk2h4md720ih on Mon May 17th at 11:47pm 2004

http://www.lepra.org.uk/ Is my charity of choice, so send a fiver! [addsig]



Quote
 Re: While it's quiet
Posted by flashman on Mon May 17th at 11:48pm 2004

No. Sorry. The sequence would run (in the case of 12 people)

1 x 3 x 5 x 7 x 9 x 11 x 2 x 6 x 10 x 4 x 12 - leaving 8
Shoot one-miss one-shoot one-miss one...



Quote
 Re: While it's quiet
Posted by fraggard on Tue May 18th at 3:58am 2004

? posted by flashman
What if there were thirty-seven prisoners?
Or ninety-three?

This is the classic Josephus problem, isn't it? There's a formula I used to use for this one... I think it is:

Survivors position = 1 + 2X - 2^floor(1+lg(X))

lg(X) is to the base 2.

For 37, it's 11. For 93, it's 123. (Edit: Should be 58. I'm stupid)





Quote
 Re: While it's quiet
Posted by flashman on Tue May 18th at 8:41am 2004

? posted by fraggard

Survivors position = 1 + 2X - 2^floor(1+lg(X))

lg(X) is to the base 2.

For 37, it's 11. For 93, it's 123.



The answer is always an even number - All odd numbers are taken out in the first circuit.



Quote
 Re: While it's quiet
Posted by Leperous on Tue May 18th at 9:08am 2004

Ok, so 2n - 2^floor(1+log2(n)) for n>2 then





Quote
 Re: While it's quiet
Posted by fraggard on Tue May 18th at 11:24am 2004

? posted by Leperous

Ok, so 2n - 2^floor(1+log2(n)) for n>2 then

What he said.

And the number for 93 is wrong... It should be 58. (59 by the forumla, 58 for your answer)





Quote
 Re: While it's quiet
Posted by mazemaster on Tue May 18th at 11:56am 2004

Awesome riddle.
1....1


2....2


3....2
4....4


5....2
6....4
7....6
8....8


9....2
10...4
11...6
12...8
13...10
14...12
15...14
16...16


17...2
18...4
[...]
31...30
32...32


33...2
[...]
64...64

65...2
[...]
128..128



Quote
 Re: While it's quiet
Posted by fraggard on Tue May 18th at 3:24pm 2004

I was looking around, and found another solution...

Apparently, if you convert X to binary, and then rotate all the bits left by 1 place, you get the final position to be in.

If X = X1X2X3X4X5...Xn-1Xn In binary, then Rotating it to become X2X3X4...XnX1 gives you the final position. (For this particular case, you have to subtract 1 from that value, I think.)






1
Post Reply