Can you solve the fortress riddle? - Henri Picciotto
Bad news: your worst enemies
are at the gate.
For your fledgling kingdom guards the
world’s only herd of tiny dino creatures.
To you, they’re sacred.
To everyone else, they’re food.
The three closest nation-states
have all teamed up
in what they call
an alliance of the hungry
to smash open your walls
and devour the herd.
Your fortifications will hold
off their armies for now.
But when their siege weapons arrive
tomorrow,
you won’t stand a chance.
Luckily, you have a wall fabricator:
if you run it all night, you may be able
to reinforce your border
before the weapons arrive.
However, it can only create wall segments
of a specific, whole number size
that you must determine ahead of time.
Your engineers have been in close
consultation with your spymaster.
Each rival kingdom has wall-busters
that come in one specific size.
The clowns’ are all 6 meters,
the royals’ are 9,
and the redheads’ are 20.
Each wall-buster can level a wall segment
of the matching size.
And they can be combined as well;
two 6′s can take out a 12 meter wall
and a 6 and a 9 could break one
that’s 15 meters.
But a 7 meter wall would hold
fast against any of them.
Meanwhile, large walls aren't
necessarily protected.
Here’s how they could take
down 70, 71, and 72 meters.
Your fabricator takes the same amount
of time to produce a wall segment
no matter its length,
and it’s not particularly fast.
So to finish the wall in time,
you need the longest segment
that can’t be destroyed
by any combination of the siege weapons,
which your enemies have hundreds of.
What wall length will save your kingdom?
Pause here to figure it out yourself.
Answer in 3
Answer in 2
Answer in 1
It's possible to solve this problem
by trial and error.
But there’s also a remarkably quick
and elegant solution
inspired by an idea that’s thousands
of years old:
the sieve of Eratosthenes.
Eratosthenes of Cyrene was a 3rd century
BCE mathematician from ancient Greece
interested in prime numbers,
that is numbers only divisible
by 1 and themselves.
Presumably he grew bored of manually
checking whether a given number was prime,
so he came up with the
following technique.
Make a giant list of numbers.
X out all of the multiples of 2,
except 2 itself.
Now do the same with multiples of 3.
The even multiples have already
been eliminated,
and the odd multiples can all be found
in this column.
4 was already accounted for when
you did multiples of 2,
so move on to 5.
The multiples of 5 and 7 show
up conveniently in diagonals.
This method eliminates all possible
composite numbers,
leaving only primes behind.
We've already identified every
prime less than 121,
and it’s easy to go
higher and higher this way.
We can use a similar technique
with our wall problem
to eliminate entire groups
of numbers at once.
A first, critical step is to be deliberate
about the number of columns.
If we use 6 again, the numbers in each
column will be exactly 6 apart.
What that means is that if we identify
a number vulnerable to the wall-busters,
then all the rest of the column
below it would also fall.
In other words,
because your enemies can make 9,
they can make 15, 21, 27, and so on
by adding the clowns’ 6-meter machines.
So right away this eliminates 6, 9 and 20,
and everything under them.
We’ve accounted for the 6′s
with the columns,
so we can focus on combinations
of 20′s and 9′s to eliminate more options.
Your rivals can easily make 20 plus 9
and 20 plus 20 and everything below.
Using this approach, we could
have eliminated the 70, 71, and 72,
and infinitely many other options
without having to do any calculations.
In the remaining column there are
no multiples of 9 or 20,
but 49 jumps out,
as 2 times 20 plus 9.
There's no way to make 43,
so that must be the largest wall segment
that your enemies can’t destroy.
And there you have it.
You plug 43 into the wall fabricator,
and after a tense night,
the sun rises on your now
impregnable fortress
and a herd that won’t become
unhappy meals.
