How can we prove that every sequence of $30$ elements from a set of three repeats a subsequence of length 3?

Question

How can we prove that for every series over $30$ elements(included $30$), there must be a "sub" three element series then will repeat itself? (Series's numbers are only $\{1,2,3\}$)

Example for a "sub" series that repeats itself $12121$ ("121" repeats) , $1111$ ("111" repeats).

Example for a good series: $12311122$

Well, this was a question from the exam, unfortunately I wasn't able to answer it. I thought of many ways to solve this, but I'm sure there's fast efficient way to solve this that I don't see. I would love to know how you would approach this.

Answer 1

Use the pigeonhole principle:

• The sequence of length 30 contains 28 subsequences of length three.
• There are 27 _____ (you fill in the blank) possible subsequences of length three.