8
$\begingroup$

Our problem is the following:

Let $n$ and $k$ be integers. We are given two (unclasped) necklaces, each with $n$ colored stones: a top necklace which has $k$ colors and a bottom necklace which has 2 colors (black and white) each appearing $n/2$ times. Say that a color of the top necklace is balanced with respect to the bottom necklace if, when we match the stones from the top with those on the bottom in pairs in order (i.e. the first stones are paired up, the second stones are paired up, etc.), the stones of that color are matched with as many black stones as white (assume that the number of stones of each of the $k$ colors is even). We then say that the top necklace is balanced with respect to the bottom necklace if each of its colors is balanced. Our goal is to find the minimum number $c = c(n,k)$ such that given any pattern of colors in the top and bottom necklaces, we can cut the top necklace with at most $c$ cuts and permute the cut pieces into a new necklace that is balanced with respect to the bottom necklace.

This problem is a variation of the necklace splitting problem of Alon, Goldberg, and West. We have conjectured that, like necklace splitting, our problem can be solved by making at most $c(n,k) = k$ cuts in the top necklace and permuting the cuts via some fixed permutation of $[k+1]$. We have not been able to find any counterexamples to this conjecture after searching through some small values of $n$ and $k$, but we are unsure of how to prove it. The proof from Alon and West applies the Borsuk-Ulam theorem, but we can't see how to apply Borsuk-Ulam to our problem directly.

We are mostly interested in the case where $k$ is a power of two. Furthermore, we have a proof that at most three cuts are needed to solve the case when $k=2$. Basically, we construct a set of $n(n-1)$ permutations that are 1-wise independent, each of which can be acquired by at most three cuts. Additionally, we can order the permutations such that each pair of adjacent permutations differs in at most 2 locations. Likewise, how far we are away from balancing the first color changes by at most one as we apply sequential permutations to a given top necklace. By 1-wise independence, the first color of the top necklace is balanced with respect to the bottom on average as we range over all the permutations, so there must exist one permutation where the first color is balanced. Once the first color is balanced, the second color is as well.

Any thoughts on this problem are appreciated.

Improve this question
$\endgroup$
8
  • $\begingroup$ What if I'm only interested in permutations where I cut the (top) necklace into pieces like 1,2,3,4,5,6, and then put the pieces back together like 1,3,5,2,4,6? Do you have an example that would show that in this case k cuts might not be sufficient? $\endgroup$
    – domotorp
    Nov 7 at 5:38
  • $\begingroup$ Those sort of fixed permutations are in fact exactly the ones we've generally used in our computer search. So far, we have not found any counterexamples for those permutations. $\endgroup$
    – Sam King
    Nov 7 at 18:33
  • $\begingroup$ @domotorp Correction, we've now found a counterexample: our program says that the necklaces 0011223344 and 0000011111 cannot be balanced with 5 cuts and the permutation 123456->135246. Other permutations of 5 cuts still work however, e.g. 135264. $\endgroup$
    – Sam King
    Nov 7 at 20:13
  • $\begingroup$ Is there a typo somewhere? 135246 and 135264 should give the same thing for 0000011111. In fact, 0000011111 corresponds to traditional necklace splitting, so in this case 135246 should always work. $\endgroup$
    – domotorp
    Nov 7 at 20:20
  • 1
    $\begingroup$ @domotorp I'm not sure I understand this counterexample. For two colors in the top necklace, we use two cuts and permute the cuts like 132. So we can cut like so: a|a|bbbbbb $\endgroup$
    – Sam King
    Nov 8 at 20:30

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.