Maths Problem: Complete Noughts and Crosses (Burnside's Lemma)

How many ways are there to complete a noughts and crosses board - an excuse to show you a little bit of Group Theory. Rotations, reflections and orbits - oh my!

[otonanoC]

Dear Dr. Grime,

Please make a video about yourself as a working mathematician. I'm very curious to know : what was your area of expertise in your graduate studies?

[morani]

singingbanana, you are my new hero! Finally someone who really loves mathematics.

[odynhros]

it´s either the feeling i learned something or your super british accent that calms me alot when watching your videos....very entertaining

[singingbanana]

XXX
OOO
XOX

Because I was trying to draw them out systematically, I did all the grids with an O in the top left corner first, but that made this grid the hardest to find.

[singingbanana]

Thank you for the problem. There were some very good solution to the original video, some were better than mine - but this is how I did it, and it was a good excuse to show some higher maths.

[Faladrin]

I find the easiest way to draw out all 23 boards is by classifying them into groups based on how many corners have naughts in them (and in the cases where 2 corners have naughts if the two corners are on a diagonal line from each other or not).  

The break down comes to this:

4 corners contain naughts = 1 board
3 corners contain naughts = 3 boards
2 corners contain naughts along a diagonal = 4
2 corners contain naughts not along a diangonal = 7
1 corner contains a naught = 6
0 corners contain a naught = 2

[modus_ponens]

This video has been one of the most interesting videos I have seen past month. Keep it up!

[smallgingerskater]

This was a great problem! Even as a 2nd year maths student who did an entire module on group theory last year, this was fun to watch and even better to solve! Keep up the great videos. :)

[uberparagon]

I've been thinking about trying to give an undergraduate colloquium about burnside's lemma, my favorite result from group theory. This is a great example! Thanks!

[tipstk]

The funny thing is that my teacher just explained a similar application of orbits of group actions yesterday! I couldn't stop smiling when I realise it was related with your problem

[singingbanana]

Well that's up to the lecturer. The proof is only a few lines once you've done the orbit-stabilizer theorem.

[kimfjeld]

Of all the 23 grids there are 17 legal grids, that is grids that don't end with a paradoxical result.

Of the 17 legal grids there are 12 grids where X win, but only 1 grid for O.

To make mattera worse for O: if the X-player choose the central square at the start of the game (or at any point for that matter), O will never be able to win in the "late game".

The visual display of grid configurations prove the huge advantage given to X in terma of winning and why O should always play for a draw.

[TheSwircle]

LOVE it!  One summer, whilst I was teaching probability in an Algebra II class, a student asked me if we could instead just play tic-tac-toe all day.  Well, instead of playing tic-tac-toe, we analyzed it in much this manner.  Classic moment.  lol  ~_~

[fractuz]

I actually thought of Burnside's Lemma on this on and got it right the first time! To be honest though that doesn't say much because it's my favourite tool in combinatorics and I jump at any possibility I get to use it. :D

[kjellman]

Thank you. Even though I read your comment a bit too fast for my own good you reminded me of this: "So since we first increase X by a number (30 % of X) and then decrease it by a larger number (30 % of Y) we end up with a number that is smaller than our original X." My mind is now at peace.

[Snakecharmer]

james, i have to say, i think ive learned more from watching you than i have learned in school lol ive told my geometry teacher about some of the cools things i saw by you and the numberphile team, and she was surprised lol

[JimmyLundberg]

Is this related to the Lemma's Sideburns theorem? After some quick googling I've realized Daniel Lemma has never had sideburns. Maybe Lemma used Occam's razor to solve his sideburn issue? Ahh, so many questions and so little time.

[Anteaterking]

Only a few month's ago, I did a presentation on Burnside's Lemma (Or more accurately NOT Burnside's Lemma), albeit with cube vertex colorings and such instead of Tic-Tac-Toe boards.

Great video, I've been watching ones across some of the channels you're involved with for the last day or so.

[richardxu]

That's one of the hardest theorems you need to know for high school competitions...

[Chugalg]

Holy Crap. 23 has been my favorite number for a long time now. This is amazing.