Can you solve the stolen rubies riddle? - Dennis Shasha
One of the kingdom’s
most prosperous merchants
has been exposed for his corrupt dealings.
Nearly all of his riches
are invested in a collection
of 30 exquisite Burmese rubies,
and the crowd in the square
is clamoring for their confiscation
to reimburse his victims.
But the scoundrel and his allies at court
have made a convincing case
that at least some of his wealth
was obtained legitimately,
and through good service to the crown.
The king ponders for a minute
and announces his judgment.
Because there’s no way to know
which portion of the rubies
were bought with ill-gotten wealth,
the fine will be determined through
a game of wits between the merchant
and the king’s most clever advisor – you.
You’re both told the rules in advance.
The merchant will be allowed to
discreetly divide his rubies
among three boxes, which
will then be placed in front of you.
You will be given three cards,
and must write a number
between 1 and 30 on each,
before putting a card in
front of each of the boxes.
The boxes will then all be opened.
For each box, you will receive exactly
as many rubies as the number written
on the corresponding card,
if the box has that many.
But if your number is greater than
the number of rubies actually there,
the scoundrel gets to keep the entire box.
The king puts just two constraints on how
the scoundrel distributes his rubies.
Each box must contain at least two rubies
and one of the boxes must contain
exactly six more rubies than another—
but you won’t know which boxes those are.
After a few minutes of deliberation,
the merchant hides the gems,
and the boxes are brought in front of you.
Which numbers should you choose
in order to guarantee the largest possible
fine for the scoundrel
and the greatest compensation
for his victims?
Pause the video now if you want
to figure it out for yourself.
Answer in 3
Answer in 2
Answer in 1
You don’t want to overshoot
by being too greedy.
But there is a way you can guarantee
to get more than half of the scoundrel’s
stash.
The situation resembles an
adversarial game like chess –
only here you can’t see the
opponent’s position.
To figure out the minimum number of rubies
you’re guaranteed to win,
you need to look for the worst case
scenario,
as if the merchant already knew your move
and could arrange the rubies
to minimize your winnings.
Because you have no way of knowing which
boxes will have more or fewer rubies,
you should pick the same number for each.
Suppose you write three 9’s.
The scoundrel might have allocated the
rubies as 8, 14 and 8.
In that case, you’d receive 9 from the
middle box and no others.
On the other hand, you can be
sure that at least two boxes
have a minimum of 8 rubies.
Here’s why.
We’ll start by assuming the opposite,
that two boxes have 7 or fewer.
Those could not be the two that
differ by 6,
because every box must have
at least 2 rubies.
In that case, the third box would have at
most 13 rubies—that’s 7 plus 6.
Add up all three of those boxes,
and the most that could equal is 27.
Since that’s less than 30,
this scenario isn’t possible.
You now know, by what’s called
a proof by contradiction,
that two of the boxes have
8 or more rubies.
If you ask for 8 from all three boxes
you’ll receive at least 16—
and that’s the best you can guarantee,
as you can see by thinking again
about the 8, 14, 8 scenario.
You’ve recovered more than half the
scoundrel’s fortune
as restitution for the public.
And though he’s managed to hold
on to some of his rubies,
his fortune has definitely
lost some of its shine.
