Today, I want to tell you about a problem devised by Hungarian mathematician Pál Turán during World War II, when he was forced to work in a brick-making factory. His job was to load the bricks onto a trolley and run it on tracks to the storage units. The problem was that when the tracks crossed, the trolleys would jump the tracks, causing the bricks to spin and creating a disaster. This inspired Turán to think of a way to design the brick-making factory to minimize the number of crossings.

Let’s say we had one kiln and two storage units. We could easily run a track connecting the kiln to every storage unit. But if we had two kilns and two storage units, we would have to connect the kilns to every storage unit, resulting in a crossing point. To solve this, we could either run a loop or put the kilns and storage units in a circle.

The first interesting example is three kilns and three storage units. We can connect them together, but it results in seven crossing points. To solve this, we could put them in a hexagon and connect them in a loop. This would result in one crossing point, minimizing the number of crossings. This is  2.5, we round it down to 2.So 3 multiplied by 2,  multiplied by 2, multiplied by 2 is going to be 24. 

If you have K kilns and S storage units, you can arrange them to minimise crossings in the following way:

  1. Put the kilns on the horizontal axis, with half on the left and half on the right (or as close to half and half as possible).
  2. Put the storage units on the vertical axis, avoiding the origin (no kilns or storage units there).
  3. Connect the kilns to the storage units.

The formula for calculating the minimum number of crossings is:

z = (K/2) * (K - 1/2) * (S/2) * (S - 1/2)

where K is the number of kilns and S is the number of storage units.

For example, if you have K = 6 kilns and S = 5 storage units, then the minimum number of crossings is 24. So that’s the rule: if it’s positive it goes on  the inside.So this one is positive, this one is   positive, this one is positive, this one is positive,  this one is positive, this one is positive.So I’m  gonna draw those in on the inside.So this one  goes in here, this one comes in here, this one   comes in here, this one comes in here, this one  comes in here and this one comes in here.So I’m  now done, I’m now done.I’ve got all my crossings  on the inside and I’ve got no crossings on the   outside.So that’s the minimum number of crossings  for the 6 version.So that’s the answer for the 6  version and we think that’s the answer for the  arbitrarily many version as well.So we think that’s  the minimum number of crosses that you need for  arbitrarily many kilns and arbitrarily many storage units. 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 also 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.