### PROBLEM LINKS

### DIFFICULTY

CHALLENGE

### EXPLANATION

The problem is more commonly known as the necklace splitting problem that is often told with thieves trying to split a necklace with an even number of each jewel type so the two thieves get the same number of each jewel. Currently, no polynomial-time algorithm is known but is also not known to be NP-hard. There is one very interesting result concerning this problem. If d is the number of istinct ingredients/jewel types, then there is a way to cut the sandwich/necklace using at most d cuts [1]. However, the proof is non-constructive and does not provide a polynomial-time algorithm for finding these cuts. To get an idea what flavor these non-constructive are, it follows from the Borsuk-Ulam theorem which is like a very powerful generalization of Brouwer’s fixed-point theorem to higher dimensions.

The problem is known to be in PPAD [2] which roughly means that there is an algorithm that will find a solution using at most d cuts that

is, in some sense, similar in spirit to the Simplex algorithm for solving linear programs. The Wikipedia page on PPAD is a decent

starting point to learn more about problems in PPAD [3] if you are curious. It is an interesting complexity class between P and NP. There

is a notion of a problem being PPAD-complete and an interesting open problem is to determine if the necklace splitting problem is PPAD-complete or not.

- Alon, Noga; West, D. B. (December 1986). “The Borsuk-Ulam theorem and bisection of necklaces”. Proceedings of the American Mathematical

Society 98 (4 pages=623-628). - Christos Papadimitriou (1994). “On the complexity of the parity argument and other inefficient proofs of existence”. Journal of Computer and System Sciences 48 (3): 498-532. doi:10.1016/S0022-0000(05)80063-7
- http://en.wikipedia.org/wiki/PPAD

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.