Hello, everyone!
Last time, I asked you how many different ways are there
to completely fill a noughts and crosses grid,
using four noughts and five crosses--
not including rotations and reflections of the board.
Now I can tell you that the answer is 23.
There are 23 different ways to completely fill
a noughts and crosses grid.
There are a couple of ways to solve this.
One is kind of a brute force way.
The other is more of a mathematician's way,
which is how I did it.
We're going to have a look at both of them.
So before we start worrying about
rotations and reflections,
let's just ask how many ways
can we fill our 3x3 grid,
using four noughts and five crosses?
Well, you've got nine positions and nine objects.
So you're going to fill the first position with a choice of nine objects.
You fill the second position with a choice of eight objects.
The third position you fill with seven objects left,
and you multiply your choices together.
So you're going to get 9 times 8 times
times 7 times 6 times 5
times 4 times 3 times 2 times 1.
That's called nine factorial [9!]--
I'm doing that very quickly
because I have talked about that sort of thing before.
However, we have over counted here.
You see, we can interchange the noughts without changing the grid.
So those four noughts can swap around.
How many ways can I swap those four noughts around?
Four factorial [4!] ways to do that.
So we divide through by four factorial.
We can also interchange the five crosses
between themselves,
and there's five factorial [5!] ways to do that.
So again, we divide by a further five factorial.
So we get the answer 126.
There's 126 grids.
But that does include rotations and reflections,
so now we're going to reduce that number further.
If you take a grid, there are eight ways you can hit it
with rotations and reflections.
That's four rotations--you've got a quarter turn,
a half turn,
three-quarter turns,
and then there's the 'do nothing' rotation.
And there's four reflections--
reflected in the horizontal axis,
the vertical axis,
and the two diagonals.
Now, if every grid produced eight different grids
when you hit it with rotations and reflections,
then what we could do is take that 126 number,
and divide by 8.
Unfortunately, it's not that easy.
Some grids do produce eight different
rotations and reflections.
Some grids only produce four different
rotations and reflections.
And some grids only produce one rotation/reflection.
And when I say one, I just mean
the original grid itself.
Now, all the grids you get
after you hit a grid with rotations and reflections,
all the different grids you get
is called the 'orbit' for that grid.
Now, if we take all the different orbits,
and take all the grids in those orbits,
and add them together,
we should get 126 different grids.
If we take one grid
from each orbit
then we should get all the essentially different grids.
So, not including rotations and reflections.
Now, if we do that,
you should find
and it is just a bit of checking, I'm afraid,
you should find 23 different orbits.
Ten orbits have size 8.
You get eight different grids when you hit them with rotations and reflections.
Eleven orbits have size 4,
and two orbits have size 1 each.
And all together, that adds up to 126 grids.
So that is a bit laborious.
That's your answer--23 orbits.
But let's take a look at the mathematician's way.
So rotations, reflections and orbits--
this is all part of something called 'group theory.'
Group theory is the mathematics of symmetry.
Now, I used the result from group theory
to solve this problem.
I used something called Burnside's Lemma.
Now, to use this Lemma,
you need to know how many grids
are fixed for each rotation and each reflection.
When I say 'fixed,' I mean when you hit it
with a rotation or a reflection,
the grid is unaffected.
It looks the same.
So if I take the 'do nothing' rotation,
then that leaves all grids--126 grids--the same--
unaffected.
If I take a quarter turn,
if it's going to be unaffected,
and look the same,
that means all the corners are going to have to be the same.
All the corners, when I turn it a quarter turn,
have cycled through.
So all the corners will need to be the same,
and there's only two ways you can do that.
So for a quarter turn,
there are only two grids
that remain unaffected.
It's the same for a three-quarter turn.
A half turn is more interesting.
If you take a grid and do a half turn,
how many grids remain fixed--unaffected?
In that case,
the diagonal corners will need to be the same,
and the opposite sides will need to be the same,
and don't forget, we're only using four noughts here--
four noughts, five crosses--
and under those conditions,
you can work out
that there are six grids
that remain unaffected by a half turn.
You can go through a similar sort of thinking
for reflections as well.
For a reflection,
either side of the reflection
will have to look the same,
and if you do that,
you'll find there are 12 grids that remain
unaffected for each reflection.
Now, Burnside's Lemma says
that the number of orbits--and that's the answer we want--
the number of orbits
is equal to
the average number
of fixed grids.
So how many fixed grids do we have?
Well, we add these together,
126 for the 'do nothing,'
we had two grids fixed for the quarter turn,
2 grids fixed for a three-quarter turn,
six were fixed for a half turn,
and 12 for each reflection.
We'll add those together,
but this is an average number we need,
so I'm going to divide by 8, as well,
because there's 8 rotations and reflections.
And you get the final answer,
you get 23.
There are 23 orbits
and I have the final answer,
and I don't have to draw it out!
Now,
that's not obvious, but--first thing, that is not obvious,
and I didn't expect you to know Burnside's Lemma,
that is something you'll meet
probably in the first year of a maths degree at university.
But I thought it would be a good excuse
to show you Burnside's Lemma.
The important thing is,
I didn't have to draw them out.
I did know there were 23 essentially different grids.
When I did try and draw them out,
I found 22, and I couldn't find the last one.
I was going "I know there is 23!
I know I'm missing one."
But it was really hard! I couldn't find this last one.
But I did know that there had to be 23 of them.
And, well--there you have it!
And, as usual--
if you have been,
thanks for watching.