So today I want to tell you a problem that was devised
by a Hungarian mathematician called Pál Turán.
And this was something he noticed when he worked in a forced labor camp in World War II;
he was actually forced to work in a brick making factory. His job is you had the kilns,
right, that's making the bricks; and then he would have to load the bricks onto a trolley
and then he would run that trolley on tracks and take it to the storage units. So you could just
run these bricks to and from the storage units. The only problem was when these tracks crossed
because when they crossed the trolleys had a habit of jumping the tracks and spinning the
bricks right - oh no, right, what a disaster. So it did make him think how can we make these tracks
or how can we design this brick making factory so we can minimise the number of crossings? So
that's our problem for today, this is the brick factory problem. All right so we've got kilns and
storage units let's do one kiln and one storage unit just to keep it simple. So that's not going
to be a problem is it? So that's just going to be a track connecting the kiln to the storage unit; not
a problem at all. What if we had one kiln and two storage units? Doesn't sound like it's going
to be a problem either does it? And then yes we can just run a track; and we want to connect the kiln
to every storage unit, that's the idea. Let's say we had two kilns and two storage units, maybe that's
a little bit more interesting. Maybe you have a kiln here and a kiln there and two storage units. Now we
want to connect every kiln to every storage unit so that would have to connect, that would have to
connect, that would have to connect. Maybe you can see I've got a crossing point here. So if I went
to complete it - I'll just do it - I'm going to have a crossing point. So what do you think? What could
we do to solve that problem? So so we could have our kilns and storage units like before; we could
start to connect them like this, and then instead of crossing the tracks maybe I'll just do a loop.
That would solve the problem. Or as another solution maybe I could just put my kilns and
storage units in a bit of a circle like this - kiln, storage, kiln, storage. Then I can connect everything
together in a loop like that, now it's another way to solve the problem. The first interesting example
will be three kilns and three storage units; so let's take a look at that. We can connect these
together, so far so good, but then we're going to start getting into problems I think. So I need to
connect to the second storage unit, and I connect to the third storage unit - I think I'm going to
start getting tracks that are crossing. And I'm going to get an answer like this - I think I have 7
crossing points. Right, oh, what a disaster. You don't want seven crossing points, you'll be picking up
bricks all day. Right, how could we solve that? How about- I don't know, best solution I can think of:
Put them in a circle, let's try that. Kiln,storage unit, alternating in a nice hexagon. But we can
connect these up in a nice easy loop can't we? Okay. So now we've got six of the lines, there's three
more to connect; essentially I need to connect the kiln to the storage unit that's opposite on this
hexagon. So let's do this one first, that's a nice easy one to connect. This kiln to this storage
unit; I don't want to cross that track, I can go the long way around, nothing wrong with that. And
now this kiln to this storage unit opposite and I will get stuck here, I will have to cross. Which is
fine, if I go on the outside I am going to have to cross the track or if I go on the inside I'm going
to have to cross one of the tracks. I hope that convinces you that I can't do it without crossing
a track, but I can do it with one, one crossing. So that kind of minimises the number of crossings.
And how can we do this in general? Right, so if you've got let's say K kilns and S storage units,
how can we arrange our factory so that we can minimise the crossings?
You might want to have a think about it but I have an answer for you, I can show you a nice
picture that does solve this- let's have a look. So what you want to do is we're going to try and
kind of draw it uh like a like a graph with an x-axis and a y-axis; I guess a kiln axis and a
storage unit axis. So like this: a horizontal and a vertical. I'm going to put the kilns on
the horizontal axis and I'll try and do half on the left and half on the right - or if it's an odd
number which is fine I'll do as close as I can to half and half. Let's say I got six, so I put three
on the left and three on the right. So that's going to be my kilns like that. And the storage
units I'll put on the vertical axis; and this is how I'd lay out the factory. We're going to avoid
the origin, right there in the middle. That's where we're avoiding, no kilns no storage units there.
Let's say I do 5 just to show you the odd number version of this as well. So 5 I'll do three
above and two below? Yeah. 1, 2, 3 and two below. So I'm claiming that this is a minimum.
Let's take a look, let's see what crossings we're going to get. I'm going to take this kiln by kiln,
I'll just work my way on the left hand side here I think. So let's do this first kiln and I'll uh
connect these three storage units up here. No problem so far, let's do the second kiln. I am
going to get crosses here. I'll do this kiln to the first storage unit, I'm gonna get two crosses,
and connect to that storage unit. Connect to the second storage unit, I've got one cross and then if
I connect to the third storage unit that's not a problem, I can get all the way up. So so far I've got
three. I'll do the final kiln as well; we're gonna get quite a few crosses here, let's try and work
it out. I'm going to connect to the first storage unit: 1, 2, 3, 4- four crosses. And to the
next one: 1, 2 and connect and then to the one at the top - that's not a problem I can just connect.
So I've got another six there so I've got nine crosses all together. So I'm gonna get nine on
this side as well when I connect these three kilns. So on the bottom we're gonna get three and we're
gonna get three down here. So all together how many crosses are we going to get? 9 plus
9 plus 3 plus 3: 24. Well I'm claiming that's a that's the best you can do - 24
crosses. It's certainly that's what we believe that's the best you can do. It's actually not been
proven that that's the best but we haven't found an answer that can do better. We can also write
this down- out as a formula so you don't have to draw the whole thing. So if you want to work it
out you can work this out as a formula; same sort of thinking, the way I showed you how it works. If
you work it out as a formula looks like this: z is the number of crosses, let's say k kilns, s storage
units. Then the formula looks like this: k divided by two - if it's an odd number you can round that
down. Multiplied by k minus 1 divided by two - if that's an odd number you can round that down. And
multiply that by s divided by 2 which we can round down and s minus 1 divided by 2 which we can round
down. So there's symmetry in this, I guess there's no difference really between the kilns and the
storage units, not from a mathematical point of view. So you can see the symmetry in there. We can just
double check our result- - (Brady: Let's do it) - And what did I have, 6 kilns? 5 storage units. So that's going
to be 6 divided by 2 - we might have to round that down. That's going to be 5 divided by 2 and
round that down. Storage units: 5 storage units so that's now a 5 divided by 2, round that
down. And 4 divided by 2, round that down. Well 6 divided by 2 is just 3; multiplied
by- this is 2.5, we round it down to 2. Same here, 2.5 rounded down to 2, and this here that's just
2 that's fine. 3 times 2 times 2 times 2 is 24; which is the answer we've got.
So that is a formula that describes this picture. We think that's the minimum. Not proven, but it does
mean that your number of crosses - if you're in this situation with your kilns and your storage units -
it's going to be this number or smaller. We know that much. So it's this number or better. We think
that's the minimum. - (I can't believe people aren't all over this one. I can't believe it's not like)
(been cracked.) - Yeah so they did think they proved this at one point and that was a proof that people
accepted for 11 years - it's one of those stories when they go, oh yeah, that seems right until someone
noticed a mistake. We know this much: so this minimum number of crosses, it's gonna be less than
my little formula and 83% of that. So we're whittling it down, we're sandwiching it between
these numbers. We're getting there, we're trying- trying to hone in on that number. It has been
proven for some numbers. So it's been proven for uh number of kilns less than or equal to 6 and
storage units as many as you like. So arbitrarily many storage units and 6 kilns or less, we know
that is the minimum. So that has been proven. Or vice versa because it's all symmetric, if you want
to do it the other way around. But for any values, no, we haven't proven that that's the minimum yet.
And there is applications for this apart from building bricks. Yeah you want to use this kind
of idea when you're making computer chips. So you've got your circuitry in your computer
chip, and you don't want them crossing, you want to minimise those crosses because every time those
circuits cross you have to do that in a new layer so that they those circuits don't cross. So it's
important when making things like that. It might be worth talking about um complete graphs as well;
a complete graph is the idea where you have these dots. They're not kilns and storage units anymore,
they're just dots and you want to connect everything to everything else. So if I had like
five dots in a pentagon and I will connect everything to everything else - first of all I
can just connect my pentagon up and then connect all the other lines I haven't done yet. So that's
called a complete graph because you've connected everything to everything. That's got five crossing
points on it - can we minimise that? Same question. So can we minimise that? Yeah you can. So we could have
the high uh five dots in a pentagon like that; and we can draw that out as a pentagon as well.
So let's do our other lines. So we could have one line there; and we could have one line there. I
think we could have one line sort of going out on the outside like that. One line going on the
outside like that. And what am I missing? This point to this point I'm missing - and I have to cross.
So I do have to cross at one point, so that's me minimising the number of crossings, so I can get
it down to 1. So the question is how do you do that in general? And that's connecting everything
to everything. We think we've got an answer to that as well. It's a really nice answer actually;
let's I'll do the 6 version for this. So for- if I wanted to connect everything to everything
for 6 you draw it as a regular polygon. So I'm going to draw a hexagon out. I then draw in my
edges, there you go, and now I need to draw in the remaining lines. This is the rule: if the slope is
positive it goes on the inside of the polygon. So by positive slope I mean something like this that
has a positive gradient okay, it's sloping upwards. This line has a positive gradient so it stays on
the inside, and this line has a positive gradient it stays on the inside. Oh and I should say this
line is also positive, going vertically up, and this line going vertically up is also positive
as well. If your line is zero or negative it goes on the outside. So this point to this point would
be negative, a negative slope, so I'm going to draw it on the outside instead like that. And
this point to this point would be negative so I'm going to draw that on the outside as well.
This point here to this point- so I've only got one line left, it's this point connecting to this point
which would have been your zero and that's going to have to cross on the outside.
There. How many crosses do we have? 3 actually, there's 2 there on the inside and then there's
1 there on the outside. And that again is what we think is the minimum number of crossings for that.
You can write that out as a formula as well. So if you just have n points connecting everything
to everything; for this diagram this is how many crosses it has - it is one quarter of and then we
do a rounding down of n divided by 2, round down n minus 1 divided by 2, round down n minus 2
divided by 2, round down n minus 3 over 2 like that. I did 6 here didn't I? Quarter of
uh 6 over 2 rounded down; 5 over 2 rounding down; 4 over 2 and 3 over 2.
And so it's gonna be a quarter of 3 times that's gonna be 2, that's gonna be a 2 and
that is 1 and a half rounded down which is a 1 which is going to be yeah 3. Which is exactly
what it should be. So that formula is describing that picture; and we think that's the minimum.
Again, it's the same problem. We haven't found a drawing that is better, so we think that's
the minimum. And that's useful to know because that's kind of your worst case scenario. Because
it's everything connecting to everything else; so if you've got a graph which doesn't connect
everything to everything else it's going to be that value or smaller than that value so it's
worth knowing that as well. We have proven that it is a minimum for n less than or equal to 12.
So we do know it's a minimum for that but for the other numbers, still a conjecture.
If you enjoy learning stuff here on Numberphile, well you're gonna love Brilliant. Their custom
made courses, questions, and quizzes will expand your mind and bring a few smiles to your face as
well. Everything's so interactive, meaning you don't just look at a screen, you get hands-on
with the material and there's no better way to learn than that. I don't just enjoy the
knowledge on Brilliant, I like that it has a bit of personality. Sometimes it's quite funny!
This course on math history - well it's a favorite of mine. And by the way brilliant has a 30-day free
trial so you could go and do this course right now. And if you do sign up to their annual premium
subscription there's a 20% discount by visiting brilliant.org/Numberphile. It's never too late
to learn something new; check out Brilliant, there's also a link in the video description.
..for us to be all related to the same ancestors. Now you were saying
this is not true to life, and I agree this is not true to life because in
this example I'm just as likely to have two parents who are from Paris..