Suponha que
e
sejam subconjuntos finitos de
, em que
é um alfabeto. En necessariamente verdade que
?
Passo 1
Resumimos o problema: sejam subconjuntos finitos
e
de um alfabeto
. Definimos
e
A pergunta é se necessariamente
.
Passo 2
Em geral a concatenação satisfaz
onde
e
são os números de colisões (pares distintos que geram a mesma palavra). Nada garante que
.
Passo 3
Para dar um contra-exemplo escolha
,
onde
é a palavra vazia.
Passo 4
Calculamos
logo
.
Passo 5
Calculamos
logo
.
Passo 6
Vemos que
portanto não é sempre verdade que
.
Resposta
Não, não é necessariamente verdade. Por exemplo, com
e
obtemos
.