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.

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?