Problem

Source: Iran second round 2011

Tags: induction, combinatorics proposed, combinatorics



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$?