3D Tic Tac Toe Puzzle: Count the Winning Lines in a 3x3x3 Cube
Source: Shared by Alok Mittal (Cannan Partners)
Problem:
A 3x3 tic tac toe has 8 "winning lines" (3 horizontal, 3 vertical and 2 diagonals). How many "winning lines" does the 3x3x3 3D tictactoe have? There is a brute force solution, and then there is the aha! solution.Update (23 Oct 2014)
Solution: Posted in comments by Anti, Taz, Javier, Shubham Gupta, Leela. Detailed solution and much more advanced problems in the document http://library.msri.org/books/Book42/files/golomb.pdf
9 per face, 3 per edge, 1 per corner, divide by 2 for symmetry: (9*6 + 3*12 + 8)/2 --> 49
ReplyDeleteReplying to Saket Mishra's comment, # of winning lines = 3*3*8 = 72 - Same double-counting as suyash's 76 - see the breakdown above. Answer: 49. (replied using AI)
Delete24 (8*3 Imagine 3 2D plates stacked horizontally)
ReplyDelete24 (8*3 Imagine 3 2D plates stacked vertically)
4 (Diagonals of the cube)
Total of 52 winning lines
Replying to Doom's comment, Total of 52 winning lines - Both off - the axis-parallel lines get double/triple counted when you stack "plates" in different orientations. Correct count: 27 axis lines + 18 face diagonals + 4 body diagonals = 49. (Reply created using AI)
Delete9 different cross-sections of dimension 1x3x3, each having 8 winning lines, plus 4 body diagonals. Hence, 9*8+4=76.
ReplyDeleteYou're double counting mamy lines
DeleteReplying to suyash's comment, 9 different cross-sections of dimension 1x3x3, each having 8 winning lines - The 76 double-counts: the 9 planar cross-sections each contribute 3+3 axis lines, but every axis-parallel line lies in TWO of your cross-sections (one of each orientation containing it). 9*8 = 72 counts the 27 axis lines twice (54) and the 18 face diagonals once. Unique: 27 + 18 + 4 = 49. (Reply created using AI)
DeleteReplying to Javier Campos's comment, I found this: http://library.msri.org/books/Book42/files/golomb.pdf - Great find - Golomb and Hales's "Hypercube Tic-Tac-Toe" has the general ((n+2)^d - n^d)/2 formula; 3x3x3 is the d=3, n=3 case: (125-27)/2 = 49. (replied using AI)
Delete3 layers each of 3 rt angle faces. Each layer is a 3*3 tic tac toe
ReplyDelete# of winning lines = 3*3*8 = 72
Total- 43
ReplyDelete(24 - When 3 2D tic-tac planes are vertically stacked)
(15 - When 3 2D tic-tac planes are horizontally stacked minus number of winning lines already covered in previous case)
(4 - Diagonal winning lines)
ReplyDeleteFor a simple 2 Dimensional Grid: 3 in x-direction + 3 along y +2 diagonals = 8 solutions
Extending same for 3 Dimensional Grid:
3*3 along x + 3*3along y +3*3 along z + 2*3 diagonals along xy + 2*3 diagonals along xz + 2*3 yz diagonals + 4 other diagonals = 49
I found this: http://library.msri.org/books/Book42/files/golomb.pdf
ReplyDeleteIs it 82 ?
ReplyDelete72 + 4 + 6.
It won't be 82. Lots of repetition in 82.
DeleteReplying to Anonymous's comment, Is it 82 ? 72 + 4 + 6. - No - the 72 already double-counts axis lines (see above), so adding more makes it worse. 49. (replied using AI)
DeleteAnswer should be 49.
ReplyDeleteTop and bottom layer -
_______
|7|3|7|
|3|1|3|
|7|3|7|
_______
mid layer -
_______
|3|1|3|
|1|0|1|
|3|1|3|
_______
each matrix component tells about number of winning lines start/end at that cell.
sum = 98
ans = 98/2 = 49 (same line counted twice, from each cell it can start or end)
Winning lines will always be in direction along with x,y,z axis or 45 aligned from them .
how did you get the number 98?
DeleteReplying to Shubham Gupta's comment, Answer should be 49. - Correct - and your per-cell table is the hands-on version of the 5^3-3^3 shell trick. (Reply created using AI)
DeleteAnswer should be 49.
ReplyDeleteTop and bottom layer -
_______
|7|3|7|
|3|1|3|
|7|3|7|
_______
mid layer -
_______
|3|1|3|
|1|0|1|
|3|1|3|
_______
each matrix component tells about number of winning lines start/end at that cell.
sum = 98
ans = 98/2 = 49 (same line counted twice, from each cell it can start or end)
Winning lines will always be in direction along with x,y,z axis or 45 aligned from them .
76.
ReplyDelete8 winning lines * 9 cross sections + 4 body diagonals
48 (8*6 faces) + 13 (26 points touching center and 2 will form a line with center) = 61 total
ReplyDeleteReplying to ankit's comment, 48 (8*6 faces) + 13 (26 points touching center and 2 will form a line with center) = 61 total - The center-containing lines are part of the 49 too, not extra: 27 axis lines + 18 face diagonals + 4 body diagonals. The face and center counts overlap. (Reply created using AI)
Delete49
ReplyDeleteReplying to Leela Prabhu's comment, 49 - Correct. The shell method counts each winning line from both endpoints (98 total), then divides by 2, so there are 49 distinct lines. (Reply created using AI)
DeleteThis is a very interesting question i must say.
ReplyDeleteOne may compute the answer as 49 or 76 by two different approaches. Which one is correct, becomes a new question
I first computed 76 as the obvious answer: (8 winning lines per face) x (3 faces per direction) x (3 directions) + (4 Body diagonals) = 76
Then I looked at the approach of 49 as answer very easily illustrated in answer by Shubham Gupta which seems to be correct too.
So again 49 vs 76. Which is it. Take your pick!
Now think a bit carefully.
When one counts 76 winning lines, one considers many repetitions.
Focus on the front-top-left cube piece. When we count 76 winning lines, we count it three times.
Think it in the same way as a rubic cube has 27 pieces ( hence our tic-tac-toe has only 27 possible places to make a move) whereas it has 9*6 coloured stickers.
So when we consider 76 lines we are considering the stickers which is incorrect.
Replying to Anti's comment, 9 per face, 3 per edge, 1 per corner, divide by 2 for symmetry: (9*6 + 3*12 + 8)/2 = 49 - Correct. A neat way to see the same endpoint count: extend the 3x3x3 board to a 5x5x5 cube. Its outer shell has 5^3 - 3^3 = 98 cells, which are the endpoints of the winning lines; each line has two endpoints, so there are 98/2 = 49. (Reply created using AI)
ReplyDeleteReplying to Anonymous's comment, It won't be 82. Lots of repetition in 82. - Right. (Reply created using AI)
ReplyDeleteReplying to Unknown's comment, 76. 8 winning lines * 9 cross sections + 4 body diagonals - Double-counting - see the reply to suyash above. 49. (Reply created using AI)
ReplyDeleteReplying to Archit Gupta's comment, One may compute the answer as 49 or 76 by two different approaches - Exactly the right way to settle it - the 76 count repeats every axis-parallel line. Glad the two approaches reconciled to 49. (Reply created using AI)
ReplyDelete