Library / /7 of 12

, 2019

Combinatorics Difficulty 8.3 Shortlist Prove it Romania

If $S$ is a $10^4$ -digit binary string consisting of zeroes and ones, and $k \le 10^4$ is a positive integer, a $k$ -block of $S$ is any substring consisting of $k$ consecutive digits; two $k$ -blocks, $a_1a_2\dots a_k$ and $b_1b_2\dots b_k$ , are of the same type if $a_i = b_i$ , $i = 1, \dots, k$ . Consider all $10^4$ -digit binary strings whose 3-blocks are of at most 7 types. Determine the maximum number of types the 10-blocks of such a string may fall in.
Cătălin Gherghe

Solution

The required maximum is 504 and is achieved for a string (to be described below) containing all 7 possible 3-block types different from 000.

To prove this, let $f(k)$ be the maximum number of $k$ -digit strings whose 3-blocks are of at most 7 types. Clearly, $f(1) = 2$ , $f(2) = 4$ and $f(3) = 7$ .

We will show that $f(k) \le f(k-1) + f(k-2) + f(k-3)$ ; equality holds if all 7 possible 3-block types different from 000 occur. It then follows recursively that $f(10) = 504$ .

To describe a $10^4$ -digit string with 7 3-block types and 504 10-block types, append a one to each of the 504 10-digit strings above, concatenate the resulting 11-digit strings in some order to form a $504 \times 11$ -digit string, then append a $(10^4 - 504 \times 11)$ -digit tail of ones.

We now show that $f(k) \le f(k-1) + f(k-2) + f(k-3)$ . Since there are $2^3 = 8$ possible 3-block types, some 3-block $abc$ occurs in none of the $k$ -digit strings under consideration.

There are at most $f(k-1)$ such strings whose last digit is different from $c$ , at most $f(k-2)$ whose last two digits are $xc$ , $x \neq b$ , and at most $f(k-3)$ whose last three digits are $xbc$ , $x \neq a$ . Consequently, $f(k) \le f(k-1) + f(k-2) + f(k-3)$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.