The Elegant Heist: Mastering the Art of Necklace Splitting

Ever wondered how stolen necklaces are tactfully divided? Join us on a captivating journey into the math under necklace splitting! This journey will lead us to a wonderful and very important theorem in mathematics, the Borsuk-Ulam theorem.

Imagine you and your friend Alice are two thieves and you stole a necklace together. The necklace has beads of two colors, red and blue. Now, you would like to split it evenly, or in other words, each of you would like half of the red beads and half of the blue beads. To do this, you open the necklace at the clasp and get an interval of beads. We assume the number of red beads and blue beads are both even, so the desired splitting is possible. But you also don't want to cut the necklace in too many pieces. How many cuts are enough to guarantee a desired division? Do you have any guesses?

The above is the simplest setting of Necklace Splitting. Last year I took a course on Algorithmic Game Theory and got interested in how algorithms and complexity appear in economic applications. During my personal investigation into the field, this problem interested me a lot because of its roots in combinatorics. I believe this is an interesting topic because it’s easy to describe but the solution to the problem is non-trivial at all. Therefore, I would like to share it with you. Are you ready? Let’s go dive into the world of necklace splitting!

Steal & Split a Necklace

As said in the beginning, you and your friend Alice stole a necklace which consists of beads of two colors, red and blue. And you would like to split it evenly. For example, the interval of beads can look like this:

Figure 1: An example of a necklace with beads of two colors.

You would like to cut the necklace into several pieces and distribute the beads evenly, in this example, each of you get 4 blue beads and 3 red beads, so 7 beads in total. Moreover you would like to use only a small number of cuts. Think about it a bit: in this example, could you use only one cut to split the necklace and take two intervals containing exactly 4 blue and 3 red beads?

If each one wants half of the beads and use a single cut, then the necklace should obviously be cut in the middle. However, then you may find the left interval has only one red bead, which is less than required. Conversely, the number of red beads in the right interval is more than required. So, it is not possible with a single cut.

But then you could shift the left interval to the right, one bead per step. We represent this below using the green box, you start moving from left to right until you get an interval with 4 blue beads. Now you need to use two cuts instead, which divide the necklace into three parts. As you can see the middle interval (in the green box) achieves the goal of 4 blue and 3 red beads. Similarly, combining the other two intervals also achieves the goal.

Figure 2: Moving the green box from the left to the right you can find the two cuts.

How many cuts will always do the job?

But are 2 cuts always enough for splitting an arbitrary necklace with an even number of blue and red beads? The answer is yes! Image a long necklace with an even number of blue and red beads, and you cut it in the middle. Then similarly, if the left has too few red beads, the right must have too many red beads. Observe that if you shift the left interval to the right by one bead, the number of red beads in it can only change by at most 1. Since at the beginning you get too few red beads and you get too much in the end, and in each step the number of red beads can only change by 1, then there must exists a stage that you get the right number of red beads. Because you always get half beads in this way, then the number of blue beads you get is also correct.

This argument shows that 2 cuts are always sufficient! In the proof above, we used a theorem in mathematics, the discrete version of the Intermediate Value Theorem. The Intermediate Value Theorem is one of those results we learn at school when studying functions but we don't appreciate its importance at that moment.

Intermediate Value Theorem
The Intermediate Value Theorem says any continuous function over a closed interval achieves all values between the function values at the endpoints of the closed interval.

Furthermore, it is not possible, in general, to achieve such a splitting with only one cut. To see this, consider, next to the example in Figure 1, also the following example: it is necessary to use 2 cuts to achieve the desired splitting, can you see why?

Figure 3: Putting beads of the same color next to eachother shows that 2 cuts are sometimes necessary.

More colors, more cuts, and Borsuk-Ulam does the magic

What if the necklace is more complicated in the sense that the beads have more colors? If the necklace has beads of 3 colors for example, how many cuts do you need to split it evenly among two thieves? How about 4 or in general $k$ colors? The problem is defined formally as follows:

General form of necklace-splitting problem

Given a $k$ -types and $n$ -beads necklace consisting of $a_j$ beads of each type $j$ ( $a_j$ is even), and the beads are fixed on the string, how many cuts are needed to guarantee a fair splitting such that each thief gets $a_j/2$ beads of each type $j$ ?

In fact, it turns out that for a necklace with $k$ -colors $k$ cuts are always enough! Furthermore, $k$ cuts are sometimes necessary by considering a $k$ -colored necklace using a similar construction as above, by putting all beads of the same color together. This result was obtained by mathematicians Professor Noga Alon and Professor Douglas West in the 80s using the Borsuk-Ulam theorem from Algebraic Topology. In fact, the name of the problem was also due to them.

Let us see together what the Borsuk-Ulam theorem states and how it solves this problem.

The Borsuk-Ulam theorem

The Borsuk-Ulam theorem says that if $f : \mathbb{S}^n \rightarrow \mathbb{R}^n$ is continuous, then there exists a point $x\in \mathbb{S}^n$ such that $f(-x) = f(x)$ .

Don't feel intimidated by the formal statement. When we write $\mathbb{R}^n$ we mean the set of $n$ -dimensional vectors of real numbers, i.e.

$\mathbb{R}^n = \{(x_1,x_2,\dots,x_n): x_i \in \mathbb{R}\}.$

With $\mathbb{S}^n$ we mean a sphere as you know it, but in $n$ dimensions, $\mathbb{S}^1$ is just the circle, $\mathbb{S}^2$ is the "ordinary" sphere. The formal definition is

$\mathbb{S}^n = \{ x \in \mathbb{R}^n \text{ such that } x_1^2+x_2^2+\dots+x_n^2 =1\}.$

In other words, every continuous function from an $n$ -dimensional sphere to the real vectors always maps some pair of antipodal points to the same number. Antipodal points are in exactly opposite directions form the sphere’s center.

Couple of fun facts

Do you know that you can apply the Borsuk-Ulam theorem to the earth to get a classical conclusion: On earth, there are always two antipodal points with same temperature and same pressure.

A second interesting fact is that in 1978 László Lovász (you can read an interview with Lovász here) proved Kneser's conjecture using the Borsuk-Ulam theorem. This breakthrough gave rise to the field of topological combinatorics.

To apply the Borsuk-Ulam theorem, we need to translate the necklace splitting problem to a so-called topological problem, that is to write as a problem concerning a function from the sphere to the real numbers.

We can use a function to keep track of where the necklace is split and the amount of each type of beads secured by each thief. This is achieved by representing the splitting points on the necklace using the unit $m$ -sphere (we denote the unknown needed number of cuts as $m$ ), where each point corresponds to a specific way the necklace is split. Each point on the sphere encodes information about the lengths of the necklace pieces, with positive and negative roots allowing differentiation between the two thieves. We’ll illustrate this using the following example

The green area in the middle represents a splitting in two pieces. This specific splitting can be represented as the vector

$\left(\frac{\sqrt{14}}{7}, - \frac{\sqrt{2}}{2}, \frac{\sqrt{42}}{14}\right) \in \mathbb{S}^2.$

Try to verify this using the definition of $\mathbb{S}^2$ above.

How did we do this translation? Observe that this splitting breaks the necklace in three pieces with lengths equal to $\frac{2}{7}, \frac{1}{2}$ and $\frac{3}{14}$ of the total length. We represent these numbers as a vector on the unit sphere $\mathbb{S}^2$ , observe that $\frac{2}{7} = \left(\frac{\sqrt{14}}{7}\right)^2, \frac{1}{2} = \left(-\frac{\sqrt{2}}{2}\right)^2$ , and $\frac{3}{14} = \left(\frac{\sqrt{42}}{14}\right)^2$ . Moreover

$\left(\frac{\sqrt{14}}{7}\right)^2 + \left(-\frac{\sqrt{2}}{2}\right)^2 + \left(\frac{\sqrt{42}}{14}\right)^2 = 1.$

Thief 1 receives the first and third pieces (because they are with + sign) and thief 2 receives the second (because it is with - sign). This step shows how to translate the points at which the necklase is cut to points on the sphere, cutting the necklase at $m$ points yields a point on $\mathbb{S}^{m-1}$ . The next step is to construct a continuous function from the sphere to the real vectors.

This function will record how many beads of each type of bead one of the two thieves receives. Say that the necklace consists of beads of $k$ different colors, then this function will send a cut of the necklace to a vector of numbers in $\mathbb{R}^k$ . In the example above it will be

$\left(\frac{\sqrt{14}}{7}, - \frac{\sqrt{2}}{2}, \frac{\sqrt{42}}{14}\right) \mapsto (4, 3).$

This means that the first thief receives 4 blue beads and 3 red ones. By considering the necklace as a continuous map from the $m$ -sphere to $\mathbb{R}^k$ , the problem is rigorously formulated. Recall the Borsuk-Ulan theorem, every continuous function from an $n$ -dimensional sphere to $\mathbb{R}^n$ always maps some pair of antipodal points to the same number. To apply the theorem the dimensions of the sphere and the reals should be the same.

Let's choose the number of cuts $m$ to be equal to the number of the types of beads $k$ , and suppose there is an even number of each type of bead. Then according to the Borsuk-Ulam theorem there are two andipodal points $x, -x \in \mathbb{S}^k$ such that $f(x) = f(-x)$ . But remember what $f(x)$ represents, and what does it mean to flip the sign in $x$ . If an element in $x = (x_1, x_2, \dots, x_m)$ , say $x_k$ is positive, then this means that thief one takes the beads in that cut. Hence the andipodal point $-x$ gives essentially the same information as $x$ since only the signs are flipped. The equality $f(x) = f(-x)$ means thus that in the cut $x$ both thieves receive the same number of beads for each color!

The theorem states that there must be some way to split the necklace evenly between the thieves. This way we have shown the sufficiency of $k$ cuts to guarantee a fair splitting between two thieves using the Borsuk-Ulam theorem. The last question that remains open is whether $k$ cuts are necessary. If you have a necklace with beads of $k$ colors, could you in general split it with less than $k$ cuts? In general no. Consider for example a necklace where beads of the same color are placed next to eachother.

I hope you were excited about learning how to use a topological method to solve an “easy” problem seemingly having nothing about topology at the first place, which is necklace splitting. However, even though we have shown that there always exists a solution with at most $k$ cuts, this proof is non constructive, which means that we have no clue from it how could we efficiently find a $k$ -cut does the job.

In summary, we discussed a constructive proof of necklace splitting problem between two thieves when we restrict the type of beads be at most two. Moreover, a general, non-constructive proof via the Borsuk-Ulam theorem was given for the general cases. Moreover, we learned that sometimes a math problem can (or even must) be solved using tools from other fields in math, showing the deep connections between different subjects inside the world of mathematics!

The featured image was taken from this amazing video from Numberphile. You can also watch this very nice video from 3blue1brown on the necklace splitting problem and the Borsuk-Ulam theorem.

Would you like to stay up to date when a new post appears on the Network Pages?

Subscribe to our mailing list