Tuesday, May 19, 2009
String of Pearls
Two friends found a necklace (a loop) of pearls. There are some black pearls and some white pearls, all otherwise indistinguishable. They want to cut the necklace into two parts (with two cuts) so that the number of black pearls on each side match, and the number of white pearls match. They cannot cut the pearls themselves, but instead cut the necklace between the pearls. There are an even number of black pearls, and an even number of white pearls. Prove that you can always do it, or else find a case where it cannot be done. After arguing and working on it for a 15 minutes, they came up with an argument. But afterwards Lizzy said she didn't like it much (compared for example to Sunday's freecell problem). This problem comes from one of Charles Leiserson's papers (I don't remember which) on VLSI layout.