Can you solve Dongle's Difficult Dilemma? - Dennis E. Shasha — Transcript

Full transcript

1. 0:06According to legend, when this planet was young and molten,
2. 0:10three galactic terraformers shaped it into a paradise.
3. 0:15When their work was done, they sought out new worlds,
4. 0:18but left the source of their power behind:
5. 0:21three powerful golden hexagons,
6. 0:25hidden within dungeons full of traps and monsters.
7. 0:28If one person were to bring all three hexagons together,
8. 0:32they could reinvent the world however they saw fit.
9. 0:36That was thousands of years ago.
10. 0:39Today, you’ve learned of Gordon, an evil wizard dead set on collecting the hexagons
11. 0:45and enslaving the world to his will.
12. 0:48So you set off on a quest to get them first,
13. 0:52adventuring through fire, ice, and sand.
14. 0:56Yet each time, you find that someone else got there first.
15. 1:00Not Gordon, but a merchant named Dongle.
16. 1:04At the end of the third dungeon. you find a note inviting you to Dongle’s castle.
17. 1:09You show up with a wallet bursting with the 99 gems
18. 1:13you’ve collected in your travels,
19. 1:14arriving just moments before Gordon, who also has 99 gems.
20. 1:20Dongle has not only collected the golden hexagons,
21. 1:24but he’s used them to create 5 silver hexagons,
22. 1:28just as powerful as their golden counterparts.
23. 1:31Why did Dongle do all this?
24. 1:33Because there’s one thing he loves above all else: auctions.
25. 1:38You and the evil wizard will compete to win the hexagons,
26. 1:43starting with the three golden ones,
27. 1:45making one bid for each item as it comes up.
28. 1:49The winners of ties will alternate, starting with you.
29. 1:53Whoever first collects a trio of either golden or silver hexagons
30. 1:58can use their power to recreate the world.
31. 2:01You’ve already bid 24 gems on the first,
32. 2:05when you realize that your rival has a dastardly advantage:
33. 2:09a mirror that lets him see what you’re bidding.
34. 2:13He bids zero, and you win the first hexagon outright.
35. 2:17What’s your strategy to win a matching trio of hexagons before your rival?
36. 2:22Pause here to figure it out for yourself.
37. 2:24Answer in 3
38. 2:25Answer in 2
39. 2:27Answer in 1
40. 2:31Dongle’s dangled a difficult dilemma.
41. 2:33Do you spend big to try to win the golden hexagons outright?
42. 2:37Save as much as possible for silver? Or something in-between?
43. 2:42Gordon can use his magic mirror and 99 gems
44. 2:45to make sure that no matter what you bid on the second gold,
45. 2:49he can bid one more and block you.
46. 2:51So the real question is— how can you force Gordon to spend enough on the golds
47. 2:57to guarantee that you’ll win on the silvers?
48. 3:01Here’s a hint.
49. 3:02Let’s say at the start of the silver auctions
50. 3:05you had a one gem advantage, such as 9 to 8.
51. 3:10You need to win three auctions,
52. 3:12so could you divide your gems into three groups of three and win?
53. 3:17For simplicity, let’s assume a set of rules that’s worse for you,
54. 3:21where Gordon wins every tie.
55. 3:24If you bid 3 each time, the best he could do
56. 3:27is win two silver hexagons, and have two gems left—
57. 3:31which you’ll beat with three bids of 3.
58. 3:35Any one-gem advantage where your starting total is divisible by three
59. 3:39will lead to victory by the same logic.
60. 3:43So knowing that, how can you force Gordon's hand in the gold auctions
61. 3:47so you go into silver with an advantage?
62. 3:50Let’s first imagine that Gordon lets you win the second gold auction
63. 3:54by betting some amount X with a tie.
64. 3:58You could then bid everything you have left on the third gold hexagon,
65. 4:02and he'd have to match you to block.
66. 4:05So if you could bid 51 on the third gold,
67. 4:08you'd go into silver with a 51 to 48 advantage, which you know you can win.
68. 4:15Solving for X reveals that in order to have 51 on round three,
69. 4:20you should bid at most 24 on round two.
70. 4:24But what about the other possibility,
71. 4:27where Gordon wins the second gold against your bid of 24—
72. 4:31would this strategy still work?
73. 4:34The least he could bid to win the second gold is 25,
74. 4:38making the total 75 to Gordon’s 74.
75. 4:42No one would then bid on round three,
76. 4:45since you’ve each blocked the other from getting three golds.
77. 4:49After that, you could bid 25 every time to win three silvers.
78. 4:55The bidding war was close,
79. 4:56but your ingenuity kept you one link ahead in the chain of inference,
80. 5:01and the silver tri-source is yours.
81. 5:04Now... what will you do with it?