Dennis is a professor of computer science at New York University. His latest books include Dr. Ecco's Cyberpuzzles: 36 Puzzles for Hackers and Other Mathematical Detectives (W.W. Norton, 2002) and Database Tuning: Principles, Experiments, and Troubleshooting Techniques (Morgan Kaufman, 2002). He can be contacted at DrEccoddj.com.
As I entered Ecco's apartment, I could see that he and his 10-year-old nephew Tyler were engaged in a heated discussion.
"This makes no sense uncle," Tyler said.
"The rule in checkers that forces me to jump prevents a whole world of strategies. I don't think it's necessary."
Ecco chuckled. "You would have gotten along well with William of Occam young Tyler."
"Occam's razor?" asked Liane.
"Right," Ecco responded, "the 13th century Franciscan theologian."
"I have his quote on my bedroom wall," Liane interjected. 'Plurality should not be assumed without necessity.' he wrote. He used the principle to fight beliefs in witchcraft. At the time, people accused witches of every possible mishap. He thought that the mishaps could come from completely natural causes. I figure that they would have heard me argue about mathematics or cosmology and convicted me forthwith. So he would have been my natural defender and ally."
"I agree," Ecco said smiling at his 16-year-old niece who somehow managed to look quite stylish in her lacrosse uniform. "He wanted explanations to be much simpler. Justice is often simple. But we'll come back to witchcraft and checkers another day, I promise. Today, I want to talk about using the Occam principles to find the ringleaders of a gang of 11 thieves.
"Here is the data we have. There have been several stock-trading events on 11 stocks that the authorities believe are collusions in purchases and sales of stock. Represent a purchase by a 1 and a sale by a 0. The 11 conspirators are smart enough not to communicate by phone or e-mail. We believe they collude by their actions. There are a few ringleaders who perform actions and then their subordinate conspirators compute a particularly simple logical/arithmetic function to decide on their action.
"Our informant tells us that they use just two circuit elements: AND takes some collection of 1s and 0s as inputs and outputs a 1 if all the inputs are 1; otherwise, it ouputs a 0. ODD returns a 1 if the number of 1s in its input collection is odd and otherwise it returns 0. (Note that if there are no 1s in its input collection, ODD returns 0.) Just those two circuit elements. No more.
"One or both of these circuit elements are used by each subordinate conspirator we believe. Here's a warmup. There were 12 events and 6 conspirators who did the following (on six different stocks):
conspirator 1: 1 1 0 1 0 0 0 1 0 1 1 1
conspirator 2: 0 1 0 1 1 1 1 0 0 1 1 1
conspirator 3: 1 1 0 1 0 0 0 1 0 1 1 1
conspirator 4: 1 1 0 0 1 1 1 0 1 0 0 0
conspirator 5: 0 0 0 0 1 1 1 1 1 0 0 0
conspirator 6: 0 1 0 0 0 0 0 1 1 0 0 0
Which ones are the ringleaders? Try before you read on."
Solution to the Warm-Up Puzzle
Conspirators 2, 4, and 6 are, or at least could be, the ringleaders. Conspirators 1 and 3 simply take the ODD function on the buy/sell values of the ringleaders. For example, in the first column, the values of conspirators 2, 4, and 6 are 0, 1, 0, respectively, so there are an odd number of 1s. In the second, 2, 4, 6 have the values 1, 1, 1, so again there are an odd number of 1s. Conspirator 5 computes the function: AND the results of 2 and 4, then take the ODD function on that result and the input from 6 (see Figure 1).
.Algebraically, C5=ODD(C6, AND(C2, C4)). So, the first column produce a 0 from the AND and the input from 6 is also 0 so the result is 0. In the second column, the AND produces a 1, but the input from 6 is also a 1, so the number of 1s is even; hence, we get a 0 result.
- Ok, now it's your turn. Here are the conspirators' buy/sell decisions on 11 different stocks.
conspirator 1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
conspirator 2: 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 0
conspirator 3: 0 0 1 1 1 1 1 0 1 1 0 1 1 0 1 0
conspirator 4: 0 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0
conspirator 5: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
conspirator 6: 1 0 0 0 1 1 0 1 1 1 1 1 0 1 0 1
conspirator 7: 1 1 0 1 0 0 1 1 0 0 1 0 1 0 0 1
conspirator 8: 1 0 1 0 0 1 0 0 0 1 1 1 0 1 1 1
conspirator 9: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
conspirator 10: 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 1
conspirator 11: 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0
Reader: Try to find the ringleaders and how each of the subordinate conspirators make his or her decision. You may be able to do this on your kitchen table. Hint: Tyler and Liane were able to do this assuming only four ringleaders. It's open whether fewer could be the ringleaders, assuming each subordinate computes a function using only at most one AND and one ODD circuit.
- There is a new group of trades. Liane and Tyler believe there are only 3 ringleaders this time. They also think the conspirators have grown careless. Can you see why?
conspirator 1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
conspirator 2: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
conspirator 3: 0 1 0 0 0 0 1 1 0 0 0 1 1 0 1 1
conspirator 4: 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1
conspirator 5: 0 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1
conspirator 6: 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1
conspirator 7: 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1
conspirator 8: 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1
conspirator 9: 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1
conspirator 10: 0 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0
conspirator 11: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
One thing that worries Ecco is that perhaps any random set of buy/sell decisions among 11 traders over a time scale of 16 could lead to the conclusion that four ringleaders and possibly even three were responsible. That would mean innocent people would be falsely accused. Do you think this would be a common occurrence for the simple AND/ODD circuits presented here? Perhaps you can find an elegant counting argument.
For the solution to last month's puzzle, see page 88.
DDJ
