Credit for this problem goes to TED-Ed. Thanks!

## Protect the fortress

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 (clowns, royals, and redheads) 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.

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?

To recap, here are the rules:

1. Find the largest possible whole number length that cannot be made by adding 6’s, 9’s, and 20’s.

2. The opening the fabricator needs to protect is 1km wide. You can plug gaps at teh ends with loose boulders, so don’t worry if your wall segment size won’t fill it exactly.

3. Your enemies have hundreds of seige weapons, so there is no segment size that would be too long for them to destroy.

4. To destroy a wall segment, one or more seige weapons must strike along its exact length - no more, no less.

Solution