nxn grid problem.

theNoodler · #1 $Old$ October 30th, 2009, 10:36 AM

Hello.

I asked about this a while ago, but I'm still unsure. Imagine you have a nxn grid (3x3 for argument). I want to know how I can work out the total number of patterns I can make with 2 colours, say black and white. An example would be:

x = black o = white

ooo xoo xxo
ooo ooo oxx
ooo ooo oxo

So, pattern one is all white, patter two has one bit black etc. I was told for this it would be 2 to the 9th, giving me 512, which can't be correct! Is it 9 squared, giving me 81? What if I had a 6x8 grid, or 17x31 grid?

I did try to host a nicer picture than my x and o, but sadly I can't get imageshack to work.

Many thanks.

N.

Mush · #2 $Old$ October 30th, 2009, 11:18 AM

Quote:

Originally Posted by theNoodler $View Post$

Hello.

I asked about this a while ago, but I'm still unsure. Imagine you have a nxn grid (3x3 for argument). I want to know how I can work out the total number of patterns I can make with 2 colours, say black and white. An example would be:

x = black o = white

ooo xoo xxo
ooo ooo oxx
ooo ooo oxo

So, pattern one is all white, patter two has one bit black etc. I was told for this it would be 2 to the 9th, giving me 512, which can't be correct! Is it 9 squared, giving me 81? What if I had a 6x8 grid, or 17x31 grid?

I did try to host a nicer picture than my x and o, but sadly I can't get imageshack to work.

Many thanks.

N.

An n x n grid with m possible colours has $m^{n \times n}$ possible combinations.

Plato · #3 $Old$ October 30th, 2009, 11:36 AM

Quote:

Originally Posted by theNoodler $View Post$

Imagine you have a nxn grid (3x3 for argument). I want to know how I can work out the total number of patterns I can make with 2 colours, say black and white. An example would be:
So, pattern one is all white, patter two has one bit black etc. I was told for this it would be 2 to the 9th, giving me 512, which can't be correct!

But that is correct.
Look at that attached graph. There are two $3\times 3$ grids.
Are they different colorings?

Maybe not. Rotate I $90^o$ counter-clockwise. We get II.
Now are they different?

If I & II are different then there are $2^9=512$ possible colorings.

If I & II are not different then you must tell us why?

Soroban · #4 $Old$ October 30th, 2009, 11:42 AM

Hello, theNoodler!

Quote:

Imagine you have a $n\times n$ grid (3x3 for argument).
How can I work out the total number of patterns made with 2 colours, say black and white.

An example would be: $\begin{array}{c}X \,=\, \text{black} \\ O \,=\,\text{white}\end{array}$

. . $\begin{array}{c}OOO\\OOO\\OOO\end{array} \qquad \begin{array}{c} XOO\\ OOO\\OOO \end{array} \qquad \begin{array}{c}XXO\\OXX \\ OXO \end{array}\qquad \hdots\text{ etc.}$

I was told for this it would be $2^9 \,=\,512$ , which can't be correct!
. . Why not?

For each of the 9 cells, you have two choices: place a Black or place a White.

So you have 9 decisions with 2 options each.
. . There will be: . $2^9 \,=\,512$ possible choices you can make.

Quote:

What if I had a 6x8 grid grid?

You have 48 cells to fill with 2 options each.

There will be: . $2^{48}$ possible choices.

theNoodler · #5 $Old$ October 31st, 2009, 09:00 AM

Hello.

Thanks for the help. I guess it just doesn't look like there could be that many combinations.

So for a 6x8 grid, there would be 281,474,976,710,656 combinations. That's just nuts.