3
$\begingroup$

Two thieves steal a necklace consisting of 10 rubies and 14 diamonds, fixed in some arbitrary order on a loop of string. Show that they can cut the necklace in two places so that when each thief takes one of the resulting pieces, he gets half the rubies and half the diamonds.

The above question has been solved on youtube but the answer given is too complicated. I seek a very intuitive and simple answer that even a school student can understand.

Bonus 1: In general, if there are x different kind of stones on the necklace then how many cuts would be needed to divide the stones equally between the 2 thieves. Assume that there are an even number of stones of each type.

Bonus 2: There are x different kind of stones on the necklace and y thieves. How many cuts are needed to divide the stones equally among the y thieves. Assume that the number of each kind of stone is divisible by y.

$\endgroup$
4
  • 4
    $\begingroup$ Please provide a YouTube link for puzzle attribution $\endgroup$
    – bobble
    Feb 24 at 15:10
  • 1
    $\begingroup$ That 3b1b video! I remember it. This is the link, so it can be attributed. $\endgroup$
    – Someone
    Feb 24 at 22:44
  • $\begingroup$ @Someone - While 3Blue1Brown is a favorite, I have seen others cover the same topic. So it could be that the OP was referring to a different video. $\endgroup$ Feb 25 at 13:59
  • $\begingroup$ Further information about the problem: en.wikipedia.org/wiki/Necklace_splitting_problem $\endgroup$ Feb 25 at 17:53

4 Answers 4

8
$\begingroup$

Note that:

each thief will get 12 gems, so arbitrarily choose any section of 12 gems in a row. If it happens to already contain exactly 5 rubies and 7 diamonds, just cut the necklace at the ends of this interval and you're done.

If not, then there are either too few rubies or too few diamonds in the interval you chose. Say there are too few rubies (it doesn't matter which, the argument works either way). Shift the interval one spot clockwise and count again. At most you can pick up one additional ruby each time you do this, and at some point you will have shifted all the way around to the other side where there are too many rubies and too few diamonds. Since you started with not enough rubies and ended with too many rubies, and the count of rubies and diamonds can only change by one each time you shifted, that means you must have passed through an interval where you had exactly the right number of rubies and that is the interval where you should make your cuts.

Edited to add illustrations:

Arbitrarily choose some place to cut the necklace in half:

enter image description here

Shift the place you cut one spot to the right and count again:

enter image description here

Keep shifting until you reach the desired end state:

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

enter image description here

$\endgroup$
3
  • $\begingroup$ Thanks a lot. Can you please attempt the bonus questions as well ? $\endgroup$ Feb 24 at 19:11
  • $\begingroup$ For the bonus questions are you still assuming there are 24 gems on the necklace in total? $\endgroup$
    – SQLnoob
    Feb 24 at 21:07
  • $\begingroup$ No, I am not assuming that but if you prefer then you can assume that there are 24 gems . $\endgroup$ Feb 25 at 6:05
2
$\begingroup$

Here is how to do.

Number the stones from 1 to 24. You want to find a set of 12 adjacent stones containing exactly 5 rubies and 7 diamonds.

Since there are only rubies and diamonds, you only need to make sure there are exactly 7 diamonds.

If the first 12 stones contain 7 diamonds, then you are done, cut between 24 and 1 and between stones 12 and 13. Both pieces contains 7 diamonds and 5 rubies.

If not, then assume wlog that the left side (1-12) contains less than 7 diamonds. The right part must contain more than 7 diamonds.

In that situation you can apply the Intermediate Value Theorem but in the discrete form.

Consider the sets {1..12}, {2..13}, {3..14}, etc. to {13..24}. Each set has one stone added and one stone removed compared to the previous set. So the number of diamonds in each set can be at most one more or one less than the previous. It can be equal.
Since the set {1..12} contains less than 7 diamonds and the set {13..24} contains more than 7 diamonds, and the count changes by at most 1 between sets, there must be one set that has exactly 7 diamonds. If not there is no way to go from "less than 7 diamonds" to "more than 7 diamonds".
When you have identified the set, just cut it out of the necklace, it contains 7 diamonds and 5 rubies. The rest of the neclace is bound to also contains 7 diamonds and 5 rubies.

$\endgroup$
2
  • $\begingroup$ Thanks a lot. Could you please try the bonus questions as well? $\endgroup$ Feb 24 at 19:11
  • $\begingroup$ The 2 stone problem is a classic problem. More than 2 is not. Anyway, with 2 thieves there will obviously be an even number of cuts. For 3 stones, 2 cuts will not be enough so you will need 4. I suppose with 4 degrees of freedom and 3 constraints it should be possible. So probably 4 cuts for 3 stone types and possibly also for 4 types. $\endgroup$
    – Florian F
    Feb 24 at 23:19
0
$\begingroup$

I'd love to come back and add diagrams for the examples.

Say you start with a loop that has all of the diamonds and all of the rubys together. You can easily cut that in half to get 7 diamonds and 5 rubies each.
rrrrrddddddd|dddddddrrrrr

The starting pattern can be made more elaborate by swapping pairs of stones.

You can swap a diamond and a ruby on one side and it still balances.
For example, the first and last stone on the right half.
rrrrrddddddd|rddddddrrrrd

If you swap a diamond on one side with a ruby on the other side, it becomes unbalanced.
rrrrrddddrdd|dddddddrrdrr
But if the chain is rotated before cutting, either the last stone or the first stone on each half is passed to the other half.
If the above chain is rotated to the left, the left side passes a ruby to the right side, and the right side passes a diamond to the left side.
rrrrddddrddd|ddddddrrdrrr
They're now balanced again.

It's possible that a rotation will pass matching stones to the other half. This happens when the two stones opposite each other on the chain are the same type. If you keep rotating, you'll eventually find a pair of different stones which when passed, will balance the chain.

"What if every stone has a matching stone opposite it and the balance never changes?" If the opposite stone is the same, then that pair of stones is balanced. If all opposing pairs of stones are the same, then all paris of stones are balanced and no balancing is required.
drdrddrdrdrd|drdrddrdrdrd

$\endgroup$
3
  • 1
    $\begingroup$ Your unalike pairs argument doesn't quite work. Rotating past such a pair will change the counts, but it doesn't seem obvious to me that the change is guaranteed to be in the right direction (it could make the balance worse) $\endgroup$
    – fljx
    Feb 24 at 9:50
  • $\begingroup$ And, if the imbalance is greater than 1, you also need to show that there will always be enough unalike pairs that will change the counts in the right direction to rebalance. $\endgroup$
    – fljx
    Feb 24 at 9:51
  • $\begingroup$ @fljx , can you provide the right answer? $\endgroup$ Feb 24 at 12:28
0
$\begingroup$

Partial answer for bonus 2:

If x = y, then it may require as many as x*(x-1) cuts.

It's possible that all the gems of one type appear consecutively on the necklace. For each of the x types, there are x-1 (overlapping) adjacent pairs of that type, and since each thief needs to get just one of them, it takes x-1 cuts to split each of those pairs.

For instance, if x = 4, then the necklace could be AAAABBBBCCCCDDDD -> A|A|A|AB|B|B|BC|C|C|CD|D|D|D -> (AB C D) (BC A D) (CD A B) (DA B C)

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.