Combinatorics Olympiad Problem 1

Probability Level 4

A baton is divided into $2n+1$ cylindrical bands of equal length $(n \geq 1)$ . In how many different ways can the $2n+1$ bands be colored if $3$ colors are available, assuming that no two adjacent bands may be given the same color? (Two colorings count as the same if one of them can be converted into the other by turning the baton around.)

This problem is not original. It is on the level of the BMO (British Mathematical Olympiad), and is therefore quite hard.

This problem is part of this set .

\frac {3}{2}(4^n+2^n)

\frac {2}{3}(2^n+4^n)

\frac {2}{3}(6^n+3^n)

\frac {1}{2}(2^n)

22^n+4^n

1 solution

Baby Googa
Mar 13, 2015

I believe the answer is incorrect. I'm getting $\frac{3}{2}(4^n)$ .

Please correct me if I'm wrong.

Verify it by taking n=1. Make the cases, it is easy for n=1. Perhaps, you will realize your mistake

Prakash Chandra Rai - 6 years, 3 months ago

If $n=1$ , then there are $3$ portions. Then there are $3$ ways to choose the color for the first cylinder, $2$ ways for the second, and $2$ ways for the last. Then we divide by $2$ so we don't overcount. This is still the same as $\frac{3}{2}(4^n)$ . What am I doing wrong?

Baby Googa - 6 years, 3 months ago

1st and 3rd may have same colour. You haven't taken that case

Prakash Chandra Rai - 6 years, 3 months ago

@Prakash Chandra Rai – Oh I get it now. Thanks!

Baby Googa - 6 years, 3 months ago

Combinatorics Olympiad Problem 1

1 solution

0 pending reports