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.