MathFun4Kids

Solution 1: Overall, there are total $2^9=512$ combinations when the light bulbs are turned blue or red randomly. The problem can be divided into following cases, depending on the number of light bulbs turning blue, for satisfying the requirement that the color of each bulb will be the same as at least one of the two adjacent bulbs on the circle.

Case 1: The number of the blue bulbs is $0$. There is only $1$ way to arrange the bulbs to satisfy the requirement:

Case 2: The number of the blue bulbs is $1$. There is $0$ way to arrange the bulbs to satisfy the requirement, as the color of the two adjacent bulb of the blue bulb is red.

Case 3: The number of the blue bulbs is $2$. These two blue bulbs must be next to each other, and there are $9$ ways to arrange the bulbs to satisfy the requirement:

Case 4: The number of the blue bulbs is $3$. These three blue bulbs must be next to each other, and there are $9$ ways to arrange the bulbs to satisfy the requirement:

Case 5: The number of the blue bulbs is $4$. This can be divided into the following sub-cases:

Case 5.1: If the $4$ blue bulbs are arranged to be next to each other and there are $9$ ways to arrange the bulbs to satisfy the requirement:

Case 5.2: If there are only $3$ blue bulbs are arranged to be next to each other, There is $0$ way to arrange the bulbs to satisfy the requirement, as the color of the two adjacent bulb of the remaining blue bulb is red.

Case 5.3: If the $4$ blue bulbs are arranged to $2$ groups, and each group contains $2$ blue blubs that are arrange to be next to each other. There must be $2$ or $3$ red blubs in-between these $2$ groups. There are $9$ ways to arrange these $5$ red bulbs in order to satisfy the requirement:

Case 6: If there are $5$, $6$, $7$, $8$, and $9$ blue bulbs, there are $4$, $3$, $2$, $1$, and $0$ red bulbs, which would be same for case 1, 2, 3, 4, and 5.

Therefore, the number of arrangement of $9$ light bulbs satisfying the requirement is $$2\cdot(1+9+9+9+9)=74$$

The probability that the color of each bulb will be the same as at least one of the two adjacent bulbs on the circle is $$\dfrac{74}{512}=\dfrac{37}{256}$$ Therefore $m=37$, $n=256$, and $$m+n=37+256=\boxed{293}$$

Solution 2: Let $n$ be the number of light bulbs on the circle. There will be $2^n$ combinations when the light bulbs are turned blue or red randomly. We try to examine combinations $f(n)$ satisfying the requirement that the color of each bulb will be the same as at least one of the two adjacent bulbs on the circle.

If a red blub is assigned as bit $0$, and a blue blub as bit $1$. There will be $2^n$ $n$-bit binary numbers. In order to satisfy the requirement, the binary number meets all the following conditions:

1. It cannot contain a sequence of $101$, nor $010$

2. It cannot start with $01$ and end up with a $1$

3. It cannot start with $10$ and end up with a $0$

4. It cannot starts with a $1$ and end up with $10$

5. It cannot starts with a $0$ and end up with $01$

$$ \begin{array}{|c|c|c|c|} \hline n & 2^n & f(n) & f(n-1)+f(n-2) & g(n)=f(n)-(f(n-1)+f(n-2)) \\ \hline 1 & 2 & 2 & & \\ \hline 2 & 4 & 2 & & \\ \hline 3 & 8 & 2 & 4 & -2 \\ \hline 4 & 16 & 6 & 4 & 2 \\ \hline 5 & 32 & 12 & 8 & 4 \\ \hline 6 & 64 & 20 & 18 & 2 \\ \hline 7 & 128 & 30 & 32 & -2 \\ \hline 8 & 256 & 46 & 50 & -4 \\ \hline 9 & 512 & 74 & 76 & -2 \\ \hline 10 & 1024 & 122 & 120 & 2 \\ \hline 11 & 2048 & 200 & 196 & 4 \\ \hline 12 & 4096 & 324 & 322 & 2 \\ \hline 13 & 8192 & 522 & 524 & -2 \\ \hline 14 & 16384 & 842 & 846 & -4 \\ \hline 15 & 32768 & 1362 & 1364 & -2 \\ \hline 16 & 65536 & 2206 & 2204 & 2 \\ \hline 17 & 131072 & 3572 & 3568 & 4 \\ \hline 18 & 262144 & 5780 & 5778 & 2 \\ \hline 19 & 524288 & 9350 & 9352 & -2 \\ \hline 20 & 1048576 & 15126 & 15130 & -4 \\ \hline \end{array} $$

Therefore

$$ f(n)=\left\{ \begin{array}{crl@{\qquad}l} 2 & n=1 & \\ 2 & n=2 & \\ f(n-1)+f(n-2)+g(n) & n\ge 3 \\ \end{array} \right. \ \ \ \ \ \ g(n)=\left\{ \begin{array}{crl@{\qquad}l} -2 & n=1 & \\ -4 & n=2 & \\ g(n-1)-g(n-2) & n\ge 3 \\ \end{array} \right. $$ $$ Or \ \ \ g(n)=\left\{ \begin{array}{rcl@{\qquad}l} -2 & (n-1)\pmod{6}\equiv 0 & \\ -4 & (n-1)\pmod{6}\equiv 1 & \\ -2 & (n-1)\pmod{6}\equiv 2 & \\ 2 & (n-1)\pmod{6}\equiv 3 & \\ 4 & (n-1)\pmod{6}\equiv 4 & \\ 2 & (n-1)\pmod{6}\equiv 5 & \\ \end{array} \right. $$

The probability that the color of each bulb will be the same as at least one of the two adjacent bulbs on the circle is $$p(n)=\dfrac{f(n)}{2^n}$$

Proof: For $n=1$, we have $2$ possible binary strings, as $0$, and $1$. We have $f(1)=2$ as none of the $2$ possible binary strings containing $010$ or $101$.

For $n=2$, we have $4$ possible binary strings, as $00$, $01$, $10$, and $11$. We have $f(2)=4$ as none of the $4$ possible binary strings containing $010$ or $101$.

When $n=3$, there are $8$ possible binary strings, as $000$, $001$, $010$, $011$, $100$, $101$, $110$, and $111$. Excluding $010$ and $101$, we have $f(3)=6$.

Therefore, $f(n)=f(n-1)+f(n-2)$ when $n=3$.

For a binary string of length $n$ that does not contain a sub-string as $010$ nor $101$, the string can end up with a suffix as $00$, $01$, $10$, or $11$. Let $a(n)$, $b(n)$, $c(n)$, and $d(n)$ be the number of strings with length as $n$ that end up with a suffix as $00$, $01$, $10$, and $11$ respectively. Therefore $$f(n)=a(n)+b(n)+c(n)+d(n)$$ Additionally, we have the following relationships:

$$ \begin{array}{rcl} a(n)&=&a(n-1)+c(n-1)\\ b(n)&=&a(n-1)\\ c(n)&=&d(n-1)\\ d(n)&=&b(n-1)+d(n-1)\\ \end{array} $$

Therefore

$$ \begin{array}{rcl} f(n)&=&a(n)+b(n)+c(n)+d(n)\\ \ &=&(a(n-1)+c(n-1))+a(n-1)+d(n-1)+(b(n-1)+d(n-1))\\ \ &=&(a(n-1)+b(n-1)+c(n-1)+d(n-1))+(a(n-1)+d(n-1))\\ \ &=&f(n-1)+((a(n-2)+c(n-2))+(b(n-2)+d(n-2)))\\ \ &=&f(n-1)+(a(n-2)+b(n-2)+c(n-2)+d(n-2))\\ \ &=&f(n-1)+f(n-2)\\ \end{array} $$

Combining with the case when $n=3$, it is proved that $\boxed{f(n)=f(n-1)+f(n-2)}$.

Solution 1: The problem is equivalent to write $8$ as the sum of at least three positive integers.

Case 1: There are $8$ $1$s in the sum, i.e. $1+1+1+1+1+1+1+1$. There is only $1$ way.

Case 2: There are $6$ $1$s in the sum, i.e. $1+1+1+1+1+1+2$. There are $7$ ways.

Case 3: There are $5$ $1$s in the sum, i.e. $1+1+1+1+1+3$. There are $6$ ways.

Case 4: There are $4$ $1$ in the sum, with the following sub-cases:

Case 4.1: For sum as $1+1+1+1+4$, there are $5$ ways.

Case 4.2: For sum as $1+1+1+1+2+2$, there are $\dfrac{6!}{4!\cdot 2!}=15$ ways.

Case 5: There are $3$ $1$s in the sum, with the following sub-cases:

Case 5.1: For sum as $1+1+1+5$, there are $4$ ways.

Case 5.2: For sum as $1+1+1+3+2$, there are $\dfrac{5!}{3!\cdot 1!\cdot 1!}=20$ ways.

Case 6: There are $2$ $1$s in the sum, with the following sub-cases:

Case 6.1: For sum as $1+1+6$, there are $3$ ways.

Case 6.2: For sum as $1+1+4+2$, there are $\dfrac{4!}{2!\cdot 1!\cdot 1}=12$ ways.

Case 6.3: For sum as $1+1+3+3$, there are $\dfrac{4!}{2!\cdot 2!}=6$ ways.

Case 6.4: For sum as $1+1+2+2+2$, there are $\dfrac{5!}{2!\cdot 3!}=10$ ways.

Case 7: There are $1$ $1$s in the sum, with the following sub-cases:

Case 7.1: For sum as $1+5+2$, there are $6$ ways.

Case 7.2: For sum as $1+4+3$, there are $6$ ways.

Case 7.3: For sum as $1+3+2+2$, there are $\dfrac{4!}{1!\cdot 1!\cdot 2!}=12$ ways.

Case 8: There is no $1$s in the sum, with the following sub-cases:

Case 8.1: For sum $2+2+2+2$, there is only $1$ way.

Case 8.2: For sum $2+2+4$, there are $3$ ways.

Case 8.3: For sum $2+3+3$, there are $3$ ways.

Combining all the above cases, the answer to the question is:

$$1+7+6+5+15+4+20+3+12+6+10+6+6+12+1+3+3=\boxed{120}$$

Solution 2: The problem is equivalent to write $8$ as the sum of at least three positive integers, which is the same as placing $8$ identical balls into $n$ unique boxes, where $n=3,4,5,6,7,8$.

Case 1: Place 8 $1$s into $8$ different boxes, with each box contains at least $1$s. There is only ${{8-1}\choose{8-1}}=1$ way.

Case 2: Place 8 $1$s into $7$ different boxes, with each box contains at least $1$s. There are ${{8-1}\choose{7-1}}=7$ ways.

Case 3: Place 8 $1$s into $6$ different boxes, with each box contains at least $1$s. There are ${{8-1}\choose{6-1}}=21$ ways.

Case 4: Place 8 $1$s into $5$ different boxes, with each box contains at least $1$s. There are ${{8-1}\choose{5-1}}=35$ ways.

Case 4: Place 8 $1$s into $4$ different boxes, with each box contains at least $1$s. There are ${{8-1}\choose{4-1}}=35$ ways.

Case 5: Place 8 $1$s into $3$ different boxes, with each box contains at least $1$s. There are ${{8-1}\choose{3-1}}=21$ ways.

Combining all the above cases, the answer to the question is:

$$1+7+21+35+35+21=\boxed{120}$$

Solution 3: The problem is equivalent to write $8$ as the sum of at least three positive integers. The total ways of writing $8$ as the sum of any positive integers, without any restrictions, including singleton, is $2^{8-1}=128$, as there are at most $8-1=7$ plus signs $(+)$ that can be used in a sum.

There is $1$ way to write $8$ as the sum of only one positive integers (singleton). And there are $7$ ways to write $8$ as the sum of only two positive integers.

Therefore, by complementary principle, the answer to the question is: $$128-1-7=\boxed{120}$$

Solution: Since $2$ players do not want to be benched, they must be included in the starting lineup. Therefore, the other $4$ players in the starting line-up must be selected from the remaining $6$ players, including those $2$ players who do not want to be captain, vice-captain, or goalie.

Case 1: If none of the two players who do not want to be captain, vice-captain, or goalie is selected.

The total number of ways to form the starting lineup would be $$6!=720$$ as no restrictions will be applied to the positions.

Case 2:If we select one of two players who do not want to be captain, vice-captain, or goalie to be in the starting lineup.

There are $2$ ways to select one of the above two to be one of the $3$ unique field players.

Additionally, $3$ additional players will be selected from the remaining 4 players who do not have any restrictions. These $3$ players plus the other $2$ players who do not want to be on the bench will have $5!$ permutations for the starting lineup.

Therefore, the total number of ways is $$ {{2}\choose{1}}\cdot {{3}\choose{1}}\cdot{{4}\choose{3}}\cdot 5!=2\cdot 3\cdot 4\cdot 120=2880$$

Case 3: If we select both two players who do not want to be captain, vice-captain, or goalie to be in the starting lineup.

There are $3$ ways to select $2$ positions from the $3$ unique field players for the above two players with $2!$ permutations.

The remaining $2$ players will be selected from the $4$ players without restriction. These $2$ players plus the $2$ players who do not want to be on the bench will have $4!$ permutations for the starting lineup.

Therefore the total number of ways is: $${{3}\choose{2}}\cdot 2! \cdot {{4}\choose{2}}\cdot 4!=3\cdot 2\cdot 6\cdot 24=864$$

Combining the above $3$ cases, the answer to the question is $$720+2880+864=\boxed{4464}$$