On the number of monochromatic close pairs of beads in a rosary

✍ Scribed by Oded Goldreich

• Book ID: 103056173
• Publisher: Elsevier Science
• Year: 1990
• Tongue: English
• Weight: 518 KB
• Volume: 80
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(90)90295-s

✦ Synopsis

We consider the following problem: Let r be a n-bead rosary with m white beads and n -m black beads. Let t be an integer, t <<n. Denote by MC,(r) the number of pairs, of monochromatic beads which are within distance t apart, in the rosary r. What is the minimum value of MC,(.), when the minimum is taken over all n-bead rosaries which consists of m white beads and n -m black beads? We prove a (reasonably) tight lower bound for this combinatorial problem. Surprisingly, when m = n 12, the answer is -(ti -1) . nt, rather than nt/2 that one might have expected. ' Ignoring additive "error" terms of the form O(r* + n/t).