0
$\begingroup$

A friend of mine asked me this puzzle few days back. I have been trying to solve this. I tried it by doing manually creating possible pairs of yellow & blue ribbons But I am sure there has to be a more structured approach to solve this. Any guidance of same will be hugely appreciated - even suggestion of approach is also just fine!

There are 10 poles placed in ground in a straight line and on each pole, one ribbon needs to be tied. You have a box full of Blue and Yellow Ribbons (you can consider infinite yellow & blue ribbons for that matter). Rules of the game are:

  1. Only one ribbon needs to be tied on each pole
  2. At least one ribbon needs to be tied on each pole
  3. No more than two adjacent poles can have Blue ribbon on them

In how many ways can the combination blue & yellow ribbons be tied on the poles?

Some examples of allowed & not allowed combinations :

  1. B Y Y Y B B Y Y Y B - Allowed (One ribbon on each pole and No more than two adjacent poles have Blue ribbon)
  2. Y Y Y Y Y Y Y Y Y Y - Allowed (One ribbon on each pole and No more than two adjacent poles have Blue ribbon)
  3. Y Y B B B Y Y B B Y - Not Allowed (As more than two adjacent poles - 4,5,6 have Blue ribbon)
  4. B Y B Y B Y B Y B Y - Allowed (One ribbon on each pole and No more than two adjacent poles have Blue ribbon)
  5. B B Y Y B B Y B B Y - Allowed (One ribbon on each pole and No more than two adjacent poles have Blue ribbon)
  6. B B B B B B B B B B - Not Allowed (As more than two adjacent poles have Blue ribbon)

Thanks in advance!

$\endgroup$
4
$\begingroup$

Let $T_n$ denote the number of "good" strings of length $n$.

Let $A_n$ denote the number of "good" strings of length $n$ which end in $Y$.

Let $B_n$ denote the number of "good" strings of length $n$ which end in $YB$ ($B_1=1$).

Let $C_n$ denote the number of "good" strings of length $n$ which end in $YBB$ ($C_2=1$).

Then $$T_n=A_n+B_n+C_n$$

Recursively, we note that $$A_n=T_{n-1}\;\;\&\;\;B_n=A_{n-1}=T_{n-2}\;\;\&\;\;C_n=B_{n-1}=A_{n-2}=T_{n-3}$$ It follows that $$T_n=T_{n-1}+T_{n-2}+T_{n-3}$$

Thus, $T_n$ satisfies the so-called Tribonacci recursion. Can you finish from here?

$\endgroup$
2
  • $\begingroup$ Thanks so much, this made things so much easier. However, just one more addendum question - I could note that An = Tn-1 and so on, but is it simply an observation or is there any proof also available for it? PS. Also, I think, B2 = 1 and C3 = 1. $\endgroup$
    – Doctor
    Mar 19 '16 at 12:11
  • $\begingroup$ Yes, $B_2=1=C_3$, those follow from the definition. I wrote out $B_1$ and $C_2$ because they don't follow from the definition (The string in $B_1$ is just $B$ which technically doesn't end in $YB$, the string in $C_2$ is $BB$ which technically does not end in $YBB$.) $A_n=T_{n-1}$ because we can always append a $Y$ to any "good" string of length one less. $\endgroup$
    – lulu
    Mar 19 '16 at 12:12

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.