6
$\begingroup$

Let $S_n$ be the number of sequences of $n$ zeroes and ones such that the sequence does not contain six consecutive identical blocks of numbers. Show that $S_n$ tends to infinity as $n\to\infty$.

Since we just need to show $S_n$ tends to infinity, I think a rough estimate should be enough. I think I should consider arbitrarily long sequences of zeroes and ones that follow a particular form and that don't contain six consecutive identical blocks of numbers. Or maybe some recurrence relation involving $S_n$ with some base cases might do the trick. Let $T_n$ denote the set of binary strings counted by $S_n$. Then $T_i$ is the set of length i binary strings for $i < 6.$ $T_6$ only excludes the all zero and all one strings. I think $T_7$ just excludes $\{10^{(6)}, 0^{(6)}1, 0 1^{(6)}, 1^{(6)}0\}$ since we can only have a block of $1$ repeating $6$ times consecutively. Obviously for a string of length n, the maximum length of an identical block that repeats at least 6 times consecutively is $\lfloor \frac{n}6\rfloor$.

$\endgroup$
3
  • 1
    $\begingroup$ When does $S_n$ tend to infinity? For what n? Please clarify the question . $\endgroup$ Jul 2, 2022 at 16:07
  • $\begingroup$ Is $010$ repeated six times an example of six consecutive identical blocks of numbers? Can the block size be one so that $111111$ is six consecutive copies of "$1$"? $\endgroup$
    – John Douma
    Jul 2, 2022 at 16:22
  • 2
    $\begingroup$ There are only finitely many square free binary words. But A028445 is the sequence of numbers of cube free binary words of length $n$. I believe that the references contain proofs that this sequence grows exponentially, though I have not checked. $\endgroup$
    – lulu
    Jul 2, 2022 at 16:43

2 Answers 2

4
+100
$\begingroup$

Call a binary sequence $n$-good if it has both length $n$ and the desired property (i.e., it does not contain six consecutive identical blocks of numbers). Call a sequence good if it is $n$-good for any natural number $n$.

It suffices to show $S_{n} \geq \frac{3}{2}S_{n - 1}$ because this would imply $S_{n} \geq \left(\frac{3}{2}\right)^{n}$, and the right-hand side diverges. We proceed with induction for which the base case is clear.

Suppose $\frac{3}{2}S_{i - 1} \leq S_{i}$ for every index $i \leq n$. Combining all $n$ inequalities gives $S_{i} \leq \left(\frac{2}{3}\right)^{n - i}S_{n}$. Consider the set of all $n$-good sequences. We can form $2S_{n}$ sequences by taking each $n$-good sequence and appending either a $0$ or $1$ to the end of the sequence.

Among the constructed $2S_{n}$ sequences, some will be $(n + 1)$-good and others won't be. For the sequences that aren't $(n + 1)$-good, you can take some $(n + 1 - 6x)$-good sequence and append some block of length $x$ exactly $6$ times for some $x \geq 1$ to construct that sequence. There are $2^{x}S_{n + 1 - 6x}$ such sequences. Summing over all possible values of $x$, the number of sequences of length $(n + 1)$ that are not $(n + 1)$-good is at most $\sum_{k = 1}^{\infty} 2^{k} S_{n + 1 - 6k}$. However,

$$\sum_{k = 1}^{\infty} 2^{k}S_{n + 1 - 6k} \leq \sum_{k =1}^{\infty} 2^{k} \left(\frac{2}{3}\right)^{6k - 1} S_{n} = \frac{192}{601} S_{n} < \frac{1}{2}S_{n},$$

where the sum of a geometric series formula was used. Taking a complement we see $S_{n + 1}$ is at most $\frac{3}{2}S_{n}$, and the result follows.

$\endgroup$
1
$\begingroup$

It is shown in [1, Theorem 7] that, on a binary alphabet, cube-free words have an exponential density. This implies that $S_n$ tends to infinity.

[1] F.-J. Brandenburg. Uniformly growing $k$-th power-free homomorphisms, Theoret. Comput. Sci. 23 (1983), 69–82.

$\endgroup$
1
  • $\begingroup$ The question is from an IMO shortlist. I don't think the answer should be too complicated. $\endgroup$ Jul 10, 2022 at 3:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .