rainbow is the name of a bird. this bird has $n$ colors and it's colors in two consecutive days are not equal. there doesn't exist $4$ days in this bird's life like $i,j,k,l$ such that $i<j<k<l$ and the bird has the same color in days $i$ and $k$ and the same color in days $j$ and $l$ different from the colors it has in days $i$ and $k$. what is the maximum number of days rainbow can live in terms of $n$?
Problem
Source: Iran second round 2011
Tags: induction, combinatorics proposed, combinatorics
29.04.2011 12:31
The answer is $2n-1$. an induction+extermal argument.
11.05.2011 13:57
We prove by induction that the maximum number of days he can live is 2n-1 days. The construction is easy: 1,2,...,n-1,n,n-1,...,2,1. For n=1 the result is true. Suppose it's true for smaller n. Let his colour in the first day be R, and this colour appears k times, at R1, R2, ..., Rk. Consider the intervals of days (R1,R2), (R2,R3), ..., (R(k-1),Rk), (Rk,...). If some colour appears in two different intervals, it contradicts the problem statement. So each colour appears in exactly one interval. Suppose there are Ci colours in interval (Ri,R(i+1)), so sum(i=1 to k) Ci = n-1. Then by induction assumption, the interval (Ri,R(i+1)) consists of at most 2Ci-1 days. Only the last interval can be empty. If it is empty then the total number of days is at most k+sum(i=1 to k-1)(2Ci-1) = 2n-1, otherwise the number of days is at most k+sum(i=1 to k)(2Ci-1)=2n-2. Now we're done.
20.05.2020 09:59
$2n-1$. Assume that a good coloring for $i<n$ colors has at most $2i-1$ days, i.e. if we have $2i-1$ days we can color them in a good manner with at least $i$ colors. Suppose we have at least $2n$ days in case $n$. Let $k$ be the color that was used forr the first day. Then lets suppose it was used id $D_1, D_2,..,D_m$ and let D be the last day. Another color cannot be in 2 of the intervals $(D_1;D_2)..(D_{m-1};D_m),(D_m;D)$; otherwise condition 2 would not be satisfied. Let $a_i$ be the number of days in $(D_i;D_{i+1})$. Then for a proper coloring we have to use at least $\lfloor\frac{a_i}{2}\rfloor+1\geq\frac{a_i+1}{2}$ colors. Hence in total we use at least $\sum_{i=1}^{m}\frac{a_i+1}{2}+1$ colors in total, but $\sum_{i=1}^{m}a_i=2n-m$ so we need at least n+1 colors, contradiction.