Tukde tukde

Consider a loop of string of unit length. Suppose we cut the string independently and at random in n places. This will divide the loop into n pieces.

1. What is the expected (average) size of the smallest piece?
2. What is the expected (average) size of the largest piece?

If you can't find an exact answer the asymptotic behaviour (to leading order) as n goes to infinity will suffice.

Update (11/12/09): Solution in comments!!

Comments

  1. An attempt to solve the first part:

    Lets work in the field of cards. You have B black and R Red cards. How many ways can you arrange them so that the minimum distance between any two red cards is greater than or equal to D?
    Its easy to see that it would be equal to distributing B - (R-1)D to R+1 beggars i.e. binomial(B - RD + D +R, R)

    So, the probability that the minimum distance is greater than or equal to D is binomail(B-RD+D+R, R)/binomial(B+R,R)

    Now, in the problem here, the probability that the minimum distance is greater than x is
    R = n;
    B is approaching infinity
    D/B = x/2pi
    So,
    The probability is
    (1+(1-n)x)^n

    So, expected value of x is it integral for x varies from 0 to 1/n
    which evaluates to 1/n^2
    :)
    :) I solved it... yo! yo! Infi max happy!! :)

    Solution of second part is from IBM's site:
    The answer to the second part can be derived by applying the above idea recursively and inductively. Consider a set of n points on an unit loop (with one point at 0). Let x be the size of the smallest piece if the loop is cut at those points. Consider deleting a piece of length x after each point. This will merge two of the points leaving a set of (n-1) points on a loop of length (1-n*x) (still with one point at 0). Since the expected size of x is 1/(n*n) the expected size of the smaller loop is (1-1/n). Let y be the size of the smallest piece when the smaller loop is cut at the remaining points. Clearly the expected size of y=(1-1/n)*(1/(n-1)*(n-1))=1/(n*(n-1)). Now the size of the second smallest piece in the original loop is x+y which has expected size (1/n)*((1/n)+(1/(n-1)). Continuing in this way we find that the expected size of the kth smallest piece is (1/n)*((1/n)+(1/(n-1))+ ... +(1/(n-k+1))). (Note the sum of the expected sizes of all the pieces is 1 as expected.) So the expected size of the largest piece (ie the nth smallest piece) is (1/n)(1+1/2+...+1/n). It is well known that the sum (1+1/2+...+1/n) behaves like ln(n) for large n so asymptotically the largest piece has size ln(n)/n.
    :)

    ReplyDelete
    Replies
    1. Edit in the solution to the first part:

      The analogy to the card problem is not that direct. How many ways can you arrange them so that the minimum distance between any two red cards and a red card and the end is greater than or equal to D?

      Its easy to see that it would be equal to distributing B - (R+1)D to R+1 beggars i.e. binomial(B - RD - D +R, R)

      D/B = x (and not D/B = x/2pi)
      R = n-1 (and not n as the first cut will just open the loop. So, effectively there are just n-1 cuts)

      The probability is
      (1-nx)^(n-1)

      So, expected value of x is it integral for x varies from 0 to 1/n
      which evaluates to 1/n^2

      Delete
  2. Thank you for maintaining this blog, helps getting a collection of the best puzzles at the time of job prep. A query - why can't we translate and expand the answer of the first part into that of the second part ? Consider the lengths of pieces as (1-x1),(1-x2),(1-x3)...... where x1, x2, x3 .... were the original lengths. Doesn't this correspond to an (n-1) dilated version of the original problem, hence getting an answer of (n+1)/n^2 ?

    ReplyDelete
    Replies
    1. Thanks for your kind words.

      Regarding your query, Please explain your solution in detail. Since your answer for second part is greater than the correct answer, I would guess that you might me making a mistake that a lot of people make. You might be taking union of the sets instead of intersection, hence increasing the probability and increasing the expected value. Please check. Thanks

      Delete
    2. You should refer the link: http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/January2006.html

      Delete

Post a Comment