Re: [obm-l] Problema 6 da OBM de 2002

2015-10-12 Por tôpico Bernardo Freitas Paulo da Costa 
2015-10-12 0:31 GMT-03:00 Gabriel Tostes :
> Mostre que não podemos formar mais que 4096 sequências binárias de tamanho 24 
> tal que quaisquer 2 diferem em ao menos 8 posições.
> Não consegui entender a resolução na Eureka. Alguém pode resolvê-lo?

Eu não sei se conheço alguma solução além da do Fábio (imagio que seja
esta a da Eureka). Mas acredito que pode ajudar a entender o problema
diminuindo os números, e tentando ser mais ambicioso: tente descobrir
a maior quantidade de sequências binárias de tamanho 4 tais que duas
quaisquer diferem em ao menos 2 posições. Vou tentar começar o
raciocínio: Suponha, sem perda de generalidade, que uma das sequências
é a . Então, você não pode ter nenhuma sequência com apenas um
"1", certo? Agora, pense em quantas sequências com dois "1" podem
haver. Ao todo, há 6, mas você não pode escolher todas elas, certo?

Para completar, ainda falta a idéia das "regiões de influência" (cada
sequência escolhida "domina" algumas sequências, as que estão mais
próximas dela do que de qualquer outra sequência). Para visualisar
isso, pense que, em vez de 4/2, o problema é sobre tam=5 / diferença
>= 3. Faça um "ponto" para cada sequência (dá 32, dá trabalho mas é
factível) e ligue as que diferem de apenas uma posição. Daí, comece
marcando uma (tipo a 0) e depois vá escolhendo como puder. Isso
deve deixar claro para você que cada sequência tem uma região de
influência de tamanho 1.

Abraços,
-- 
Bernardo Freitas Paulo da Costa

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.


=
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=

RE: [obm-l] Problema 6 da OBM de 2002

2015-10-12 Por tôpico Esdras Muniz 
Em qual EUREKA está a solução deste problema?


-Mensagem Original-
De: "Bernardo Freitas Paulo da Costa" <bernardo...@gmail.com>
Enviada em: ‎12/‎10/‎2015 12:29
Para: "Lista de E-mails da OBM" <obm-l@mat.puc-rio.br>
Assunto: Re: [obm-l] Problema 6 da OBM de 2002

2015-10-12 0:31 GMT-03:00 Gabriel Tostes <gtos...@icloud.com>:
> Mostre que não podemos formar mais que 4096 sequências binárias de tamanho 24 
> tal que quaisquer 2 diferem em ao menos 8 posições.
> Não consegui entender a resolução na Eureka. Alguém pode resolvê-lo?

Eu não sei se conheço alguma solução além da do Fábio (imagio que seja
esta a da Eureka). Mas acredito que pode ajudar a entender o problema
diminuindo os números, e tentando ser mais ambicioso: tente descobrir
a maior quantidade de sequências binárias de tamanho 4 tais que duas
quaisquer diferem em ao menos 2 posições. Vou tentar começar o
raciocínio: Suponha, sem perda de generalidade, que uma das sequências
é a . Então, você não pode ter nenhuma sequência com apenas um
"1", certo? Agora, pense em quantas sequências com dois "1" podem
haver. Ao todo, há 6, mas você não pode escolher todas elas, certo?

Para completar, ainda falta a idéia das "regiões de influência" (cada
sequência escolhida "domina" algumas sequências, as que estão mais
próximas dela do que de qualquer outra sequência). Para visualisar
isso, pense que, em vez de 4/2, o problema é sobre tam=5 / diferença
>= 3. Faça um "ponto" para cada sequência (dá 32, dá trabalho mas é
factível) e ligue as que diferem de apenas uma posição. Daí, comece
marcando uma (tipo a 0) e depois vá escolhendo como puder. Isso
deve deixar claro para você que cada sequência tem uma região de
influência de tamanho 1.

Abraços,
-- 
Bernardo Freitas Paulo da Costa

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.


=
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.