[obm-l] Re:

[gugu@xxxxxxx]

   Caro Helder,
 (a)  Faltou ABB na sua lista, mas acho que foi por esquecimento, nao ?
 Nesse caso a resposta e' 10: AAABBBABAA, por exemplo (como sao 8 sequencias, 
que tem 8 primeiras letras e' claro que 10 e' o menor possivel; se fosse num 
circulo e nao numa fila a resposta seria 8). Se voce quiser mesmo omitir o ABB 
a resposta passa a ser 9: BBBAAABAB, por exemplo.
 (b) A resposta e' 2^n+n-1 (que e' claramente o minimo possivel, como acima; se 
for num circulo a resposta e' 2^n). Ha' mais de uma prova interessante desse 
fato (essas sequencias se chamam sequencias de de Brujin, se nao me engano). 
Acho que vou deixar que as outras pessoas pensem um pouco sobre como provar 
este fato, e depois, se for necessario, eu escrevo uma prova.
   Abracos,
            Gugu

Citando Helder Suzuki <heldersuzuki@yahoo.com.br>:

> Se eu tenho muitos carros azuis ou brancos, e eu faço
> uma fila com somente 3 desses carros, posso ter uma
> das seguintes combinações:
> AAA
> AAB
> ABA
> BAA
> BAB
> BBA
> BBB
> onde A indica um carro azul e B indica um carro
> branco.
> 
> (a) Qual a quantidade mínima de carros(azuis e
> brancos) que eu preciso para formar uma única fila tal
> que eu possa encontrar dentro dela todas as
> combinações de 3 carros?
> obs: as combinações podem se sobrepor
> 
> (b) Qual a quantidade mínima de carros(azuis e
> brancos) que eu preciso para formar uma única fila tal
> que eu possa encontrar dentro dela todas as
> combinações de N carros?
> obs: as combinações podem se sobrepor
> 
> Abraços,
> Helder Toshiro Suzuki
> 
> _______________________________________________________________________
> Yahoo! Mail
> Mais espaço, mais segurança e gratuito: caixa postal de 6MB, antivírus,
> proteção contra spam.
> http://br.mail.yahoo.com/
> =========================================================================
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> =========================================================================
> 




-------------------------------------------------
This mail sent through IMP: http://horde.org/imp/
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================