Okay today we have a puzzle. So I'm gonna
give you all the numbers from 1 to 15, I
suspect you're gonna shorten this
dramatically in the edit. Your challenge
is: can you take numbers from 1 to 15 and
can you rearrange them into a new order
such that any two adjacent numbers add
to give you a square number? So, for
example, you could put 1 - let's give it a
go, we'll give it a try - we can put 1 there and
then next to it we could put 3. You go,
okay that's pretty good because 1 plus 3
is 4, that's a square number. I could
chuck 6 here, because 3 plus 6 is 9,
that's a square number. Oh what am I
gonna do? What can I add to that to make
it a square number? 10 - that'll work, right? And
then so on. So we'll give you a second if
you want to try it. - (Brady: So we have to use all)
(of them?) - Yeah use all of them. In one
long line; any order you want but any
two that are adjacent have to add to a
square number.
Welcome back, thank you for trying the
puzzle. If you got it- - (Brady: It could be it could)
(be days later!) - It could be days later, my goodness how you have
aged, but you know you gave it a go. You
were saying Brady you didn't think it was
possible, like it feels unlikely? You know?
But it can be done and I gave you a
false start - it doesn't work if you have
these numbers in this order. So I
deliberately, and very meanly, gave you a
starting point that does not work.
(Brady: Why would you do that?) - Because I'm a jerk.
I want people to work it out for
themselves; but why doesn't it work? Right,
because this does- this fulfills the
requirement. Every two of these do add to
give you a square number, but then you
just you can't join up the rest of them,
right? You've run out of room. So
the way I went about solving this when I
first did it was I thought, okay I'm
gonna draw all the possible links.
Because you start looking at this and
you're like, okay well 10 works with 15
cos I get 25 but 10 also works with 6.
And so actually I've got options
for how I put them in the same order. Snd
some of them have more possible links or
neighbours they could go with than you
can actually put in a long line. So I was
like, right right I'm gonna do this.
There's 1, I put 1 over here - I can do
them in order, that's 1. Okay 2: 1 and 2
don't add to give you a square number so
I'm gonna put 2 over there out of the
way, right ok. 3: now 3 I can add- link to
1 because that gives me 4, that is a
square number. Now four doesn't work with
anything so far, but it does work with 5
so I put 5 over there. 6 works with 3;
and so you can see if I only had the
numbers from 1 to 6 it wouldn't be
possible to order them, so every single
pair adds to a square number. Put 7 into
the mix; 7 goes with 2 because it gives
you 9, 8 adds on to 1 - gives you 9. 9 fits
in off 7, because I get 16. 10 links into
6 - 16, 11- and still now I've got these
series I could use. In fact if this looks
familiar that there is the original
series I gave: 8, 1, 3, 6, 10
is one possible ordering. But there's no
way so far to link it up with the rest
of them, we'll keep filling these in. 12
to 4,13 we'll also link to 12 because I
can get 25; oh but I can also get 16 so that
links to... Aha! Okay so now we're starting
to join this all together. Let's put in
14. And 14 is the first number where now
everything holds together because 14, 25
and 16 - we've now got a connected network,
or graph - whatever you want to call it.
But there's no path, right? So this would
work but you've missed 1 and 8.
That would work but you've missed these.
So at 14 it's all joined together but
doesn't work, 15 is the one you need to
hold it all together. Because 15 fills in
this gap: 1- so there's 25 and 16, and now
there's our solution. 8, 1, 15, 10, 6, 3, 13, 12;
and then all the way along that tail. And
so that is the order you've got to put
those numbers so that every single pair
between them adds to a square number. And
I- annoyingly I picked this bit here of
this curve, knowing that that is not a
valid part of the path that goes all the
way through this square sums network.
(Brady: That makes 15 a pretty special number.)
It makes 15 a pretty special number,
it's the first number for which
you can order the numbers so every
single- so you you were right Brady to think,
that doesn't feel likely. And it's
because I picked 15, because up until then
doesn't work. I could've picked 16 actually
because 16 you can add on to 9 to get 25.
Okay; oh wait all 17. Okay so 17 goes over
there and so now you think, well there you go that's perf-
and there's the path: 16 all the way
through to 17 you have a perfectly valid
solution. But why stop there? Why not do
it from 1 to 18? 18 fits in over here,
there's 18. Oh now, now we've got a
problem. Because if you put 18 over there
there's no longer a way to go through
the whole network, going through every
single number once and once only; because
we've got a tail here sticking off and
we've got a little tail sticking here.
And if we start here and go that way we
can never get back to 18, if
we start here we can never go back for
these guys. So we've broken it. So it
works for all the numbers from 15 to 17,
and then 18 breaks it. But what if it
works again after that?
So we'd call this a graph in mathematics,
and graph theory is what we're kind of
using to solve this puzzle. And we're
looking for a path - a path is any
kind of journey which doesn't go through
the same vertex more than once. And if we
have a path that goes through every
single vertex then it's called a
Hamiltonian path. And so to solve this
puzzle you're looking for the
Hamiltonian path which goes all the way
through the graph. So let's try adding on
a few more numbers and see if we can get it
to work for a bigger value. If I add 19
over here that doesn't solve our two
tails problem over there. So as long as
this exists there are no solutions. 20
doesn't help; ooh actually that's now
solved one tail problem. So we can come
in here, oh but maybe if we come in here we
either go around that way or we go
around that way. Because we then have
to come off and do the rest of this. And
because of this bottleneck here and here
you do one way, but if you loop around then
you can't get out so that's still not
solvable. We need another way out of this
loop before we can do it.
21? Oh, starting to get crowded. 21 can go down
here because it links 15, which I'm gonna
run under there, to 4. So these are
crossing but that's that's not a new
vertex, right, obviously I'm just drawing
the links. 22 links up 3 to 14; does that
get us out of our problem? Because we can
come through here and out, but then we
can't get out- it's still not doable.
It can be done once we get to 23. So if
we put 23 in- let's pop it down there. Now
it is possible to trace all the way
through this network. Shall we give
it a go? I have spoken too soon! Okay we
can work this out. So okay, let's see if we can
do this. You've got to start from 18 because
that's like our little tail over here. If
we come in here and we go all the way
around here,
I suspect we need to mop up these.
Because if we leave any of these behind we're gonna be
in trouble. So let's come down, take those, get
into here, come up here- oh yeah here we
go; then we go across 21, 15, 10, 6, 19, 17, 8, 1
and there you go. So it's possible to
find a Hamiltonian path on the graph, as
soon as we add node 23. But very sadly
when we add node 24 it breaks again. So
24 joins 1 to 12, 24 goes there. And then
1 links to 12. And now it's broken
again! But when you add 25 it's fixed
again! And it then works for 26, it works
with 27, and it works all the way up so-
we think. As far as we're aware, from 25
onwards it works for every possible
value. You can somehow find a path
through this network.
Well it's not over yet people, if you'd like to see even
bigger graphs with more nodes and their
Hamiltonian paths have a look at our
extra footage over on Numberphile2.
You'll also hear more stories from Matt,
including how he made a bit of a Parker
square of this issue when he was doing
his book. And you'll hear from a very
special guest. I'll put links down in the
description and in all the usual places,
thanks for watching.