Election Fraud in Verity

Dr. Dobb's Journal August, 2005

By Dennis E. Shasha

Dennis is a professor of computer science at New York University. His most recent books are Dr. Ecco's Cyberpuzzles (2002) and Puzzling Adventures (2005), both published by W. W. Norton. He can be contacted at DrEcco@ddj.com.

Dr. Ecco Solution

In a certain county having voting machines without paper trails, inspectors depend on exit polls to determine whether the voting machines have worked properly. Normally, they use statistics and the assumption of random sampling, but sometimes they want to be sure.

The city of Verity is proud of its honest electorate. Two candidates, Fred and Wendy, have run against one another. There are only 100 voters. Each voter is given a unique number between 1 and 100 upon leaving the voting booth. The five pollsters record those numbers as well as the votes when they ask the voters how they voted. Each pollster manages to talk to 80 voters, and in every case, Fred beats Wendy by 42 to 38. Yet Wendy carries the city by 51 to 49. Upon hearing these results, Fred cries foul. You are brought in to investigate. Both Fred and Wendy agree about the following:

The voters were honest with the pollsters and the pollsters reported their results honestly.
Every pollster spoke to 80 people, 42 of whom voted for Fred against only 38 for Wendy.
Between every pair of pollsters, all 100 people were interviewed.

How many pollsters could there be under these conditions for it to be possible that Wendy won, even if this were unlikely assuming random sampling?
How might the voters be divided among the pollsters?
So, was Fred right?

Here is an open problem: Suppose we made a change, so that between every pair of pollsters, at least 96 distinct voters were interviewed, instead of all 100 people. In this case, how many pollsters could there be?

DDJ