Lightbulbs in a 3×3 square

Question

Suppose we have a $3\times 3$ arrangement of lightbulbs and we switch them on/off randomly (probability $½$). What is the probability the no adjacent bulbs are on?

My attempt was:

Let $1= $ on and $0 =$ off. Then these are the only arrangements with both no adjacent $0$s or $1$s:

$$\pmatrix{ 0&1&0 \\ 1&0&1 \\ 0&1&0}\qquad\pmatrix{ 1&0&1 \\ 0&1&0 \\ 1&0&1} $$ Therefore the arrangements in which there are "either no adjacents, or only $0$-adjacents", are those obtained from the arrangements above and turning $1$s into $0$s, which happens in $2^4 + 2^5 - 1 = 47$ ways (the $-1$ being for overcounting the all-$0$ arrangement). But the condition "either no adjacents, or only $0$-adjacents" is equivalent to "no $1$-adjacents". So I get: $$\frac{47}{512}$$ Apparently this is wrong, but I'm having trouble seeing what I've missed. I'd love some help!

Answer 1

I solved this thanks to the help in the comments. There are additional cases given by (up to rotation): $$\pmatrix{\color{red}{\bullet} & \color{blue}{\bullet} & 0 \\ 0 & 0 & \color{red}{\bullet} \\ \color{blue}{\bullet} & \color{red}{\bullet} & \color{blue}{\bullet}}$$ The only new cases are these (up to rotation and symmetry): $$\pmatrix{\color{red}{1} & 0 & 0 \\ 0 & 0 & \color{red}{1} \\ 0 & \color{red}{1} & 0}\qquad \pmatrix{\color{red}{1} & 0 & 0 \\ 0 & 0 & \color{red}{1} \\ 0 & 0 & 0}\qquad \pmatrix{0 & \color{blue}{1} & 0 \\ 0 & 0 & 0 \\ \color{blue}{1} & 0 & \color{blue}{1}}$$ The first gives of $4$ by rotation, the second gives us $2\times 4$ by rotation an axial symmetry, and the third gives us $4$ by rotation. So in total $63$ arrangement, giving: $$\frac{63}{512}$$

Answer 2

Here is another solution.

• If the center square is a 1, then all four middle-edge squares must be 0; then the four corners can each be 0 or 1 independently, leading to $2^4=16$ configurations.
• If the center square is a 0, then we are counting the number of cyclic bitstrings of length 8 with no two consecutive 1s. The number of cyclic bitstrings of length $n$ with no two consecutive 1s is known* to equal $F_{n+1}+F_{n-1}$, where $F_k$ is the $k$th Fibonacci number. Therefore the number of such configurations is $F_9+F_7 = 34+13=47$.

Together these account for all $16+47=63$ configurations.

*Consider a particular bit in a cyclic bitstring of length $n$.

• If it equals 0, then the remainder forms a (noncyclic) bitstring of length $n-1$ with no two consecutive 1s, the number of which is known to equal $F_{n+1}$.
• If it equals 1, then its two neighbors must equal 0; then the remainder forms a (noncyclic) bitstring of length $n-3$ with no two consecutive 1s, the number of which is $F_{n-1}$.