Can you solve Dongle's Difficult Dilemma? - Dennis E. Shasha
According to legend,
when this planet was young and molten,
three galactic terraformers
shaped it into a paradise.
When their work was done,
they sought out new worlds,
but left the source of their power behind:
three powerful golden hexagons,
hidden within dungeons
full of traps and monsters.
If one person were to bring all
three hexagons together,
they could reinvent the world
however they saw fit.
That was thousands of years ago.
Today, you’ve learned of Gordon, an evil
wizard dead set on collecting the hexagons
and enslaving the world to his will.
So you set off on a quest
to get them first,
adventuring through fire, ice, and sand.
Yet each time, you find that someone else
got there first.
Not Gordon, but a merchant named Dongle.
At the end of the third dungeon. you find
a note inviting you to Dongle’s castle.
You show up with a wallet bursting
with the 99 gems
you’ve collected in your travels,
arriving just moments before Gordon,
who also has 99 gems.
Dongle has not only collected
the golden hexagons,
but he’s used them to create
5 silver hexagons,
just as powerful
as their golden counterparts.
Why did Dongle do all this?
Because there’s one thing he loves
above all else: auctions.
You and the evil wizard will compete
to win the hexagons,
starting with the three golden ones,
making one bid for each item
as it comes up.
The winners of ties will alternate,
starting with you.
Whoever first collects a trio
of either golden or silver hexagons
can use their power to recreate the world.
You’ve already bid 24 gems on the first,
when you realize that your rival
has a dastardly advantage:
a mirror that lets him see
what you’re bidding.
He bids zero,
and you win the first hexagon outright.
What’s your strategy to win a matching
trio of hexagons before your rival?
Pause here to figure it out for yourself.
Answer in 3
Answer in 2
Answer in 1
Dongle’s dangled a difficult dilemma.
Do you spend big to try to win
the golden hexagons outright?
Save as much as possible for silver?
Or something in-between?
Gordon can use his magic mirror
and 99 gems
to make sure that no matter what you bid
on the second gold,
he can bid one more and block you.
So the real question is— how can you force
Gordon to spend enough on the golds
to guarantee that you’ll win
on the silvers?
Here’s a hint.
Let’s say at the start
of the silver auctions
you had a one gem advantage,
such as 9 to 8.
You need to win three auctions,
so could you divide your gems
into three groups of three and win?
For simplicity, let’s assume
a set of rules that’s worse for you,
where Gordon wins every tie.
If you bid 3 each time,
the best he could do
is win two silver hexagons,
and have two gems left—
which you’ll beat with
three bids of 3.
Any one-gem advantage where your
starting total is divisible by three
will lead to victory by the same logic.
So knowing that, how can you force
Gordon's hand in the gold auctions
so you go into silver with an advantage?
Let’s first imagine that Gordon lets
you win the second gold auction
by betting some amount X with a tie.
You could then bid everything you have
left on the third gold hexagon,
and he'd have to match you to block.
So if you could bid 51 on the third gold,
you'd go into silver with a 51 to 48
advantage, which you know you can win.
Solving for X reveals that in order
to have 51 on round three,
you should bid at most 24 on round two.
But what about the other possibility,
where Gordon wins the second gold
against your bid of 24—
would this strategy still work?
The least he could bid to win
the second gold is 25,
making the total 75 to Gordon’s 74.
No one would then bid on round three,
since you’ve each blocked the other
from getting three golds.
After that, you could bid 25
every time to win three silvers.
The bidding war was close,
but your ingenuity kept you one link
ahead in the chain of inference,
and the silver tri-source is yours.
Now... what will you do with it?
