I encountered this brainteaser while coding, but it is essentially a math problem:
Sheldon, Leonard, Penny, Rajesh and Howard are in the queue for a "Double Cola" drink vending machine; there are no other people in the queue. The first one in the queue (Sheldon) buys a can, drinks it and doubles! The resulting two Sheldons go to the end of the queue. Then the next in the queue (Leonard) buys a can, drinks it and gets to the end of the queue as two Leonards, and so on.
For example, Penny drinks the third can of cola and the queue will look like this:
Rajesh, Howard, Sheldon, Sheldon, Leonard, Leonard, Penny, PennyWrite a program that will return the name of a man who will drink the n-th cola.Note that in the very beginning the queue looks like that:
Sheldon, Leonard, Penny, Rajesh, Howard
After a long time I managed to come up with a long, contrived solution, although apparently the following works:
For a number $n$, subtract by 4 and then divide by 2, and then repeat as necessary until the number is at or below 5. Then you are done, with 1 = Sheldon, 2 = Leonard, etc.
Can anybody explain how exactly to derive this answer? It is very elegant although I have no clue what process would lead towards it.
Let's call for simplicity the people a,b,c,d and e. Then it is not too hard to see they will come on the following order:
a, b, c, d, e
a,a, b,b, c,c, d,d, e,e (twice each)
a,a,a,a, b,b,b,b, c,c,c,c, d,d,d,d, e,e,e,e (4 times each)
Then 8 times each, etc.
Informal proof: Suppose each time a person gets a cola, he is created as a double person not in the end of line, but rather in a separate row. When the line is over, this row becomes the new line. Then the (k+1)-th row is created by all people in the k-th row "doubling" themselves, at the same order.
Now, suppose you want to find the $n$-th person, and suppose $n$ is in the $k$-th row. When you subtract 4 from n and then divide by 2 you simply move to the same person in the $(k-1)$th row. You do that iteratively until you get to the first row.