Can you solve the fantasy election riddle? - Dennis E. Shasha

After much debate, the fantasy realm you call home

has decided dragon jousting may not be the best way to choose its leaders,

and has begun transitioning to democracy.

The candidates are a giant orange troll and an experienced tree statesman.

An all-powerful eyebrow has hired your company— The Dormor Polling Agency—

to survey the citizens of the land and predict who will win.

There’s a lot riding on this:

if you get it wrong, heads— well, your head—

will quite literally roll.

Your job is to go from door to door,

asking voters whether they prefer the troll or the treefellow

and to use the results to project how the election will go.

Your fellow citizens want you to succeed and would tell you the truth...

but there’s a problem.

Few are willing to admit they support the troll

on account of his controversial life choices.

If you were to ask a troll supporter who she'll vote for,

there’s a good chance that she’ll claim to support the treeman,

skewing your results.

You’re about to begin your rounds when a stranger offers you some cryptic advice:

“Here’s the question that will save your neck: what have you got in your pocket?”

You reach into your pocket and pull out... a silver coin,

which has the current king’s head on one side and his tail on the other.

How can you use it to conduct an accurate poll?

Pause here to figure it out yourself. Answer in 3

Answer in 2

Answer in 1

The trick here is to use the coin to add random chance

to your interaction that will give troll supporters deniability.

In other words, you’re looking for a system where when someone says “troll,”

it could either be because the coin somehow told them to,

or because they actually support the troll—

and you’d have no way to tell the difference.

You’ll also need to know how frequently the coin skewed the results,

so you can account for it in your calculations.

One solution is to have every pollee go into their house and flip the coin.

If it lands heads, they should tell you “troll,”

whether or not they actually support him.

If it lands tails, they should tell you their actual preference.

Here’s what happens:

you poll 200 voters, and 130 say they’ll vote for the troll.

For about 50%, or 100 of them, the coin will have landed heads.

So you can subtract 100 troll votes off his total,

and know the troll’s real support is 30 to 70, and he’s very likely to lose.

The election comes around, but before the results can be certified

a third party candidate swoops in and burns the treefellow to a crisp.

The freshly signed and deeply flawed constitution mandates that this challenger

gets to take his victim’s place in a new election.

The Dormor Polling Agency sends you back out on the streets with your trusty coin.

Only this time no one is comfortable admitting their preference:

supporting the troll is still shameful,

and nobody wants to express support of a dragon who murdered his way into the race.

But your job is your job. How do you conduct an accurate poll now?

Pause here to figure it out for yourself. Answer in 3

Answer in 2

Answer in 1

This time, instead of masking just one candidate preference,

you need some way to disguise both.

At the same time, you also need to leave space for some portion of the people

polled to express their true preference.

But a coin toss only has two possible outcomes... right?

Suppose you have everyone flip the coin twice—

now there are four possible results.

You can tell the people who flip heads twice in a row

to report support for the troll;

those who get tails twice in a row to report dragon;

and those with any other combination to declare their true preference.

The chances of getting either two heads or two tails in a row

are 50% times 50%— or 25%.

Subtracting that proportion of the total respondents

from each candidate’s score should give you something close

to the real distribution.

This time, 105 respondents announced themselves in favor of the troll

and 95 for the dragon.

Out of the total, the coin will make 25%

or 50 respond troll and another 50 respond dragon.

Subtracting 50 from each result reveals that voters seem to prefer the troll

by a margin of about 55 to 45.

It’s close, but as predicted, the troll wins the election,

and you live to poll another day.