January 2006
<<December January February>>
Answer:
Identify the loop of string with real numbers from the unit interval in the obvious way. We may assume without loss of generality that one of the cuts is at 0. Fix n. Let x be the expected size of the smallest piece. Let f(t) be the probability that the smallest piece has size at least t. Note it is easy to see that x equals the integral from 0 to 1 of f(t). We claim f(t)=(1-n*t)**(n-1) for t < 1/n, f(t)=0 otherwise. Let t < 1/n. Then we assert configurations of n points on a unit loop of string (with one point at 0) such that cutting at those points produces pieces of length at least t correspond to configurations of n points on a loop of length (1-n*t) with one point at 0 and otherwise unrestricted. This follows because the configurations map into each other by deleting (or adding) length t of string after each point. The claim follows because the density of the configurations on the shorter loop is (1-n*t)**(n-1). We can now compute x by evaluating the integral of (1-n*t)**(n-1) with respect to t from 0 to 1/n. Let s=(1-n*t). Then the integral becomes (1/n)*(integral from 0 to 1 of s**(n-1) with respect to s) or 1/(n*n). So the answer to the first part is 1/(n*n).
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.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com