Com no máximo cinco: 1a - Usuário: 0000 - Se der 0 ou 4, a resposta é imediata. FIM na 1a (se der 4) ou 2a (se der 0)
- Se der 1 ou 3, basta variar o bit nas 4 posições (no máximo) totalizando 4 tentativas na pior das hipóteses. FIM no máximo na 5a etapa - Se der 2: 2a - Usuário insere dois 0 e dois 1. - Se der 0 ou 4, a resposta é imediata. FIM na 2a (se der 4) ou 3a. (se der 0) - Senão, a resposta só pode ser 2. Então: 3a. Usuário escolhe um par 01 e inverte. - Se der 0 ou 4, a resposta é imediata. FIM na 3a. (se der 4) ou 4a. (se der 0) - Se der 2 novamente, significa que tanto no par que foi mexido quanto no par que não foi mexido havia 1 bit na posição correta: 4a. Inverte o 0 do primeiro par com o 1 do segundo par - Vai dar 0 ou 4, a resposta é imediata. FIM na 4a.(se der 4) ou 5a (se der 0) Agora resta saber se dá com 4 hehe 2008/11/18 Felipe <[EMAIL PROTECTED]> > é entao, fiquei na duvida se podia usar entropia aí, pq eh um pouco > diferente, mas com 6 eh tranquilo acertar > problema eh provar mesmo quantos sao ehhe > > 2008/11/18 Maurício Collares <[EMAIL PROTECTED]> > > Não existe maneira de fazer só com 4 tentativas. Suponha que o >> computador pode prever o que você vai falar (isso não é nada irreal, >> pois se o computador escolhe os bits aleatoriamente e uniformemente, a >> chance de ele escolher o correspondente a "adivinhar" é não nula). >> Você tenta "0001" e o computador, só de maldade, responde "1". Você >> não sabe qual dos 4 dígitos está errado, mas o fato é que você só tem >> mais três tentativas pra acertar segundo sua conjectura: >> >> * Se você tentar mudar apenas um dígito por tentativa (em relação a >> combinação original), o computador adivinha qual dígito você não >> tentou e escolhe ele como o errado, de modo que você só vai poder >> acertar de quinta. >> * Se você mudar mais de um dígito em uma das três tentativas que >> sobrou e, por consequencia disso, conseguir mudar todos os dígitos (se >> não mudar todos, faz a mesma coisa que no caso anterior), você vai ter >> dois dígitos que sempre são mudados juntos em relação a configuração >> original. Então o computador adivinha qual par sempre é testado >> conjuntamente e escolhe um elemento do par como errado. Então, em >> todas as tentativas, ou você não muda o dígito errado, ou muda o >> dígito errado pra um dígito certo e muda um dígito certo pra um dígito >> errado. >> >> Segue-se que, no pior caso, 4 lances não bastam. É fácil fazer com 6 >> lances (basta tentar uma configuração inicial qualquer e mudar os bits >> um por um para conseguir informação sobre eles: em cinco lances, vc >> tem toda a informação necessária, e aí dá pra acertar no sexto), mas >> não pensei como fazer pra provar que dá (ou que não dá) pra fazer com >> cinco. >> >> -- >> Abraços, >> Maurício >> >> 2008/11/18 Felipe <[EMAIL PROTECTED]>: >> > por entropia deveria ser -log_2 ^(1/(2^4))=log_2^(2^4)=4 bits >> > certo? >> > >> > 1a-q tal poe sem perda de generalidade 0000 >> > descobre que sao 2 zeros e 2 uns (2 acertos) >> > 2a-depois poe 0111 (3 acertos) >> > 3a- 0001 >> > 4a- >> > >> > ah fiz rapido , alguem deve achar uma maneira de no máximo 4. >> > >> > >> > >> > 2008/11/18 Douglas Ribeiro Silva <[EMAIL PROTECTED]> >> >> >> >> O jogo dos 4 bits consiste no computador escolher um número de 4 bits >> >> e o usuário tentar adivinhar. Para cada palpite do usuário o >> >> computador retorna quantos bits ele acertou. >> >> >> >> Ex: o computador escolhe 0101 >> >> >> >> Usuario: 0000 >> >> PC:2 >> >> Usuario: 0100 >> >> PC: 3 >> >> Usuario: 1111 >> >> PC: 2 >> >> Usuario: 0111 >> >> PC: 1 >> >> Usuario: 0101 >> >> PC: 4 >> >> >> >> Qual a melhor estratégia para o jogo? O jogador deve sempre trocar a >> >> quantidade de dígitos que o computador indicar? Qual a quantidade >> >> máxima que um usuário inteligente gastaria para acertar o numero? >> >> >> >> >> ========================================================================= >> >> Instruções para entrar na lista, sair da lista e usar a lista em >> >> http://www.mat.puc-rio.br/~obmlistas/obm-l.html<http://www.mat.puc-rio.br/%7Eobmlistas/obm-l.html> >> >> >> ========================================================================= >> > >> > >> >> ========================================================================= >> Instruções para entrar na lista, sair da lista e usar a lista em >> http://www.mat.puc-rio.br/~obmlistas/obm-l.html<http://www.mat.puc-rio.br/%7Eobmlistas/obm-l.html> >> ========================================================================= >> > >
