## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 1381-1408 |

Number of pages | 28 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 38 |

Issue number | 2 |

DOIs | |

State | Published - Jun 2024 |

## All Science Journal Classification (ASJC) codes

- General Mathematics

## Keywords

- necklace
- random walk
- second moment method