Provando que n+2 eh otimo no item (a): Suponha que voce arrumou um jeito de testar n+1 pares e garantir que funciona. Vou mostrar que tah errado.
Afinal, nos seus n+1 pares tem 2n+2 baterias, contando repeticoes. Portanto, alguma das 2n+1 baterias aparece em (pelo menos) dois dos seus pares. Marque essa bateria com a letra R e olhe para os OUTROS pares, fora esses 2 (ou mais)... Destes n-1 (ou menos) pares, escolha uma bateria de cada e marque com a letra R tambem (pode ser repetido se quiser). No final das contas, marcamos com a letra R um total de 1+(n-1)=n baterias (ou menos, se tiver repeticoes). Pois bem, se essas baterias fossem as ruins, os seus pares NAO achariam uma combinacao boa, entao seu jeito nao GARANTE que a lanterna vai acender. Agora falta mostrar que n+3 eh otimo para (b) -- ou arrumar um jeito melhor. Abraco, Ralph. On Sun, Feb 24, 2019 at 6:49 PM Ralph Teixeira <[email protected]> wrote: > Era n+2 para o item (a); o que eu falei ali foi um jeito de fazer em n+3 > para o item (b), melhor que o n+4 que eu tinha falado antes. > > Abraco, Ralph. > > On Sun, Feb 24, 2019 at 5:14 PM Pedro José <[email protected]> wrote: > >> Boa tarde! >> Ralph, >> também não sei se é ótimo. Postei a resposta para provocar. >> Só que você afirmou ter um método melhor, mas não foi. Para a) com n+2 >> estava garantido acender. Com o que você propôs podemos atingir n+3. Então >> não foi melhor. >> Ou talvez não tenha compreendido. >> >> Sds, >> PJMS >> >> Em dom, 24 de fev de 2019 às 15:27, Pedro José <[email protected]> >> escreveu: >> >>> Boa tarde! >>> a) Você pode ter n baterias com falha e n+1 sem estar em modo de falha. >>> Seu pior caso é sempre pegar uma ruim e uma boa, pois aí você nem acende >>> a lâmpada nem esgota rapidamente as em modo de falha. >>> Quando você fizer n tentativas, a que sobrou é boa. >>> E em cada lote tem uma boa e uma em falha. >>> Você pode demorar duas se na primeira escolher a que está em modo de >>> falha. Portanto, você poderá gastar n+2 tentativas no máximo. >>> Isto é interpretando o problema da seguinte forma. qual o menor número >>> de tentativas que garanta a funcionabilidade da lâmpada. Pois a lâmpada >>> pode funcionar com apenas uma tentaiva. >>> >>> b) O pior caso é n tentativas. Sendo sempre uma ruim e uma boa. >>> Pegando dois lotes temos três chances para não acender a lâmpada RB, BR >>> e RR e uma para acender BB. Portanto, no pior caso teríamos n+4 tentativas. >>> >>> Creio que seja isso. >>> Todavia, recomendaria um voltímetro. >>> >>> Sds, >>> PJMS >>> >>> >>> >>> Em dom, 24 de fev de 2019 às 11:40, Jeferson Almir < >>> [email protected]> escreveu: >>> >>>> Peço ajuda aos amigos da lista, sei que existe um problemas da obm >>>> "parecido", aguardo dicas ou soluções. Eu tentei formar um grafo de >>>> tentativas e penso como otimizar ele. >>>> >>>> a.) Existem 2n + 1 (n> 2) baterias. Não sabemos quais baterias são >>>> boas e quais são ruins, mas sabemos que o número de baterias boas é maior >>>> do que o número de baterias ruins. Uma lâmpada usa duas baterias e só >>>> funciona se ambas forem boas. Qual é o menor número de tentativas >>>> suficientes para fazer a lâmpada funcionar? >>>> >>>> b.) O mesmo problema, mas o número total de baterias é 2n (n> 2) e os >>>> números de baterias boas e ruins são iguais. >>>> >>>> >>>> >>>> -- >>>> Esta mensagem foi verificada pelo sistema de antivírus e >>>> acredita-se estar livre de perigo. >>> >>> >> -- >> Esta mensagem foi verificada pelo sistema de antivírus e >> acredita-se estar livre de perigo. > > -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
