RANDOM NECKLACES REQUIRE FEWER CUTS

It is known that any open necklace with beads of t types, in which the number of beads of each type is divisible by k, can be partitioned by at most (k 1)t cuts into intervals that can be distributed into k collections, each containing the same number of beads of each type. This is tight for all values of k and t. Here, we consider the case of random necklaces, where the number of beads of each type is km. Then the minimum number of cuts required for a "fair"partition with the above property is a random variable X(k, t,m). We prove that for fixed k, t and large m, this random variable is at least (k 1)(t + 1)/2 with high probability. For k = 2, fixed t, and large m, we determine the asymptotic behavior of the probability that X(2, t,m) = s for all values of s ≤ t. We show that this probability is polynomially small when s < (t + 1)/2, is bounded away from zero when s > (t + 1)/2, and decays like Θ (1/ logm) when s = (t + 1)/2. We also show that for large t, X(2, t, 1) is at most (0.4 + o(1))t with high probability and that for large t and large ratio k/ log t, X(k, t, 1) is o(kt) with high probability.