Re: [obm-l] Jogo dos 4 bits
Olá pessoal! Desculpem a minha ausencia esses dias da lista pra responder às duvidas dos que responderam o meu e-mail inicial. Ótima estratégia Ralph! Gostei bastente mesmo do seu método! Mas como você mesmo levantou a hipótese, será que da pra fazer com menos tentativas? Acho que não... pelos motivos citados pelo Maurício Acho que chegamos então que o mínimo são 5 tentativas.. Obrigado a todos! 2008/11/18 Ralph Teixeira [EMAIL PROTECTED]: Se o objetivo eh minimizar o numero **maximo** de palpites... Certamente, eh possivel adivinhar em um maximo de 5 palpites, usando a seguinte estrategia de ir trocando um digito de cada vez (Pi=i-esimo palpite, Ri=i-esima resposta): P1= P2=0001 P3=0011 P4=0111 Se a resposta melhorou ao passar de Pi para Pi+1, eh porque aquele digito que voce trocou estah correto, e vice-versa. Ou seja, apos estes 4 palpites, voce jah sabe os ultimos 3 digitos com certeza. Agora basta olhar a resposta a P1 para descobrir se o digito incerto eh 0 ou 1; assim, o 5o palpite serah correto. Exemplo: R1=1, R2=2, R3=1 e R4=2. Como R2R1, o ultimo digito eh 1, isto eh, xxx1 (pois esta eh a unica diferenca entre P1 e P2); Como R3R2, xx01. Como R4R3, x101. Enfim, como R1=1, soh tem um 0 na resposta, entao 1101 eh a resposta. Esta estrategia eh facilmente generalizavel: sempre eh possivel adivinhar um numero de n bits com, no maximo, n+1 palpites (agora, serah que dah com menos?). Abraco, Ralph 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: PC:2 Usuario: 0100 PC: 3 Usuario: 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 =
Re: [obm-l] Jogo dos 4 bits
nao ficou muito claro. O PC retorna so os bits que estão nas posições corretas né? 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: PC:2 Usuario: 0100 PC: 3 Usuario: 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 =
Re: [obm-l] Jogo dos 4 bits
por entropia deveria ser -log_2 ^(1/(2^4))=log_2^(2^4)=4 bits certo? 1a-q tal poe sem perda de generalidade 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: PC:2 Usuario: 0100 PC: 3 Usuario: 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.htmlhttp://www.mat.puc-rio.br/%7Eobmlistas/obm-l.html =
Re: [obm-l] Jogo dos 4 bits
por entropia deveria ser -log_2 ^(1/(2^4))=log_2^(2^4)=4 bits certo? 1a-q tal poe sem perda de generalidade 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: PC:2 Usuario: 0100 PC: 3 Usuario: 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.htmlhttp://www.mat.puc-rio.br/%7Eobmlistas/obm-l.html =
Re: [obm-l] Jogo dos 4 bits
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 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: PC:2 Usuario: 0100 PC: 3 Usuario: 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 =
Re: [obm-l] Jogo dos 4 bits
é 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 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: PC:2 Usuario: 0100 PC: 3 Usuario: 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.htmlhttp://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.htmlhttp://www.mat.puc-rio.br/%7Eobmlistas/obm-l.html =
Re: [obm-l] Jogo dos 4 bits
Ainda pergunto: o computador retorna quantos bits estão certos ou quantos bits estão certos nas posicoes certas? Por exemplo. Se o computador escolhe 0001 Eu chuto 1000 Ele me retorna 4 (3 zeros e 1 um) ou 2 (apenas 2 zeros na posicao correta)? Isso faz toda a diferença e não ficou claro no enunciado. 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 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: PC:2 Usuario: 0100 PC: 3 Usuario: 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 =
Re: [obm-l] Jogo dos 4 bits
Com no máximo cinco: 1a - Usuário: - 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 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: PC:2 Usuario: 0100 PC: 3 Usuario: 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.htmlhttp://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.htmlhttp://www.mat.puc-rio.br/%7Eobmlistas/obm-l.html =
Re: [obm-l] Jogo dos 4 bits
Se o objetivo eh minimizar o numero **maximo** de palpites... Certamente, eh possivel adivinhar em um maximo de 5 palpites, usando a seguinte estrategia de ir trocando um digito de cada vez (Pi=i-esimo palpite, Ri=i-esima resposta): P1= P2=0001 P3=0011 P4=0111 Se a resposta melhorou ao passar de Pi para Pi+1, eh porque aquele digito que voce trocou estah correto, e vice-versa. Ou seja, apos estes 4 palpites, voce jah sabe os ultimos 3 digitos com certeza. Agora basta olhar a resposta a P1 para descobrir se o digito incerto eh 0 ou 1; assim, o 5o palpite serah correto. Exemplo: R1=1, R2=2, R3=1 e R4=2. Como R2R1, o ultimo digito eh 1, isto eh, xxx1 (pois esta eh a unica diferenca entre P1 e P2); Como R3R2, xx01. Como R4R3, x101. Enfim, como R1=1, soh tem um 0 na resposta, entao 1101 eh a resposta. Esta estrategia eh facilmente generalizavel: sempre eh possivel adivinhar um numero de n bits com, no maximo, n+1 palpites (agora, serah que dah com menos?). Abraco, Ralph 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: PC:2 Usuario: 0100 PC: 3 Usuario: 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 =
