MathDB

Strings of binary numbers (pure math solution required, not informatical ones)

Source: Romanian TST for 2019 IMO

October 1, 2019

Infodiscrete mathscombinatorics

Problem Statement

For a natural number

n,

a string

s

of

n

binary digits and a natural number

k\le n,

define an

n,s,k

-block as a string of

k

consecutive elements from

s.

We say that two

n,s,k\text{-blocks} ,

namely,

a_1a_2\ldots a_k,b_1b_2\ldots b_k,

are incompatible if there exists an

i\in\{1,2,\ldots ,k\}

such that

a_i\neq b_i.

Also, for two natural numbers

r\le n, l,

we say that

s

is

r,l

-typed if there are, at most,

l

pairwise incompatible

n,s,r\text{-blocks} .

Let be a

3,7\text{-typed}

string

t

consisting of

10000

binary digits. Determine the maximum number

M

that satisfies the condition that

t

is

10,M\text{-typed} .

Cătălin Gherghe

Back to Problems View on AoPS