0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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... $\endgroup$ – Mike Earnest Apr 19 at 22:19
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.