Find the maximum length $m$ of the sequence $a_1 a_2 \dots a_m$ such that
(1) Each $1\le a_i\le n(\in\mathbb{N})$
(2) No $1\le i \le m-1$ such that $a_{i}=a_{i+1}$
(3) Call $(x,y)$ good if $a_i=x, a_j=y, a_k=x$ for some $1\le i<j<k\le m$. If $(x,y)$ is good, $(y,x)$ is not good.
I found a proof using induction on $n$.
I want a proof with non-inductive argument. (Probably global?)
And if the problem is famous, can you give a link to it?