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. Pratik Poddar9:01 PM, November 05, 2009

    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. Pratik Poddar3:30 PM, December 26, 2012

      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. Anoopam Agarwal7:47 PM, October 13, 2012

    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. Pratik Poddar3:35 PM, December 26, 2012

      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. Pratik Poddar3:37 PM, December 26, 2012

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

      Delete

Post a Comment

Popular posts from this blog

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

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 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Consecutive Heads

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 tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more