### 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