[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Torneio das Cidades ( Número mínimo de Tentativas )
bom dia! Não sei onde vi que so precisam +4. Nada a ver. Em ter, 26 de fev de 2019 14:09, Pedro José Boa tarde! > > Embora seja bastante óbvio. Só me apercebi agora. > Para o caso b, quando nós chegamos ao pior caso com n testes, sem > resultado. No algoritmo primordial. Pegava-se dois pares falhos e tínhamos > + 4 chances. n+4. > Depois o Ralph, o melhorou e caímos em n +3. > O que havia reparado é que para tirar pelo menos n baterias defeituosas, > pegando um conjunto de n+ 1 baterias, se faz necessário (n+1)*n/2 testes. O > que dá uma relação número de testes : mínimo de n baterias defeituosas de > (n+1)/2, o que dá uma melhor relação para pelo menos uma bateria, que dá 1. > Para pelo menos duas, 3/2 e só vai piorando. > Portanto, o método usado por Ralph, por sentimento não podia ser o melhor. > Mas como melhorá-lo? > Simples, por demais, embora só atinei agora. É só lembrar que quando > somamos 4 a n, nós estamos desperdiçando dois testes que nós já o fizemos > antes. > Portanto para não esquecer: > Separa-se 4 bateias e n-2 testes com as 2n-4 restantes. Ai se faz os 4 > testes, no máximo com essas últimas. Teremos então n+2 igual ao resultado > do item a) > > Sds, > PJMS > > > Em dom, 24 de fev de 2019 às 19:10, Ralph Teixeira > escreveu: > >> 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 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é 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é 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 < > jefersonram...@gmail.com> 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. >>> >>> >>
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Torneio das Cidades ( Número mínimo de Tentativas )
Boa tarde! Embora seja bastante óbvio. Só me apercebi agora. Para o caso b, quando nós chegamos ao pior caso com n testes, sem resultado. No algoritmo primordial. Pegava-se dois pares falhos e tínhamos + 4 chances. n+4. Depois o Ralph, o melhorou e caímos em n +3. O que havia reparado é que para tirar pelo menos n baterias defeituosas, pegando um conjunto de n+ 1 baterias, se faz necessário (n+1)*n/2 testes. O que dá uma relação número de testes : mínimo de n baterias defeituosas de (n+1)/2, o que dá uma melhor relação para pelo menos uma bateria, que dá 1. Para pelo menos duas, 3/2 e só vai piorando. Portanto, o método usado por Ralph, por sentimento não podia ser o melhor. Mas como melhorá-lo? Simples, por demais, embora só atinei agora. É só lembrar que quando somamos 4 a n, nós estamos desperdiçando dois testes que nós já o fizemos antes. Portanto para não esquecer: Separa-se 4 bateias e n-2 testes com as 2n-4 restantes. Ai se faz os 4 testes, no máximo com essas últimas. Teremos então n+2 igual ao resultado do item a) Sds, PJMS Em dom, 24 de fev de 2019 às 19:10, Ralph Teixeira escreveu: > 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 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é 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é >>> 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 < jefersonram...@gmail.com> 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. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] Torneio das Cidades ( Número mínimo de Tentativas )
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 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é 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é >> 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 < >>> jefersonram...@gmail.com> 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.
[obm-l] Re: [obm-l] Re: [obm-l] Torneio das Cidades ( Número mínimo de Tentativas )
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é 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é > 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 < >> jefersonram...@gmail.com> 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.
[obm-l] Re: [obm-l] Torneio das Cidades ( Número mínimo de Tentativas )
Boa tarde! Será que não sai pelo princípio de gavetas? Aí garante-se que é mínimo? Sds, PJMS. Em dom, 24 de fev de 2019 às 17:02, Pedro José escreveu: > 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é > 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 < >> jefersonram...@gmail.com> 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.
[obm-l] Re: [obm-l] Torneio das Cidades ( Número mínimo de Tentativas )
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é 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 < > jefersonram...@gmail.com> 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.
[obm-l] Re: [obm-l] Torneio das Cidades ( Número mínimo de Tentativas )
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 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.
[obm-l] Re: [obm-l] Torneio das Cidades ( Número mínimo de Tentativas )
b) Tem um jeito melhor: comece testando ab,ac,bc. Se der errado, significa que tem (pelo menos) 2 ruins aqui, entao sobram 2n-3 baterias onde tem mais boas do que ruins... O que eh exatamente o item (a)! (Bom, trocando n por n-2). Entao pelo metodo da (a), conseguimos um par de baterias boas em (n-2)+2=n tentativas extra. Total: n+3 tentativas! Agora, isso eh o otimo? Abraco, Ralph. On Sun, Feb 24, 2019 at 2:55 PM Ralph Teixeira wrote: > 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 > 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.
[obm-l] Re: [obm-l] Torneio das Cidades ( Número mínimo de Tentativas )
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 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.
[obm-l] Re: [obm-l] Torneio das Cidades ( Número mínimo de Tentativas )
Já vi um problema parecido da OBM que dava pra resolver usando o teorema de Turan. Pra esse imaginei assim, VC separa as baterias em dois grupos, B das boas e R das ruins e liga duas se foram testadas juntas. O numero máximo de arestas que dá pra colocar sem a lampada acender é |B|×|R| +|R|×(|R|-1)/2. Em dom, 24 de fev de 2019 11:40, Jeferson Almir 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.
