Browse · MathNet
PrintSELECTION TESTS FOR THE 2019 BMO AND IMO
Romania 2019 counting and probability
Problem
If is a -digit binary string consisting of zeroes and ones, and is a positive integer, a -block of is any substring consisting of consecutive digits; two -blocks, and , are of the same type if , . Consider all -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 be the maximum number of -digit strings whose 3-blocks are of at most 7 types. Clearly, , and .
We will show that ; equality holds if all 7 possible 3-block types different from 000 occur. It then follows recursively that .
To describe a -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 -digit string, then append a -digit tail of ones.
We now show that . Since there are possible 3-block types, some 3-block occurs in none of the -digit strings under consideration.
There are at most such strings whose last digit is different from , at most whose last two digits are , , and at most whose last three digits are , . Consequently, .
To prove this, let be the maximum number of -digit strings whose 3-blocks are of at most 7 types. Clearly, , and .
We will show that ; equality holds if all 7 possible 3-block types different from 000 occur. It then follows recursively that .
To describe a -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 -digit string, then append a -digit tail of ones.
We now show that . Since there are possible 3-block types, some 3-block occurs in none of the -digit strings under consideration.
There are at most such strings whose last digit is different from , at most whose last two digits are , , and at most whose last three digits are , . Consequently, .
Final answer
504
Techniques
Recursion, bijection