Friday, October 7, 2011

World Quant

First puzzle was asked in the World Quant's test last year. I will post more from that test tomorrow.

1. Let a and b are two real numbers. What is the probability that leading digit of a/b is 1. Leading digit in 0.001980 is 1.

Random Puzzle:

2. There are hundred prisoners and everybody is locked in a different cell. There is a room with a switch which can be either on or off. Initially, the switch is on. Jailer randomly takes one prisoner at a time into the room and ask the following question: "Has everybody been here at least once?"

You can see the state of the switch and decide. If you say yes and all other 99 prisoners have been in the room at least once, you all are saved. But, if not all have been in that room, all die. If your answer is no, then he will give you a chance to toggle the switch. You might toggle or you might not. Then, he locks you to your room. He again takes one random prisoner and do the same.

What should be the strategy of the prisoners such that probability that everybody is eventually saved is 1?

Clarification: Jailer takes a "random" prisoner among 100 prisoner. Same prisoner might be picked twice.
Posted by at

17 comments:

  1. NAOctober 8, 2011 at 4:41 PM

    There cannot be a more comprehensive description of the problem

    www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf

    ReplyDelete
    Replies
    1. PabloNovember 26, 2015 at 4:16 PM

      Is not there a crucial difference. The riddle as presented by William of UCB says one prisoner each day. So if the same prisoner is bought repeatedly, in each case he is aware of how many prisoners have passed between these two visits. In the problem presented here, that information is not available.

      I am not sure whether this makes a difference though.

      Delete
  2. vivek madanOctober 8, 2011 at 5:53 PM

    Thanks!! I guess it describes all aspects of the protocol very beautifully.

    ReplyDelete
  3. SaurabhOctober 10, 2011 at 10:09 AM

    Possible approach to 1st puzzle-
    consider the scientific notation of real numbers. Now, calculate the probability for at most n digits (with first digit from left is always non-zero). calculate the no. of possible cases and divide it by (81x10^(2n-2), i.e. the sample space). And then applying limit n tending to infinity, should be the answer. I found out to be coming around (36.5/81) although I am not sure about my calculations...
    Comments awaited...

    ReplyDelete
    Replies
    1. UnknownAugust 23, 2012 at 1:11 PM

      Let me inquire how did you get that the number of all strings of length at least n with non-zero left digit is 81*10^(2n-2)? As I see it is simply 10^n-1. If we calculcate the number of strings of length exactly n there are 9*10^(n-1) of them.

      However, the general question. How did you conclude that the probability of appearence of each string is equal? It's incorrect.

      Delete
  4. vishalNovember 4, 2011 at 10:31 PM

    Not sure if this method covers everything, but here is my approach, Let a and b be the labels on the two coordinate axis. Now in the 1st quadrant plane of (a,b), draw the lines L1: a = b, L2: a = 2b.In between these two lines, lie all the reals (a, b) > 0 such that a/b > 1. To calculate the ratio of area swept by this open triangle to the entire 1st quadrant, it should be sufficient to calculate the smaller angle between the the two lines L1 and L2 divided by pi/2. That is, (2/pi)* arctan (1/3). = 0.2048.
    By symmetry we can repeat this for all 4 quadrants.

    ReplyDelete
    Replies
    1. UnknownAugust 23, 2012 at 1:17 PM

      If I understood well we calculate the area of the triagle with vertices (0,0), (1,0), (1,0.5). The area is equal to 1/4.

      Delete
  5. El blog de un estudiante internacionalMay 18, 2012 at 9:13 PM

    Here is an alternative approach. I think in this case we have to look for a uniform distribution. If we take T(a) and T(b) the leading digits of a and b respectively, we can consider that T(a) and T(b) follow a uniform distribution on {1,2,...,8,9} as a and b are randomly chosen real numbers, any non-zero digit have the same probability of being the leading digit. So we need to calculate that T(a)/T(b) has 1 as his leading digit, that is verified if T(a)<=T(b)<2T(a). Now, as we considered T(a) and T(b) uniform distributed, we just count the cases and divide by 81, finally we obtain: P(T(a)<=T(b)<2T(a)) = 25/81

    ReplyDelete
    Replies
    1. UnknownAugust 23, 2012 at 1:38 PM

      ...that is verified if T(a)<=T(b)<2T(a).

      Consider a=2, b=3. a/b=0,(6) with T(a/b)=6.

      Further, you assume that T(a)/T(b)=T(a/b) that is incorrect.

      Delete
    2. UnknownAugust 31, 2012 at 2:19 PM

      Benford's law does the trick

      Delete
    3. smallvortexApril 25, 2013 at 7:49 AM

      Should invert a <->b:
      a/b have 1 as its leading digit <-> T(b)<T(a)<2T(b)

      Delete
  6. dmytroOctober 18, 2012 at 3:41 AM

    This comment has been removed by the author.

    ReplyDelete
  7. dmytroOctober 18, 2012 at 3:42 AM

    I got the answer 1/3 and confirmed this with a C++ simulation. I posted my solution in my blog. Please let me know what you think.
    http://puzzlesandstuff.blogspot.com/2012/10/prab-starts-with-1.html

    ReplyDelete
  8. Carl BarnesFebruary 11, 2013 at 9:05 PM

    Hi Vivek,
    Was the first puzzle asked in the computer test of WorlQuant or the interview?
    Can you tell me more about the online computer test?
    Thanks a lot!

    ReplyDelete
    Replies
    1. smallvortexApril 25, 2013 at 7:50 AM

      Do you get any information about that, could you give to me. Thanks :)

      Delete

Subscribe to: Post Comments (Atom)