Encontre todos os pares de conjuntos de seqüências
e
para os quais
.
Passo 1
O enunciado pede que encontremos todos os pares de conjuntos de sequências binárias
e
tais que a concatenação
isto é,
é exatamente o conjunto dado de seis cadeias.
Passo 2
Seja
e
. Então
. Logo
pode ser
,
,
ou
.
Passo 3
Casos triviais com
ou
:
- Se
então e tem todos os seis elementos, de modo que
- Se
então e tem todos os seis elementos, de modo que
Passo 4
Caso não-trivial
. Então deve haver dois prefixos
em
e três sufixos em
tais que cada uma dos 6 cadeias seja
ou
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
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
sobram os sufixos
Se tirarmos o prefixo “1” das outras três cadeias
sobram exatamente os mesmos sufixos
Portanto a fatoração não-trivial é
pois
Passo 5
Caso
. 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
além dos triviais já citados.
Resposta
Os únicos pares
que satisfazem
são:
(a)
(b)
(c)