Puzzle time - cutting the necklace
-
Two thieves steal a necklace consisting of 10 rubies and 14 emeralds, fixed in some arbitrary order on a loop of golden 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 emeralds.
-
:::
Starting with the emeralds, you have 14 different cut pairings available which splits them up 7 and 7. Let the cuts occur at the clockwise edge of the emerald, leaving any rubies between the adjacent emeralds on the clockwise side of the cuts.
Then let the ruby imbalance be described by a number from -10 to 10. The objective is zero. Each of the 14 cut pairings gives an imbalance number. For every negative number, there will be an opposing positive number where the cut pairing is in the opposite order but otherwise identical. So if a given cut pairing has non-zero imbalance, you're guaranteed, as you move the cut pairing one position clockwise, that you'll eventually reach adjacent cut pairings where one has an imbalance to one side, and the next has an imbalance to the other side. In any such case, one of the cuts can be moved clockwise such that it captures exactly enough rubies to set the imbalance to zero.
:::
-
-
@Horace I was thinking along the same lines, but your last sentence is where I still scratch my head. For continuous functions, there's the "intermediate value theorem", but your imbalance is discrete - couldn't it "jump" over the 0, e.g., from -1 to +1?
@klaus said in Puzzle time - cutting the necklace:
@Horace I was thinking along the same lines, but your last sentence is where I still scratch my head. For continuous functions, there's the "intermediate value theorem", but your imbalance is discrete - couldn't it "jump" over the 0, e.g., from -1 to +1?
Right, good point. So let the number be "rubies clockwise from first cut" minus "rubies clockwise from second cut". That number, for an even number of rubies, will always be even itself: in this case from the set [-10, -8, ..., 8, 10]. Any capturing of a ruby by moving the cut within the space between emeralds will modify that number by 2, up or down. If the sign of that number changes when the original pair of cuts is rotated clockwise, then you can go back to the previous pair and move one of the cuts clockwise to capture the appropriate number of rubies.
