Problem 44850. X O X O

Created by Rayner Saggers

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>On a noughts and crosses board, how many possible unique combinations are there given a square grid of length n?</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Assumptions/constraints:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>All squares are populated.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Number of naughts and number of crosses can only differ by a maximum of 1. I.E. The game was played until the board was full</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Minimum Grid size (n) = 1x1</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This is a discrete maths question, which can be simplified by focussing on one of the options. If we look at the options for locating just the crosses on the grid, we know that the remaining locations must contain naughts and so similarly for the opposite condition. The maths is relatively simple, and is the solution to \"choose k from n\".</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>19-Feb-19 - Test suite updated to take into account solutions where the opposing player goes first.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

45 Solutions
23 Solvers

Last Solution submitted on Aug 26, 2020

Last 200 Solutions

Problem Comments

3 Comments

3 Comments

Vadim Smirnov on 3 Apr 2019

Rayner, by N do you include odds and even lengths ? what's the minimal length too? Cant imagine a game being fun with just one square )

Rayner Saggers on 8 Apr 2019

By 'n' I mean any length of square grid. You solution should still be valid for a 1x1 grid. (I've now added an extra test script for this case). Though in reality I agree such a game wouldnt be much fun!

https://www.mathworks.com/matlabcentral/cody/problems/44851 adds the dynamic of stopping play when someone wins, though Ciaran's test suite needs fixing before you can attempt this one

Reece Blunt on 30 May 2019

Lovely little problem Rayner, look forward to trying Ciaran's

Solution Comments

Solution 1729999

2 Comments

2 Comments

Martin Vatshelle on 19 Feb 2019

This is a nice problem, but the solution test suit is poor.
To get 126 for n = 3 one need to assume same player always starts.
If either player could start we get more solutions.
I.E. number of solutions with 4 x's and 5 o's + number of solutions with 5 x's and 4 o's

Rayner Saggers on 19 Feb 2019

https://www.mathworks.com/matlabcentral/cody/problems/44851 provides a more challenging extension that asks the user to take into account that games end when there's a "win".

My first attempt at producing a community problem so thanks for the feedback on improving the test suite.

Problem Recent Solvers23

Problem Tags

discrete maths games