Uncle Shiva has gifted Nikhil a new toy. Uncle Shiva believes in gifting toys with a mathematical flavour and this is no different. This toy consists of a wooden board with wooden pegs. The pegs are arranged in $N$ columns with $3$ pegs in each column. Each peg is coloured Red, Blue or Green.
Nikhil has a set of $N − 1$ elastic bands (i.e. rubber bands). He builds a chain of bands linking column $1$ to column $N$ as follows. He starts by placing a band from a peg in column $1$ to a peg in column $2$. From the peg where the first band ends, he places a second band connecting that peg in column $2$ to a peg in column $3$. Continuing in this way, he places all $N − 1$ bands to connect the $N$ columns.
While building this chain of elastic bands, he is not allowed to connect two pegs at the same position in adjacent columns. So for instance, the second peg on column $i$ cannot be connected to the second peg on column $i − 1$ or the second peg on column $i + 1$. It may be connected to any other peg in those two neighbouring columns.
Uncle Shiva has added a constraint. Nikhil has to arrange the bands so that while mov- ing from column $1$ to column $N$ along the bands, the number of red pegs encountered should be even (i.e. $0$ or $2$ or $4$ or $\ldots$).
Nikhil is way too smart for Uncle Shiva and he can solve this game in a jiffy. Instead, he decides to count the number of ways in which he can solve the game.
Suppose we have $N = 3$ and the colours of the pegs in the $3$ columns are
\begin{array}{|c|c|c|c|} \hline \text{Column} &1 &2 &3\\ \hline \text{Peg 1} &R &B &B\\ \hline \text{Peg 2} &G &G &G\\ \hline \text{Peg 3} &R &R &B\\ \hline \hline \end{array}
That is, the first column has $3$ pegs coloured Red, Green and Red respectively. The second column has 3 pegs coloured Blue, Green and Red respectively and the last one has $3$ pegs coloured Blue, Green and Blue respectively.
One solution is to connect the first peg on column $1$ with the third peg on column $2$ and then connect the third peg on column $2$ with the first peg on column $3$. Writing $P_j$ to refer to $j^{th}$ peg in a column, we may represent such a solution as: $P_1—P_3—P_1$.
The collection of all solutions is enumerated below:
• $P_1—P_3—P_1$
• $P_1—P_3—P_2$
• $P_2—P_1—P_2$
• $P_2—P_1—P_3$
So, the answer for this arrangment is $4$.
Your task is to compute the number of solutions for the following $3$ arrangements of pegs:
\begin{array}{|c|c|} \hline \text{Column} &1 &2 &3 &4 &5 &6\\ \hline \text{Peg 1} &R &R &R &R &G &B\\ \hline \text{Peg 1} &R &G &R &B &B &G\\ \hline \text{Peg 1} &G &G &G &R &R &G\\ \hline \hline \end{array}
\begin{array}{|c|c|} \hline \text{Column} &1 &2 &3 &4 &5 &6\\ \hline \text{Peg 1} &G &G &R &G &B &G\\ \hline \text{Peg 1} &G &R &R &B &G &R\\ \hline \text{Peg 1} &B &B &G &G &R &R\\ \hline \hline \end{array}
\begin{array}{|c|c|} \hline \text{Column} &1 &2 &3 &4 &5 &6 &7\\ \hline \text{Peg 1} &R &G &R &B &B &R &B\\ \hline \text{Peg 1} &G &R &R &G &R &G &R\\ \hline \text{Peg 1} &G &G &G &R &G &R &R\\ \hline \hline \end{array}
The answers are as follows:
- $40$
- $52$
- $96$
I can't figure out how to mathematically compute these.
I was able to code it out, but we have to do it manually because it's part of a written Informatics Olympiad.
(source) (ZIO-2016)
Define the solution counting function $C(c, r, p)$ to be the number of chains ending at column $c$, row $r$, and with total red pegs equal to $p\pmod 2$. Then if the peg at column $c$ and row $r$ is red we have $$C(c, r, p) = \sum_{r' \neq r} C(c-1, r', 1-p)$$ and otherwise we have $$C(c, r, p) = \sum_{r' \neq r} C(c-1, r', p)$$ with suitable base cases. You can easily work along the table filling out those values. E.g. to take the first example case, using subscript for even parity and superscript for odd parity, we have
$$\begin{matrix} R_0^1 & R_1^1 & R_3^1 & R_3^5 & G_7^9 & B_{13}^{19} \\ R_0^1 & G_1^1 & R_3^1 & B_5^3 & B_5^{11} & G_{15}^{17} \\ G_1^0 & G_0^2 & G_2^2 & R_2^6 & R_8^8 & G_{12}^{20} \end{matrix}$$
giving a total count of even parity paths to the last column of $13+15+12 = 40$.