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 >> ========================================================================= > > ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =========================================================================
