2
$\begingroup$

The line - codes we are looking at consist of black and red lines. These lines can have width 1 or 2. Black and red lines are taking turns, black line, red line, black line, ... The code ends and begins with a black line (width 1 or 2). The width of the full code is 14.

Question:

How many codes are possible ? Give a proof.

Example: enter image description here

$\endgroup$
  • 3
    $\begingroup$ This is just a normal combinatorics problem. It belongs on math.stackexchange.com, not here. $\endgroup$ – BlueRaja - Danny Pflughoeft Jun 22 at 20:39
6
$\begingroup$

Let $R(n)$ be the number of codes of total width $n$, so the question asks for $R(14)$.

Consider any code that contains at least $3$ stripes. You can strip off the last two stripes, and still have a valid code that begins and ends in a black stripe, and conversely any valid code can be extended by appending a red and a black stripe to it. The two stripes can be of width $\color{red}{1}+1$, $\color{red}{1}+2$, $\color{red}{2}+1$, or $\color{red}{2}+2$. This means that the $R(n)$ satisfies the recurrence relation: $$R(n)=R(n-2)+2R(n-3)+R(n-4)$$ It is fairly obvious that $$R(0)=0\\R(1)=1\\R(2)=1\\R(3)=1\\R(4)=3$$ We can simply extend the sequence by applying the recurrence relation: $$0, 1, 1, 1, 3, 4, 6, 11, 17, 27, 45, 72, 116, 189, 305, 493, 799, ...$$ So $R(14)=305$.

Some additional maths: If there were no colours, so that the codes could have any number of stripes, then the sequence would be the Fibonacci numbers. In this case you almost have a Fibonacci sequence too, as each term is at most one away from being the sum of the previous two terms. In fact, $$R(n)=R(n-1)+R(n-2)+c_n$$ where $c_n$ is $-1$, $1$, or $0$, when $n$ is $0$, $1$, $2$ modulo $3$ respectively.
The ratio of successive terms is the golden ratio, just like Fibonacci. If you look at the associated polynomial, $x^4=x^2+2x+1$, it has the roots $\phi$, $1/\phi$, (like Fibonacci) but also the complex roots $\omega$ and $\omega^2$ which causes those offsets of $-1$, $0$, and $1$.

$\endgroup$
  • $\begingroup$ Note that the polynomial reduces to (x^2)^2 = (x+1)^2. If the code has n colors in sequence, the characteristic polynomial becomes (x^2)^n = (x+1)^n, providing additional roots. $\endgroup$ – AxiomaticSystem Jun 30 at 14:11
3
$\begingroup$

There are:

$305$ ways to do this.

Proof:

Each code belongs to one of the following generating functions.
$$\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}$$ $$\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}$$ $$\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}$$ $$\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}\color{red}{(x+x^2)}\color{black}{(x+x^2)}$$

Now:

Each generating function must contain a certain number of $x^2$ (regardless of color) to hit a code length of $14$. Hence the answer is:
$$\binom{7}{7}+\binom{9}{5}+\binom{11}{3}+\binom{13}{1}=1+126+165+13=305$$

$\endgroup$
  • $\begingroup$ I have an other solution with a little bit more codes. $\endgroup$ – Matti Jun 22 at 10:58
  • 2
    $\begingroup$ 9; 5 = 126 not 105, if you sum that up correctly then you get the same result as Jaap Scherphuis. $\endgroup$ – Bodo Thiesen Jun 22 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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