I'm gonna start it off with a puzzle. Just, just to get us going
So I've taken the Aces, the Kings, the Queens and Jacks out of a deck of cards
You can see I've arranged them in a 4x4 grid and the puzzle is:
Can you arrange these cards, so that every row, every column, and the two diagonals
have, an Ace, a King, a Queen, a Jack in them
and every row, column, and the diagonals
I also want them to include a club, a heart, a spade and a diamond.
(Brady: It's like a Sudoku)
It is like a sudoku! So try it out - it should be the same kind of thing as a Sudoku. There is a solution.
I'm not trying to catch you out. There are many solutions. So try and find a solution.
How many solutions can you find? My rows are already working?
I've got Ace, King, Queen, Jack in each row and I've got clubs, hearts, spades, diamonds in each row
But my columns don't work. What do I need to do?
This ace can't be in the same column as an Ace, and I don't want to put it there either
I can't have hearts in the same column as hearts. What about if I just swap these two?
over, let's see. Is there anything wrong with that? I don't - oh, I've got my Kings. They're in the same column
So maybe I could swap those two
over if I keep thinking about it. I want my diagonals to be like this as well
I've got a club and a club
Maybe I can swap the Jack and the Queen over and you keep going like this. So you keep trying this out
Swapping them over, seeing what works. If you're like me
You're probably going to find yourself getting into a stuck place at some point where it's just not working
So what I recommend is you do treat it like a Sudoku - do it with pen and paper. I think it works out better
So here's my Sudoku kind of version. I know what the sort of thing I want. I want an ace a
King a
Queen and a Jack in every row, column, diagonal. I want club, heart,
spade, diamond doing the same thing
And so then, yeah
let's just think it through let's do the Aces and let's see where it fits on the next row so it can't be in the
first column. It can't be on the diagonal matching with our ace so it could be in the third or fourth box?
Oh, for no reason let's put it in the third box. Let's see what happens when I do that
If I do that that does help though, I'm gonna look at the fourth row
because I can't do this first column,
I can't do the third column, and I can't do the diagonal either so it can't be in that box at the end
So it has to be there, which means I now know where the last Ace goes. It has to be on the third row,
fourth box. So it's nice and pleasing, in a Sudoku kind of way, and the suits are the same. If I did clubs
It can't be the first column, can't be the diagonal,
it can't be here because I've already got ace of clubs already which means it has to be in the last
box on the row and where else could my clubs go? Err, well, if I look at the fourth row, it's not the first column
it's not the fourth column and it can't be Ace of clubs again. Which puts it there
and then that forces is the last club to go
here, I think; and you just carry on in that way. Here's one of the possible solutions you could do
[Squeaking noises]
So the last row is going to be: we will need the king
We will need the Ace
We will need the Jack and right there in the bottom Queen of Hearts, and that should work. Every row
every column and the two diagonals as well has an Ace, King, Queen and Jack and also one of each suit:
clubs, hearts, spades and diamonds. It's kind of like a Latin square. Latin squares are quite famous
It's kinda like a double Latin square really; a Latin square
I would have four objects and I want these four objects to appear in each row and each column.
It doesn't have to be the diagonals by the way,
diagonals is fun for a puzzle
but it's not going to be what we're going to do for the maths. If I just had them as A, B,
C and D. I want A, B, C and D to be in every row and every column without
matching up so I could have A, B, C, D. A, B, C, D
A, B, C
and D. Right, that's a Latin square. Then, what we're doing is kind of a double Latin square
I could do another Latin square in the same boxes. I'll use the numbers 1, 2, 3 & 4 this time so it looks different
So we can start off with 1, 2, 3 & 4 and then fill in the rest of them
So it's a Latin Square and I want each combination to appear once
only. So if I do the rest of it, it would be 1, 2, 3, 4. 1, 2,
3, 4. 1, 2,
3, 4 like this; so it's two Latin squares and they're kind of superimposed on top of each other, but every combination
occurs once it's called a Greco-Latin square and
It sounds like a pure math thing
has loads of applications in in real life maths and I was taught it in statistics
and it doesn't sound like something you would be taught in statistics, but it is something that you would use when you're designing experiments.
Imagine you're
organizing
Some sort of tournament, errm what a ping-pong tournament. Okay, you got the ping-pong tournament, very exciting.
It's a four-day tournament. All right, it's a big deal, and you've got team
Letters and team Numbers, if I use this, so on the first team, it's A, B, C and D; on the second team it's 1, 2
3 and 4. And let's say your slots for playing games are 8 a.m, 10 a.m
Erm, then there's a 2:00 p.m. slot and a 4:00 p.m. slot. Isn't it a bit unfair if you have to play at 8 a.m?
First thing in the morning, you might not be playing at your best, so it would be fairer if
every player got to play a game at 8 a.m.
If every player got to play one of these slots,
then that would be a fair thing to do and that's what's happened here. It would also be fair if every player
A, B, C, D gets to compete against every player 1, 2, 3, 4 and that's what's happened.
You've arranged the tournament so that every player gets to play each opponent and
every player gets to play in each slot.
So everything's nice and fair, but also it allows you to make comparisons.
Let's say I wanted to compare player A and player C
I can compare them, because both players have played in each slot and
both players have played all the other opponents. So if you add up their total score,
you can tell which is the better player. They use this idea for designing experiments
so there aren't these little hidden biases - so you can arrange your
experiment so that those kind of biases all spread out and everyone had - put in the same in situation.
So then you can make comparisons between two different things. So this works for a 4x4 square,
does it work for other sizes? Okay 2x2 3x3. In fact, it doesn't work for a 2x2 square;
it's too small, just doesn't work. We have A and B and well, let's put A and B here,
I've relaxed the diagonal rule now, and we've got 1 and 2. Now, where am I going to put number 1 here?
I can't put it there cos I've already done this, and I can't put it here because it would be in the same column. You'll
find that you can't do it for a 2x2 square. Too small, It's impossible. You can do it for a 3x3.
So if you've got a prime number size, a nice little rule is: let's start with
A, B, C. Let's take the first Latin square and for each row, I'm gonna advance it one place across.
So now I'm going to start on the second square and it'll be A, B, C. And then for the next row A, B, C.
For my next Latin square, with 1, 2 & 3
I'm going to advance them 2 steps across. So for the next row let's move it 2 steps along. You'll have 1, 2 & 3
And then from the next row, let's go another two steps along
So we go 1, 2 & 3 and you see, 'hey! That works'.
So we've got this Greco-Latin Square, this double Latin square for 3x3. We can do for 5x5 as well, because it's a prime number.
So obviously the next question is: 6x6, does it work for 6x6?
That's difficult. In fact so difficult that
famous mathematician, Euler, got involved.
Err, so it's it's got a special name, because it's a special case. It has a special name,
they call it the 36 officer problem.
So you've got six regiments and each regiment has six officers of different rank,
And you want to arrange them into one of these squares. So you've got different
ranks and different regiments in rows and columns. Euler, near the end of his life, he thought "I'm gonna try this problem out."
He came up with
loads of different
methods for designing
these Greco-Latin squares. All these different algorithms and methods for making them, for
constructing them; and he made
3x3, 4x4, 5x5, 7x7,
he could make 8x8, 9x9. Everything that he tried, failed
for 6x6. And he said "I don't think it can be done. I keep trying. It keeps failing
I've not found a single solution. If there is a solution it's gonna be some kind of crazy
Irregular pattern. I don't think it can be done and I can't see a way of showing it, without just checking every possibility."
So he said, well:
2x2 can't be done.
6x6 can't be done. And for the same reason, he decided,
10x10 squares can't be done.
14x14
squares can't be done. Odd numbers, fine. He could do the multiples of four. So, four, eight and twelve and all that,
That's fine. He could do that.
But all the other even numbers, he couldn't solve. So he conjectured, and it's become a conjecture,
They were impossible, can't be done. And it was a conjecture for a long time.
Well, it was proven
in 1901,
hundred years ago. French mathematician, Gaston Tarry,
he proved it by checking every possibility. Which is 9408
possibilities and
he showed that the 6x6
grid is
Impossible, it can't be done. (Brady: so Euler was right?) So Euler was right!
The 6x6 is impossible, and I want to be fair to Gaston Tarry, he did have a general proof.
He was a proper mathematician, he had a general proof. But he also checked every possibility, which is funnier.
(How did he do it? Because he didn't have computers did he just manually do it?)
He, he manually did it, exactly. So the next question, of course: is 10x10
impossible? Now,
wow, that's gonna be a lot of cases to check - if you want to check those. That was an open problem for a bit longer,
until someone proved that
They're impossible! The, the 10s the 14s, the 18s, the 22s: they're impossible. They can't be done, that was proven in the 1920s.
The proof was wrong.
The proof was wrong - but it went unnoticed
for thirty years until
1959. An Indian mathematician, called Raj Bose, who was working the same kind of area, looked at the proof and went:
That's funny, funny. There's something wrong about that - and
he went: I'm gonna try and construct one of these impossible grids. And he did, mathematically.
He could able construct a
22x22, cos that was one of these that was meant to be impossible.
So this huge grid, double Latin square, and, he could make it. Which shows that, yeah, Euler
was wrong that there was a 22x22 example.
Then, working with other mathematicians and also this was one of the early uses of computers, we're talking about
1950s computers as well. They could get a 10x10
example. Ten lots of two colours, sort of superimposed. It's a beautiful image. And so they had
examples where they where they could construct them! And Euler was wrong, they could do a 10x10,
they could do a 22x22. They called them 'Euler Spoilers'.
I think it's a kind of a joke.
Mmhm kind of a joke, so they had these and then very quickly they could prove it, in general.
10,
14, 18, 22; these ones that were meant to be impossible:
they were *not* impossible. They could prove it. They could be done, now
we have a way to directly construct them and it's quite involved, but we can actually create
these
supposedly impossible grids.
So that means only 2 and 6 is impossible - 2: I'm not surprised by. It's, it's small
It's just too small to work
6, I find surprising, especially cos 3, 4, 5 work
6 doesn't work. It's this really kind of strange one. Really odd one out, and then all the other numbers - work.
So the moral of the story is: even a great mathematician,
one of history's great mathematicians - even someone like Euler - can be wrong.
And of course, never arrange a ping-pong tournament with six team members.
(Brady: Thanks so much for watching this some more footage from this interview on our extras channel - called Numberphile2)
Two Latin squares on top of each other, can we do three? Here's a 4x4.
Let's add another Latin Square to it. So I'm gonna use circles plus
triangles and squares. (Brady: And a huge thank you to those of you who are able to support us on Patreon)
(That support lets us add a few bells and whistles more animations and things like that)
(Some of your names are on the screen at the moment)
(They're playing a bit of ping-pong. And if you go to the numberphile website, you can see the full list of all our supporters.)
(For more information there are links in the video description)
[ping-pong noises]