IMO 1993 SL 18

Origin: POL

Problem

Let Sn be the number of sequences (a1, a2, . . . , an), where ai \in {0, 1}, in which no six consecutive blocks are equal. Prove that Sn \to\infty as n \to\infty.

Solution

Let Bn be the set of sequences with the stated property (Sn = |Bn|). We shall prove by induction on n that Sn \geq3 2Sn−1 for every n. Suppose that for every i \leqn, Si \geq 2Si−1, and consequently Si \leq
2 n−i Sn. Let us consider the 2Sn sequences obtained by putting 0 or 1 at the end of any sequence from Bn. If some sequence among them does not belong to Bn+1, then for some k \geq1 it can be obtained by extend- ing some sequence from Bn+1−6k by a sequence of k terms repeated six times. The number of such sequences is 2kSn+1−6k. Hence the number of sequences not satisfying our condition is not greater than  k\geq1 2kSn+1−6k \leq  k\geq1 2k 2 6k−1 Sn = 3 2Sn 2(2/3)6 1 −2(2/3)6 = 192 601Sn < 1 2Sn. Therefore Sn+1 is not smaller than 2Sn −1 2Sn = 2Sn. Thus we have Sn \geq
3 n.