Encontre todos os pares de conjuntos de seqüências A e B para os quais A B=\{10,111,1010,1000,10111,101000\}.

Passo 1

O enunciado pede que encontremos todos os pares de conjuntos de sequências binárias A e B tais que a concatenação
A\,B \;=\;\{\,10,\,111,\,1010,\,1000,\,10111,\,101000\}
isto é,
A\,B=\{\,x y\mid x\in A,\;y\in B\}
é exatamente o conjunto dado de seis cadeias.

Passo 2

Seja \lvert A\rvert=m e \lvert B\rvert=n. Então \lvert A\,B\rvert=m\cdot n=6. Logo (m,n) pode ser (1,6), (2,3), (3,2) ou (6,1).

Passo 3

Casos triviais com (m,n)=(1,6) ou (6,1):
  • Se \lvert A\rvert=1 então A=\{\epsilon\} e B tem todos os seis elementos, de modo que
A=\{\epsilon\},\quad B=\{10,111,1010,1000,10111,101000\}.
  • Se \lvert B\rvert=1 então B=\{\epsilon\} e A tem todos os seis elementos, de modo que
A=\{10,111,1010,1000,10111,101000\},\quad B=\{\epsilon\}.

Passo 4

Caso não-trivial (m,n)=(2,3). Então deve haver dois prefixos u,v em A e três sufixos em B tais que cada uma dos 6 cadeias seja u ou v seguido do mesmo conjunto de 3 sufixos.
Observando as cadeias, note que exatamente três começam por “101” e as demais três começam por “1”. Se tirarmos o prefixo “101” das cadeias
1010,\;10111,\;101000
sobram os sufixos
0,\;11,\;000.
Se tirarmos o prefixo “1” das outras três cadeias
10,\;111,\;1000
sobram exatamente os mesmos sufixos
0,\;11,\;000.
Portanto a fatoração não-trivial é
A=\{\,1,\;101\},\qquad B=\{\,0,\;11,\;000\},
pois
\{1,101\}\,\{0,11,000\} =\{10,111,1000,\;1010,10111,101000\}.

Passo 5

Caso (m,n)=(3,2). Seriam três prefixos e dois sufixos, mas não há forma de agrupar as seis cadeias em dois blocos de três com mesmos sufixos—nenhuma escolha de dois sufixos dá exatamente três cadeias cada. Logo não há solução em (3,2) além dos triviais já citados.

Resposta

Os únicos pares (A,B) que satisfazem A\,B=\{10,111,1010,1000,10111,101000\} são:
(a) A=\{\epsilon\},\;B=\{10,111,1010,1000,10111,101000\}. (b) A=\{10,111,1010,1000,10111,101000\},\;B=\{\epsilon\}. (c) A=\{1,\,101\},\;B=\{0,\,11,\,000\}.

Exercícios de Livros Relacionados