A Tricky Vote
An election is being held to select one of two candidates, A or B. n voters turn out in a long, orderly line. A motley crew of pollsters show up to predict the turnout, but none is diligent enough to survey the entire line, or savvy enough to conduct a proper statistical sample. Instead, each pollster arbitrarily selects some single interval of the line and queries everyone in that interval. The intervals may be of various sizes, and they may overlap.
After comparing their haphazard data, the pollsters notice that candidate A, the presumptive favorite, has more than two-thirds support in every survey interval.
Assume the process is 'nice' in the following senses:
-Everyone truthfully reveals their intentions to the pollsters, and intentions don't change;
-Everyone in line eventually votes (once) for their intended candidate, and votes are faithfully counted;
-No one changes position in the line.
Also assume that everyone is surveyed at least once.
Can you conclude that candidate A is the winner?
Note that 2/3 is the lowest threshold one could hope for: for consider 4 voters, with prefereces going B A A B, and with 2 survey intervals consisting of the first three and last three voters respectively; then A has exactly 2/3 support in each, yet the outcome is a tie.
If this problem gives you trouble, try solving it first with 'two thirds' replaced by 'ninety-nine percent'.
I enjoy questions like this one, that try to deduce 'global' conditions from a collection of 'local' observations. With the advent of 'property testing' in computer science, they have become increasingly important to the field. I hope to make further posts on the subject soon, and possibly also discuss generalizations of the above problem (Does anyone know if/where it's been studied before?)
Update, 9/27: I've since learned that this problem falls in well-trod territory of functional and harmonic analysis; specifically, the (affirmative) answer to this problem essentially states that a certain 'maximal operator' over a function space is 'bounded'. The solution techniques described by David and myself in the comments are standard and fall under the rubric of 'covering theorems', the most basic one being due to Vitali. I'll try to blog more soon on what I've learned about this problem, which gets very interesting in 2 dimensions...
After comparing their haphazard data, the pollsters notice that candidate A, the presumptive favorite, has more than two-thirds support in every survey interval.
Assume the process is 'nice' in the following senses:
-Everyone truthfully reveals their intentions to the pollsters, and intentions don't change;
-Everyone in line eventually votes (once) for their intended candidate, and votes are faithfully counted;
-No one changes position in the line.
Also assume that everyone is surveyed at least once.
Can you conclude that candidate A is the winner?
Note that 2/3 is the lowest threshold one could hope for: for consider 4 voters, with prefereces going B A A B, and with 2 survey intervals consisting of the first three and last three voters respectively; then A has exactly 2/3 support in each, yet the outcome is a tie.
If this problem gives you trouble, try solving it first with 'two thirds' replaced by 'ninety-nine percent'.
I enjoy questions like this one, that try to deduce 'global' conditions from a collection of 'local' observations. With the advent of 'property testing' in computer science, they have become increasingly important to the field. I hope to make further posts on the subject soon, and possibly also discuss generalizations of the above problem (Does anyone know if/where it's been studied before?)
Update, 9/27: I've since learned that this problem falls in well-trod territory of functional and harmonic analysis; specifically, the (affirmative) answer to this problem essentially states that a certain 'maximal operator' over a function space is 'bounded'. The solution techniques described by David and myself in the comments are standard and fall under the rubric of 'covering theorems', the most basic one being due to Vitali. I'll try to blog more soon on what I've learned about this problem, which gets very interesting in 2 dimensions...
Labels: general math, puzzles
posted by Andy D at
6:38 PM
2 Comments:
Yes, candidate A is the winner. Here is an easy proof. Let's call an interval a "polled interval" if some pollster has surveyed it.
Lemma: There is a collection of polled intervals I_1, ... I_r such that every voter is in at least 1 of the I_j's but no voter is in more than 2.
Proof: Let I_1, ..., I_r be the smallest collection of polled intervals which contains every voter. Suppose, for contradiction, that voter x is in more than two of the I_j's. Then there is some I_j containing x such that the let end point of I_j is (weakly) to the right of some other I_k which contains x and such that the right endpoint of I_j is (weakly) to the left of some other I_l which contains x. But then I_j is contained in I_k union I_l, so we can delete I_j and obtain a smaller collection, a contradiction. QED.
Now that we have the lemma, the claim is immediate. Fix a collection of intervals as in the lemma. If every voter voted as many times as the number of intervals in which he was contained, then candidate A would win by at least a 2:1 ratio. Making each voter vote only once can only cut candidate A's total by a factor of 2 at most, so he still wins.
David Speyer
By
Anonymous, at 3:55 PM
Thanks, David--that was exactly my solution.
My first analysis worked by isolating a 'significant' collection of disjoint polled intervals--containing at least half the voters--and that yielded a slightly worse result, hence my suggestion to readers. I then realized it was easy to modify to get the improved result.
By
Anonymous, at 1:40 AM
Post a Comment
<< Home