# Sequence of letters ABCD, pigeon hole?

Show that in every sequence $$(a_1 , a_2 , \ldots, a_{100})$$ of the letters $$A,B,C,D,$$ there are two indices $$1 \leq i < j < 98$$ such that $$(a_i,a_{i+1},a_{i+2}) = (a_j,a_{j+1},a_{j+2})$$.

I don’t really even understand what this is asking or what principles I should be using.

• You are trying to prove there exists a sequence of three letters which appears twice in the sequence. For example, if the sequence started ABACCDADBACA..., then BAC appears twice in that sequence. There are $4\times 4\times 4$ possible three letter subsequences, and there are $98$ subsequences in your sequence, so... – Mike Earnest Apr 19 at 22:19

## 1 Answer

You are asked to prove that in any such sequence there are two equal subsequences of length 3.

The technique you should use is pigeongole principle

First, how many different sequenced of length $$3$$ do exist if every element has $$4$$ options ($$A, B, C, D$$)?
Next, how many sub-sequences of length 3 does you sequence contain? (Clearly it is $$98$$)
You are only left to divide second value by first one and make a conclusion from pigeongole principle.