Bom, tenho estrategias boas, mas tem que provar que sao otimas (ou arrumar uma melhor):
a) Faca n tentativas com 2 baterias cada, sem intersecao. Se nenhuma dessas tentativas der certo, voce eh muito azarado e cada par tinha exatamente uma bateria ruim. Bom, entao a bateria que nao foi testada tem que ser boa -- tente-a com cada uma do ultimo par testado, vai ter que funcionar. Total: n+2 tentativas. b) Idem ao de cima... Mas se apos n tentativas nao deu certo, tome os dois ultimos pares (digamos, ab e cd) e tente as combinacoes com 1 bateria de cada (digo: ac, ad, bc, bd). Uma dessas vai ter que funcionar. Total: n+4 tentativas. (Sinto um cheirinho de que esta aqui NAO eh otima.... Mas tem que pensar mais.) Abraco, Ralph. On Sun, Feb 24, 2019 at 11:39 AM Jeferson Almir <jefersonram...@gmail.com> wrote: > 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.
