Read about this in Concrete Mathematics - Knuth some time back... Interesting problem
There are n persons in a circle, numbered 1 to n. Going around the circle, every second person is removed from the circle, starting with person number 2, 4, and so on. Show that the number of the last person remaining in the circle can be obtained by writing n in binary, then moving the leftmost 1 to the right. So for example, with n = 13 persons (1101 in binary), the last person is number 11 (1011 in binary).
Math at :
http://en.wikipedia.org/wiki/Josephus_problem
Solution:
In case of 13,
The order in which people die are
xxx0
xx01 {Since last bit of 13 was 1, hence xx01, otherwise it would have been xx11}
x111 {Since secondlast bit of 13 was 0, hence x111, otherwise it would have been x011}
0011 {Since thirdlast bit ....}
So, you would want to be 1011
So, we can see that the solution for a general n is
in the bit representation of n, add a bit 1 at the end and remove the first bit
So, for 1101 -> 1011
For 10,
order of killing is 2, 4, 6, 8, 10, 3, 7, 1, 9
So left is 5
1010 -> 0101
For 15,
order of killing is 2, 4, 6, 8, 10, 12, 14, 1, 5, 9, 13, 3, 11, 7
1111 -> 1111
For 7,
order of killing is 2, 4, 6, 1, 5, 3
0111 -> 1111?? 0111
For 6,
order of killing is 2, 4, 6, 3, 1
0110 -> 1101?? 0101
So, if the output is >n, we should be making the first bit 0
I suppose.. thats the answer.... :)
Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)
Subscribe to:
Posts (Atom)
Fraction Brainteaser
Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...

-
This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this art...
-
Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tos...
-
Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...
