Dr. Dobb's | Election Fraud in Verity

Election Fraud in Verity

A little electoral math to puzzle your brain.

August 01, 2005
URL:http://www.drdobbs.com/parallel/election-fraud-in-verity/184406218

August, 2005: Election Fraud in Verity

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 [email protected].

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

August, 2005: Election Fraud in Verity

Dr. Ecco Solution

Solution to "Treasure Arrow," DDJ, July 2005.

Let's first solve the problem symbolically. The pole has length L, mass Mp, and the arrowhead has weight Ma. We represent the pole's mass Mp as a point mass at the center.

Now, let's say we have five elastics including ones at the ends and at every quarter point. We know that the lengths of the bands must form a straight line because the pole is stiff. This observation (due to my colleague Alan Siegel) gives us a constraint in addition to balanced torque and balanced vertical force. Here, s1 is the stretch of the leftmost band in centimeters. is the difference from one band to the next one to the right, again in centimeters.

s1+=s2
s2+=s3
s3+=s4
s4+=s5

The balance of vertical forces gives us:

5s1+((1+2+3+4))=Mp+Ma

The balance of torques gives us:

LMp/2 from the pole.

Countertorques:

L(s1+(3/4)(s1+)+(1/2)(s1+2)+(1/4)(s1+3))
=L((s1(1+3/4+1/2+1/4))+
(3/4+1+3/4))
=L(2.5s1+2.5)
=2.5L(s1+)

So (1) Mp/2=2.5(s1+), from torque balance; (2) Mp+Ma=5(s1+2), from vertical balance. From (2), ((Mp + Ma)/5)- 2=s1. Therefore, using the torque balance:

Mp/2=2.5(s1+)
=2.5((((Mp+Ma)/5)-2)+)
= 2.5((((Mp+Ma)/5)-))
=(2.5((Mp+Ma)/5))-(2.5)
=(((Mp+Ma)/2))-(2.5)

So:

2.5=Ma/2
=Ma/5

Therefore, s1=Mp/5+Ma/5-2Ma/5= Mp/5-Ma/5. This implies that if Mp= Ma, then s1=0. Since these two quantities are in fact equal, s1=0, so the left band is at its rest length of 1 meter, the right band is down 60 centimeters, and the arrow is pointing to a point that is 100 cm+260 cm=2.2 meters from the top. Further, is 20 centimeters. So, Mp=Ma=100 kilograms.

Optimal Farming: Errata and Reader Improvements

Alan Dragoo was the first to point out the bug in my solution to problem 1. He suggested a design where one circle would cover a central square and four smaller rectangles would cover side rectangles. Denis Birnie independently arrived at the same solution, as well as a very interesting solution for open problem three. You can find those at http://cs.nyu.edu/cs/faculty/shasha/papers/birniedobbssol.doc.

DDJ