MathDB

Words and equivalence

Source: OBM 2017

March 20, 2023

Combinatorics of wordscombinatoricsmath olympiad

Problem Statement

Let's consider words over the alphabet

\{a,b\}

to be sequences of

a

and

b

with finite length. We say

u \leq v

if

u

is a subword of

v

if we can get

u

erasing some letter of

v

(for example

aba \leq abbab

). We say that

u

differentiates the words

x

and

y

if

u \leq x

but

u \not\leq y

or vice versa.
Let

m

and

l

be positive integers. We say that two words are

m-

equivalents if there does not exist some

u

with length smaller than

m

that differentiates

x

and

y

.
a) Show that, if

2m \leq l

, there exists two distinct words with length

l

\

m-

equivalents. b) Show that, if

2m > l

, any two distinct words with length

l

aren't

m-

equivalent.

Back to Problems View on AoPS