Can you solve the fortress riddle? - Henri Picciotto

1,359,161 views ・ 2022-05-31

TED-Ed


Please double-click on the English subtitles below to play the video.

00:07
Bad news: your worst enemies are at the gate.
0
7503
3921
00:11
For your fledgling kingdom guards the world’s only herd of tiny dino creatures.
1
11424
6340
00:17
To you, they’re sacred.
2
17972
1627
00:19
To everyone else, they’re food.
3
19599
2210
00:21
The three closest nation-states have all teamed up
4
21851
3670
00:25
in what they call an alliance of the hungry
5
25521
2878
00:28
to smash open your walls and devour the herd.
6
28399
3212
00:32
Your fortifications will hold off their armies for now.
7
32111
3504
00:35
But when their siege weapons arrive tomorrow,
8
35615
2627
00:38
you won’t stand a chance.
9
38242
1794
00:40
Luckily, you have a wall fabricator:
10
40203
2502
00:42
if you run it all night, you may be able to reinforce your border
11
42705
4088
00:46
before the weapons arrive.
12
46793
1793
00:48
However, it can only create wall segments of a specific, whole number size
13
48711
5714
00:54
that you must determine ahead of time.
14
54425
2586
00:57
Your engineers have been in close consultation with your spymaster.
15
57428
4129
01:01
Each rival kingdom has wall-busters that come in one specific size.
16
61808
5255
01:07
The clowns’ are all 6 meters,
17
67230
2210
01:09
the royals’ are 9, and the redheads’ are 20.
18
69524
3962
01:13
Each wall-buster can level a wall segment of the matching size.
19
73986
4547
01:18
And they can be combined as well;
20
78616
2002
01:20
two 6′s can take out a 12 meter wall
21
80618
3253
01:23
and a 6 and a 9 could break one that’s 15 meters.
22
83871
3587
01:27
But a 7 meter wall would hold fast against any of them.
23
87625
4087
01:32
Meanwhile, large walls aren't necessarily protected.
24
92380
3628
01:36
Here’s how they could take down 70, 71, and 72 meters.
25
96175
5130
01:41
Your fabricator takes the same amount of time to produce a wall segment
26
101639
3921
01:45
no matter its length, and it’s not particularly fast.
27
105560
3461
01:49
So to finish the wall in time,
28
109188
2002
01:51
you need the longest segment that can’t be destroyed
29
111190
3128
01:54
by any combination of the siege weapons,
30
114318
2670
01:56
which your enemies have hundreds of.
31
116988
2294
01:59
What wall length will save your kingdom?
32
119824
2711
02:02
Pause here to figure it out yourself. Answer in 3
33
122869
2711
02:05
Answer in 2
34
125580
2544
02:08
Answer in 1
35
128124
2335
02:10
It's possible to solve this problem by trial and error.
36
130710
3503
02:14
But there’s also a remarkably quick and elegant solution
37
134213
3587
02:17
inspired by an idea that’s thousands of years old:
38
137800
3545
02:21
the sieve of Eratosthenes.
39
141345
2169
02:23
Eratosthenes of Cyrene was a 3rd century BCE mathematician from ancient Greece
40
143806
6256
02:30
interested in prime numbers,
41
150062
2378
02:32
that is numbers only divisible by 1 and themselves.
42
152440
4254
02:37
Presumably he grew bored of manually checking whether a given number was prime,
43
157445
5005
02:42
so he came up with the following technique.
44
162450
2836
02:45
Make a giant list of numbers.
45
165995
2169
02:48
X out all of the multiples of 2, except 2 itself.
46
168164
3837
02:52
Now do the same with multiples of 3.
47
172460
2461
02:55
The even multiples have already been eliminated,
48
175129
2753
02:57
and the odd multiples can all be found in this column.
49
177882
3795
03:02
4 was already accounted for when you did multiples of 2,
50
182053
3545
03:05
so move on to 5.
51
185598
1752
03:07
The multiples of 5 and 7 show up conveniently in diagonals.
52
187516
4880
03:12
This method eliminates all possible composite numbers,
53
192605
3920
03:16
leaving only primes behind.
54
196525
2294
03:19
We've already identified every prime less than 121,
55
199195
4212
03:23
and it’s easy to go higher and higher this way.
56
203658
2419
03:26
We can use a similar technique with our wall problem
57
206619
3420
03:30
to eliminate entire groups of numbers at once.
58
210039
3337
03:33
A first, critical step is to be deliberate about the number of columns.
59
213834
4880
03:38
If we use 6 again, the numbers in each column will be exactly 6 apart.
60
218839
4880
03:43
What that means is that if we identify a number vulnerable to the wall-busters,
61
223970
4504
03:48
then all the rest of the column below it would also fall.
62
228474
3629
03:52
In other words, because your enemies can make 9,
63
232520
3211
03:55
they can make 15, 21, 27, and so on
64
235731
4129
03:59
by adding the clowns’ 6-meter machines.
65
239860
3045
04:03
So right away this eliminates 6, 9 and 20, and everything under them.
66
243030
5506
04:09
We’ve accounted for the 6′s with the columns,
67
249203
2461
04:11
so we can focus on combinations of 20′s and 9′s to eliminate more options.
68
251664
5505
04:17
Your rivals can easily make 20 plus 9 and 20 plus 20 and everything below.
69
257378
5881
04:23
Using this approach, we could have eliminated the 70, 71, and 72,
70
263634
5381
04:29
and infinitely many other options without having to do any calculations.
71
269015
4754
04:34
In the remaining column there are no multiples of 9 or 20,
72
274103
4171
04:38
but 49 jumps out, as 2 times 20 plus 9.
73
278274
3712
04:42
There's no way to make 43,
74
282236
1960
04:44
so that must be the largest wall segment that your enemies can’t destroy.
75
284405
4838
04:49
And there you have it.
76
289493
1377
04:50
You plug 43 into the wall fabricator, and after a tense night,
77
290870
4212
04:55
the sun rises on your now impregnable fortress
78
295082
3504
04:58
and a herd that won’t become unhappy meals.
79
298586
3211
About this website

This site will introduce you to YouTube videos that are useful for learning English. You will see English lessons taught by top-notch teachers from around the world. Double-click on the English subtitles displayed on each video page to play the video from there. The subtitles scroll in sync with the video playback. If you have any comments or requests, please contact us using this contact form.

https://forms.gle/WvT1wiN1qDtmnspy7