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..
