There are$n$ balls numbered $1,2,\cdots,n$, respectively. They are painted with $4$ colours, red, yellow, blue, and green, according to the following rules: First, randomly line them on a circle. Then let any three clockwise consecutive balls numbered $i, j, k$, in order. 1) If $i>j>k$, then the ball $j$ is painted in red; 2) If $i<j<k$, then the ball $j$ is painted in yellow; 3) If $i<j, k<j$, then the ball $j$ is painted in blue; 4) If $i>j, k>j$, then the ball $j$ is painted in green. And now each permutation of the balls determine a painting method. We call two painting methods distinct, if there exists a ball, which is painted with two different colours in that two methods. Find out the number of all distinct painting methods.
Problem
Source: 2013 China TST Quiz 1 Day 1 P3
Tags: induction, combinatorics proposed, combinatorics
duanby
04.04.2013 17:52
THE ANSWER IS$\frac{\binom{2n-2}{n-1}}{n}$ my method to prove it is by induction and the recursion of the Catalan number it's ture for n=3 if n is ture then n+1: n+1 is blue 1>if n is not blue n and n+1 is adjacent let n n+1 be a number n so f(1,2,...,n-1)=$\ C_{n-1}$ and n can be red or yellow so in this case 2 $\ C_{n-1}$ method 2>if n is blue then prove that for any coloring that n is blue there exist a permutation satisfy the property: by clockwise the number between n+1 and n is a permutation of t,t+1...n-1,the number between n and n+1 is a permutation of 1,...,t-1 ($2\le $ t $\le$n-1) and for different t the color of the points are different first proof for t1>t2 the coloring is different this is because t1 is green in t=t1 but not green in t=t2 then prove the existence
induction assume n-k is the greatest number that is not blue then do some detailed discussion
AT LAST count the number for n+1 is \[ C_{n-1} +C_1*C_{n-2}+...+C_{n-1}=C_{n}\]
yunxiu
15.04.2013 10:08
duanby wrote: first proof for t1>t2 the coloring is different this is because t1 is green in t=t1 but not green in t=t2 ${t_1}$ can be green in $t = {t_2}$. $n,...,n - 1,{t_1},n - 2,...,n + 1$.
duanby
15.04.2013 18:00
I think you are wrong. in this case there must be number in both side of n,n+1 （前面有写到的）
the4seasons
10.11.2017 10:51
I don't think I quite understand the problem. If the answer is as what duanby has typed, then if n=4, there are 5 colourings. However, I am only able to find 4: >Blue, Red, Red, Green >Green, Yellow, Yellow, Blue >Yellow, Blue, Red, Green >Blue, Green, Blue, Green What is wrong with my understanding of this question?