[Guest]

Two kids were playing a game of tic tac toe on a 6x6 board. Neither of them really knew what they were doing, so they just alternated placing X's and O's on a board. It just so happened that at the end of the game, every column and row had exactly three X's and three O's.

This made the kids wonder. How many different possible ways that could have occurred?

55640

but i would love to be proven wrong, because i am not too confident with my answer

[Guest]

If u mean any combination with no rules ...

then 2 ^ 36 combination's ...

so 68,719,476,736 times ...

if u meant 3 of each in each row, column etc ... then NFI lol :-)

[Guest]

here's the way i see it.

x,x,x,o,o,o

x,x,x,o,o,o

x,x,x,o,o,o

o,o,o,x,x,x

o,o,o,x,x,x

o,o,o,x,x,x

lest say we start with this.

any change on the top would need to be reflected on the bottom, and can be done so in one of 3 ways.

o,x,x,o,o,x

x,x,x,o,o,o

x,x,x,o,o,o

x,o,o,x,x,o

o,o,o,x,x,x

o,o,o,x,x,x

o,x,x,o,o,x

x,x,x,o,o,o

x,x,x,o,o,o

o,o,o,x,x,x

x,o,o,x,x,o

o,o,o,x,x,x

o,x,x,o,o,x

x,x,x,o,o,o

x,x,x,o,o,o

o,o,o,x,x,x

o,o,o,x,x,x

x,o,o,x,x,o

since we have 9 items on the top, and they can be done in any order, that's 9! or 362880 *3 = 1,088,640.

[Guest]

hmmm, on second thought...

I realize now that picking 1, then 2, then 3, is the same as picking 3, then 2, then 1.

I'll have to think some more about this.

[Guest]

I think you've got a very clever approach to counting the possibilities, but I just think you've got the counting wrong.

I think there are 3 parts to this.

Your reasoning is that when you change the top-left corner from X to O, you have to balance it. Yes, I agree (and I think it's a very clever approach), but to do this you have to change the top row AND the left column. Assuming you're changing from the top-right 3x3 block and the bottom-left 3x3 block only, that gives 6 options (not 3). That's the first part.

(We can ignore the bottom-right 3x3 block because it can't change anything, and we can ignore the top-left 3x3 block for now because any changes there will be picked up later.)

Now we repeat this logic for each of the 9 X's in the top-left 3x3 block. There are 2^9 possible combinations of X's and O's in that 3x3 block (not 9!). That's the second part, and so it gives us a total of 6 x 2^9 so far.

But we've done all these changes assuming the bottom-right 3x3 block remains fixed with all X's. But in fact there are 2^9 possible combinations within that bottom-right block as well. That's the third part.

So, if my logic is correct, the total is 6 x 2^9 x 2^9.

[Guest]

297200 by brute force calc. I have no idea how to do this with logic.

Dim pos As New List(Of Integer())

Dim Possibilities As Long = 0

' Determine all combinations in each column combinations(6,3)

For n As Integer = 7 To 56 ' any number with three 1's from 000111 through 111000 are possible combinations

Dim a(5) As Integer

Dim c As Integer = 0

For i As Integer = 0 To 5

a(i) = n \ 2 ^ i And 1

If a(i) = 1 Then

c += 1

End If

Next

If c = 3 Then pos.Add(a)

Next

' Try all combinations in each column and then cross check each row

For c1 As Integer = 0 To 19

For c2 As Integer = 0 To 19

For c3 As Integer = 0 To 19

For c4 As Integer = 0 To 19

For c5 As Integer = 0 To 19

For c6 As Integer = 0 To 19

Dim validrows As Integer = 0

For row As Integer = 0 To 5

If pos(c1)(row) + pos(c2)(row) + pos(c3)(row) + pos(c4)(row) + pos(c5)(row) + pos(c6)(row) = 3 Then validrows += 1

Next

If validrows = 6 Then Possibilities += 1

Next

Next

Next

Next

Next

Next

MsgBox(Possibilities)

Edited July 19, 2010 by littlej

[Guest]

55640

nooo! i meant to type in 556400 as my answer.

[superprismatic]

I also wrote a program using completely different logic in my program than littlej had in his.

297200, the same as littlej. So, I'm pretty sure that it's correct.

[Guest]

I also wrote a program using completely different logic in my program than littlej had in his.

297200, the same as littlej. So, I'm pretty sure that it's correct.

well now im convinced that that is the correct answer. but does anyone know how to find it without computer aid?

i tried figuring it out by a method that i'll explain later when i am not so tired.

Edit: and now that we know the answer it might be easier to find logically

Edited July 20, 2010 by klose