# Pigeonhole principle - sequence of 3 digits 0,2,1

A sequence is called green if formed of digits 0,1,2 (digits can be repeated) A sequence is called original if there is no 3 digits that are repeated twice :

An example for non original sequence: 12121, such that 12121 and 12121 are repeatedly

Prove that for every sequence of 30 and up are non original:

My attempt is, we assume in contrary that for every sequence of max 29 is non original. if the assumption is wrong then the statement for every sequence of 30 and up is non original

we have $$3^3 = 27$$ possibilities to form 3 digits of 0,2,1 and we have set of 29 holes to fill, i don't know how to continue from here

• How many three-digits sequences are there in an $n$-digit sequence? Aug 28 '20 at 13:41
• Follow-up question: find a original sequence of $29$ digits. Aug 28 '20 at 13:42
• @AnginaSeng $n/3$ for first question? Aug 28 '20 at 13:44
• I reckon there are two in a four-digit sequence $abcd$, viz, $abc$ and $bcd$. Aug 28 '20 at 13:45
• @AnginaSeng so $\left \lceil \frac{n}{3} \right \rceil$ Aug 28 '20 at 13:47

In a sequence of $$30$$ digits, you have $$28$$ subsequences of three consecutives digits (the one beginning at the first digit, the one beginning at the second digit, ..., the one begining at the $$28$$th digit).
But there are only $$27$$ possible green sequences of three digits. That means that two of the $$28$$ sequences are the same.
• so for 29 digits we have 27 of 3 consecutive digits and there is 27 possible green digits so 27 are the holes and 27 are the pigeons so $\left \lceil \frac{27}{27} \right \rceil = 1$ means the assumption is wrong hence statement for sequence of 30 and up is correct? Aug 28 '20 at 14:05
• The fact that you have $27$ holes for $27$ pigeons only tell that you cannot apply pigeonhole principle... It does not tell that the result is false. A way to prove it would be to find explicitely an original sequence with $29$ digits. Aug 28 '20 at 14:11
• The argument I gave you in the answer proves that sequences with $\geq 30$ digits are non original, using pigeonholes principle. But it does not prove anything for a $29$-digits sequence. Aug 28 '20 at 14:21
• so according to your answer for 30 digits we have 28 of 3 consecutive digits and there is 27 possible green digits so 28 are the holes and 27 are the pigeons so $\left \lceil 28/27 \right \rceil$= 2 so there are 2 of 3 digits sequence repeated? Aug 28 '20 at 14:25