2
$\begingroup$

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!

$\endgroup$
4
  • 1
    $\begingroup$ You can have say only the top left corner light and the right middle light on. They are not adjacent, but this pattern is not counted in your method since the two lights are not from the same checkerboard pattern. $\endgroup$ Commented Feb 7, 2021 at 21:57
  • 1
    $\begingroup$ @JaapScherphuis oh man I feel so silly. Thank you. So then I get $2\times 4+2\times 4=16$ additional ones, totalling to $63$ $\endgroup$
    – Lac
    Commented Feb 7, 2021 at 21:59
  • $\begingroup$ @Lac we are different than a traditional forum. Here, if you find a solution, you are encourage to self-answer (go to the answer box at the bottom of the page and type up an answer there) instead of editing the question. That way questions are questions and answers are answers. $\endgroup$
    – bobble
    Commented Feb 7, 2021 at 22:19
  • $\begingroup$ @bobble Ok no worries, I answered $\endgroup$
    – Lac
    Commented Feb 7, 2021 at 22:33

2 Answers 2

4
$\begingroup$

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}$$

$\endgroup$
1
  • $\begingroup$ Thank you for a good self-answer! In a few days (I think 2) you can accept this answer to indicate that it solved your problem satisfactorily. $\endgroup$
    – bobble
    Commented Feb 7, 2021 at 22:35
0
$\begingroup$

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}$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.