[obm-l] Re: [obm-l] RE: [obm-l] combinatória
MAS NESSE CASO, A FÓRMULA NÃO ESTARIA CONSIDERANDO POR EXEMPLO O CASO: 1+14 E 14 + 1 COMO DISTINTOS? EU GOSTARIA DE DESCONSIDERAR ESSES CASOS, OU EU ME ENGANEI? AGRADEÇO O RETORNO. = 2012/1/15 João Maldonado joao_maldona...@hotmail.com Na verdade sabendo que um termo pode ser 0 o numero de formas é infinito mas você pode usar a formula C(14+ n, n-1) para um numero limitado de variaveis (a formula ja foi facilmente demonstrada aqui na lista ) Ou até C(14, n- 1 ) com n variando de 1 a 15, para o numeero de solucoes inteiras positivas []s João -- From: mat.mo...@gmail.com Date: Sat, 14 Jan 2012 12:54:41 -0200 Subject: [obm-l] combinatória To: obm-l@mat.puc-rio.br GOSTARIA DE UMA AJUDA EM RELAÇÃO A ESTE PROBLEMA: DE QUANTAS FORMAS PODEMOS REPRESENTAR O NÚMERO 15 COMO SOMA DE VÁRIOS NÚMEROS NATURAIS? A DIFICULDADE É QUE ESTOU CAINDO EM VÁRIOS CASOS, ACREDITO QUE DEVA TER UMA MANEIRA MAIS RÁPIDA PARA ISSO, TENTEI COMBINAÇÕES COMPLEMENTARES ANALISANDO A COMBINAÇÃO DOS RESTOS PARA SER 15, MAS SÃO MUITOS CASOS. OBRIGADO
[obm-l] Re: [obm-l] RE: [obm-l] RE: [obm-l] Re: [obm-l] Re: [obm-l] RE: [obm-l] Quantidade mínnima de tentativas
Fiz assim: Considere três grupos: abc, de, fgh Testo o primeiro grupo (abc): se falhar este grupo tem 1 ou 2 pilhas boas. Testo o terceiro grupo (fgh): se falhar este grupo tem 1 ou 2 pilhas boas. Testo cada elemento do segundo grupo contra os pares formados pelos elementos dos outros grupos. São 12 testes, a saber: abd, acd, bcd, abe, ace, bce e tb fgd, fhd, ghd, fge, fhe, ghe Note que o segundo grupo (de) pode ter 0, 1 ou 2 pilhas boas. 1) Se tiver 0 então existe duas boas no grupo (abc) e duas boas em (fgh) 2) Se tiver 1 boa, então um dos grupos (abc) ou (fgh) tem duas boas (e o outro uma). Nesse caso, um dos doze testes acima teria funcionado. Logo, se não funcionou, podemos excluir essa hipótese. 3) Se tiver duas boas, então cada um dos grupos (abc) e (fgh) tem só 1 boa também. Se pensarmos primeiro no caso 3, podemos testar (ade), (bde), (cde) e uma vai funcionar. Se não funcionar, resta o caso 1, e os testes (abf), (abg) e (abh) devem funcionar - se não funcionar, então com certeza c funciona junto com fg ou fh, ou seja, temos mais dois testes, (cfg) e (cfh) Então no pior caso temos, 1+1+12+3+3+2 = 22 Estou certo ou há alguma falha no raciocínio? Abs a todos. Hugo. Em 13 de janeiro de 2012 23:00, Breno Vieira brenovieir...@hotmail.comescreveu: Como eu ja disse, achei 23: 1. Teste ABC, se nao funcionar sabemos que pelo menos uma entre A, B e C nao funciona. 2. Teste as combinacoes entre DEFGH (DEF,DEG,DEH,DFG,DFH,DGH,EFG,EFH,EGH,FGH), se nenhuma funcionar temos que tres entre DEFGH nao funcionam, portando duas entre ABC e duas entre DEFGH funcionam. 3. Sabemos que AB, AC ou BC sao formadas por duas que funcionam e que pelo menos uma entre D,E,F,G funciona, bastam entao mais 12 testes totalizando 23. PS:Ainda tem mais outros dois algoritmos um pouco mais complicados que eu fiz e que tambem chegam em 23. Quem da menos?
Re: [obm-l] Fobonacci
Bom, eu não sabia disso mas agora que você falou... A recorrência que define os termos de ordem ímpar da seq. de Fibonacci pode ser obtida assim: F(2n+1)=F(2n)+F(2n-1) F(2n)=F(2n-1)+F(2n-2) F(2n-2)=F(2n-1)-F(2n-3) (tô fazendo um esforço para só deixar os de ordem ímpar do lado direito) Então F(2n+1)=3F(2n-1)-F(2n-3) Agora deixa eu ver os alegados quadrados. Seriam: F(n)5F(n)^2-4 1 1=1^2 2 16=4^2 5 121=11^2 13 841=29^2 ...... Será que a sequencia da direita tem alguma ordem razoável... Digo, olhando para 1,4,11,29..., qual é a recorrência? Hmmm, parece que cada termo é 3 vezes o anterior menos ao anteanterior, de novo! Bom, mas isso tudo é chute, vamos ver se a gente consegue MOSTRAR isso. TEOREMA: Defina A(0)=1, A(1)=2 e A(n+1)=3A(n)-A(n-1) (n=2). Defina também B(0)=1, B(1)=4 e B(n+1)=3B(n)-B(n-1). Afirmo que: i) 5A(n)^2-4=B(n)^2 ii) você já vai ver que preciso de algo mais aqui. Prova: i) Para n=0 e n=1 é só verificar direto. Por indução, se a propriedade vale para n=k e n=k-1, então: 5A(k+1)^2-4 = 5(3A(k)-A(k-1))^2-4 = 45A(k)^2-30A(k)A(k-1)+5A(k-1)^2-4 = (9B(k)^2+36)-30A(k)A(k-1)+B(k-1)^2 Ah, droga, eu não tenho a mínima ideia do que fazer com aquele A(k)A(k-1)... Se fosse algo conhecido, razoável tipo, eu acho que a coisa toda vai dar (3B(k)-B(k-1))^2, né? Para isso valer, eu precisava que fosse 36-30A(k)A(k-1)=-6B(k)B(k-1), isto é, eu queria que fosse 5A(k)A(k-1)=B(k)B(k-1)+6... Como provar isto? Façamos por indução, ora! Então adicione lá no enunciado o seguinte: ii) 5A(n)A(n-1)=B(n)B(n-1)+6 Esta propriedade claramente vale para n=1 e n=2. Agora o passo de indução (note que estou usando (i) com n=k, então a indução é feita com (i) e (ii) ao mesmo tempo!): 5A(k+1)A(k) = 5(3A(k)-A(k-1))A(k) = 15A(k)^2-5A(k)A(k-1) = (3B(k)^2+12)-B(k)B(k-1)-6 = = 3B(k)^2-B(k)(3B(k)-B(k+1))+6 = B(k)B(k+1)+6 Pronto! Este era o pedaço que faltava para terminar a indução em (i). Acabou! Abraço, Ralph P.S.: Agora, para DESCOBRIR que estes números funcionam, dê uma olhada na teoria de Equação de Pell, que ajuda a resolver coisas do tipo 5n^2-4=p^2. 2012/1/15 marcone augusto araújo borges marconeborge...@hotmail.com: Provar q a equação x^2+y^2+z^2=3xyz tem infinitas soluções inteiras. Essa questão ja foi resolvida na lista Um colega tentou uma soluçao diferente: Fez y=n e z=1,encontrando x^2 - 3nx +n^2 +1=0 x= (3n + - raiz(5n^2 - 4))/2 5n^2 - 4 deve ser um quadrado perfeito Tentei mostrar q existem infinitos valores de n para os quais 5n^2 - 4 é um quadrado perfeito e não consegui Mas o colega me informou q para n igual aos termos de ordem impar da sequencia de fibonacci, a referida expressão é um quadrado perfeito(1,2,5,13,34,...) Não sabemos provar Alguem poderia esclarecer? = 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] Fobonacci
Já que o Ralph mandou uma solução recorrência mate-mágica, eu vou completar com uma solução Força bruta mate-mágica. Você conhece a fórmula dos números de Fibonacci, né? F(n) = (a^n - b^n)/raiz(5), onde 2a = 1 + raiz(5) e 2b = 1 - raiz(5). Bom, isso quer dizer que 5 * F(n)^2 = (a^n - b^n)^2 = a^(2n) - 2 a^n b^n + b^(2n). Bom, 5 * F(n)^2 é um quadrado (mas de um número irracional, porque tem um raiz(5)). Mas não é isso que a gente quer. Lembra que tem um -4. Mas como conseguir fazer o -4 ajudar a formar um quadrado ??? É aqui que entra a mágica dos Fibonacci: a*b = -1. Assim, o termo cruzado é simplesmente -2 * (-1)^n. Que é -2 quando n é par, +2 quando n é ímpar. E quando n é impar, somando com o -4, isso vira -2, ou seja, troca o sinal. Trocando o sinal, fica a^(2n) + 2 a^n b^n + b^(2n) = (a^n + b^n)^2. Aqui, você pode terminar de vários jeitos. Note que os termos com raiz(5) vão cancelar (porque a tem 1 + raiz(5) e b tem 1 - raiz(5)), mas o maior problema mesmo é que tem um fator 2^n no denominador. Eu faria assim (pensando um pouco como o Ralph) : a^n + b^n satisfaz a mesma recorrência de Fibonacci (porque a^2 = a + 1 e b^2 = b + 1, portanto a^(n+2) = a^(n+1) + a^n e idem para b, e daí a soma também). Vejamos os primeiros valores a^0 + b^0 = 1 + 1 = 2 (inteiro) a^1 + b^1 = (1 + raiz(5))/2 + (1 - raiz(5))/2 = 1 (inteiro) Daí, todos os valores de a^n + b^n são inteiros também ! Pra conferir: n : F(n) : a^n + b^n 0 : 0 : 2 (5*0 + 4 = 4 = 2^2) 1 : 1 : 1 (5*1 - 4 = 1 = 1^2) 2 : 1 : 3 (5*1 + 4 = 9 = 3^2) 3 : 2 : 4 (5*4 - 4 = 16 = 4^2) 4 : 3 : 7 (5*9 + 4 = 49 = 7^2) 5 : 5 : 11 (5*25 - 4 = 121 = 11^2) 6 : 8 : 18 (5*64 + 4 = 324 = 18^2) 7 : 13 : 29 (5*169 - 4 = 841 = 29^2) (eu pensei que isso ia dar certo porque, veja bem, 5 * F(2n+1)^2 quer dizer que a raiz(5) do denominador vai embora, daí que devia dar pra simplificar) Antes de acabar, também uma fórmula com quadrados dentro de Fibonacci: F(n)^2 = F(n-1)*F(n+1) - (-1)^n, e no nosso caso, a gente tem um treco do tipo 5 F(n)^2 - 4(-1)^n = C(n)^2, e eu quase aposto que dá pra mostrar isso direto... E como disse o Ralph: é claro que as soluções de 5n^2 - 4 = m^2 vão satisfazer uma recorrência (Pell), e ele sabia disso, portanto ele fez as contas e achou a recorrência. Eu tive preguiça de achar a recorrência, mas acabei achando uma fórmula com um - 4 (-1)^n ;) Abraços, -- Bernardo Freitas Paulo da Costa 2012/1/16 Ralph Teixeira ralp...@gmail.com: Bom, eu não sabia disso mas agora que você falou... A recorrência que define os termos de ordem ímpar da seq. de Fibonacci pode ser obtida assim: F(2n+1)=F(2n)+F(2n-1) F(2n)=F(2n-1)+F(2n-2) F(2n-2)=F(2n-1)-F(2n-3) (tô fazendo um esforço para só deixar os de ordem ímpar do lado direito) Então F(2n+1)=3F(2n-1)-F(2n-3) Agora deixa eu ver os alegados quadrados. Seriam: F(n) 5F(n)^2-4 1 1=1^2 2 16=4^2 5 121=11^2 13 841=29^2 ... ... Será que a sequencia da direita tem alguma ordem razoável... Digo, olhando para 1,4,11,29..., qual é a recorrência? Hmmm, parece que cada termo é 3 vezes o anterior menos ao anteanterior, de novo! Bom, mas isso tudo é chute, vamos ver se a gente consegue MOSTRAR isso. TEOREMA: Defina A(0)=1, A(1)=2 e A(n+1)=3A(n)-A(n-1) (n=2). Defina também B(0)=1, B(1)=4 e B(n+1)=3B(n)-B(n-1). Afirmo que: i) 5A(n)^2-4=B(n)^2 ii) você já vai ver que preciso de algo mais aqui. Prova: i) Para n=0 e n=1 é só verificar direto. Por indução, se a propriedade vale para n=k e n=k-1, então: 5A(k+1)^2-4 = 5(3A(k)-A(k-1))^2-4 = 45A(k)^2-30A(k)A(k-1)+5A(k-1)^2-4 = (9B(k)^2+36)-30A(k)A(k-1)+B(k-1)^2 Ah, droga, eu não tenho a mínima ideia do que fazer com aquele A(k)A(k-1)... Se fosse algo conhecido, razoável tipo, eu acho que a coisa toda vai dar (3B(k)-B(k-1))^2, né? Para isso valer, eu precisava que fosse 36-30A(k)A(k-1)=-6B(k)B(k-1), isto é, eu queria que fosse 5A(k)A(k-1)=B(k)B(k-1)+6... Como provar isto? Façamos por indução, ora! Então adicione lá no enunciado o seguinte: ii) 5A(n)A(n-1)=B(n)B(n-1)+6 Esta propriedade claramente vale para n=1 e n=2. Agora o passo de indução (note que estou usando (i) com n=k, então a indução é feita com (i) e (ii) ao mesmo tempo!): 5A(k+1)A(k) = 5(3A(k)-A(k-1))A(k) = 15A(k)^2-5A(k)A(k-1) = (3B(k)^2+12)-B(k)B(k-1)-6 = = 3B(k)^2-B(k)(3B(k)-B(k+1))+6 = B(k)B(k+1)+6 Pronto! Este era o pedaço que faltava para terminar a indução em (i). Acabou! Abraço, Ralph P.S.: Agora, para DESCOBRIR que estes números funcionam, dê uma olhada na teoria de Equação de Pell, que ajuda a resolver coisas do tipo 5n^2-4=p^2. 2012/1/15 marcone augusto araújo borges marconeborge...@hotmail.com: Provar q a equação x^2+y^2+z^2=3xyz tem infinitas soluções inteiras. Essa questão ja foi resolvida na lista Um colega tentou uma soluçao diferente: Fez y=n e z=1,encontrando x^2 - 3nx +n^2 +1=0 x= (3n + - raiz(5n^2 - 4))/2 5n^2 - 4 deve ser um quadrado perfeito Tentei mostrar q
[obm-l] Re: [obm-l] Re: [obm-l] RE: [obm-l] RE: [obm-l] Re: [obm-l] Re: [obm-l] RE: [obm-l] Quantidade mínnima de tentativas
Amigo meu fez da seguinte forma: Suponha que as 8 pilhas sejam divididas em 3 grupos: ABC | DEF | GH (1) ABC tem 3 pilhas carregadas - 1 teste (2) DEFGH tem 3 pilhas carregadas - C(5,3) = 10 testes. Obs.: Como DEFGH não tem 3 pilhas carregadas e ABC não tem 3, ambos tem, obrigatoriamente, 2 pilhas carregadas Configurações Possíveis: * ABC tem 2 * DEF tem 0, 1 ou 2 * GH tem 0, 1 ou 2 (3) GH tem 2 pilhas carregadas: Como ABC tem 2 também, precisamos apenas de 2 testes. Obs.: Agora, podemos voltar a atenção para DEF Configurações Possíveis: * ABC tem 2 * DEF tem 1 ou 2 * GH tem 0 ou 1 (4) Testar 2 de ABC com 1 de DEF = C(3,2) * C(3,1) = 9 testes TOTAL: 1 + 10 + 2 + 9 = 22 testes Em 16 de janeiro de 2012 10:36, Hugo Fernando Marques Fernandes hfernande...@gmail.com escreveu: Fiz assim: Considere três grupos: abc, de, fgh Testo o primeiro grupo (abc): se falhar este grupo tem 1 ou 2 pilhas boas. Testo o terceiro grupo (fgh): se falhar este grupo tem 1 ou 2 pilhas boas. Testo cada elemento do segundo grupo contra os pares formados pelos elementos dos outros grupos. São 12 testes, a saber: abd, acd, bcd, abe, ace, bce e tb fgd, fhd, ghd, fge, fhe, ghe Note que o segundo grupo (de) pode ter 0, 1 ou 2 pilhas boas. 1) Se tiver 0 então existe duas boas no grupo (abc) e duas boas em (fgh) 2) Se tiver 1 boa, então um dos grupos (abc) ou (fgh) tem duas boas (e o outro uma). Nesse caso, um dos doze testes acima teria funcionado. Logo, se não funcionou, podemos excluir essa hipótese. 3) Se tiver duas boas, então cada um dos grupos (abc) e (fgh) tem só 1 boa também. Se pensarmos primeiro no caso 3, podemos testar (ade), (bde), (cde) e uma vai funcionar. Se não funcionar, resta o caso 1, e os testes (abf), (abg) e (abh) devem funcionar - se não funcionar, então com certeza c funciona junto com fg ou fh, ou seja, temos mais dois testes, (cfg) e (cfh) Então no pior caso temos, 1+1+12+3+3+2 = 22 Estou certo ou há alguma falha no raciocínio? Abs a todos. Hugo. Em 13 de janeiro de 2012 23:00, Breno Vieira brenovieir...@hotmail.comescreveu: Como eu ja disse, achei 23: 1. Teste ABC, se nao funcionar sabemos que pelo menos uma entre A, B e C nao funciona. 2. Teste as combinacoes entre DEFGH (DEF,DEG,DEH,DFG,DFH,DGH,EFG,EFH,EGH,FGH), se nenhuma funcionar temos que tres entre DEFGH nao funcionam, portando duas entre ABC e duas entre DEFGH funcionam. 3. Sabemos que AB, AC ou BC sao formadas por duas que funcionam e que pelo menos uma entre D,E,F,G funciona, bastam entao mais 12 testes totalizando 23. PS:Ainda tem mais outros dois algoritmos um pouco mais complicados que eu fiz e que tambem chegam em 23. Quem da menos?
[obm-l] Re: [obm-l] Re: [obm-l] RE: [obm-l] RE: [obm-l] Re: [obm-l] Re: [obm-l] RE: [obm-l] Quantidade mínnima de tentativas
Se no ultimo caso,no conunto fgh as que funcionam forem gh , nao precisaria testar cgh tbm? Em 16 de janeiro de 2012 10:36, Hugo Fernando Marques Fernandes hfernande...@gmail.com escreveu: Fiz assim: Considere três grupos: abc, de, fgh Testo o primeiro grupo (abc): se falhar este grupo tem 1 ou 2 pilhas boas. Testo o terceiro grupo (fgh): se falhar este grupo tem 1 ou 2 pilhas boas. Testo cada elemento do segundo grupo contra os pares formados pelos elementos dos outros grupos. São 12 testes, a saber: abd, acd, bcd, abe, ace, bce e tb fgd, fhd, ghd, fge, fhe, ghe Note que o segundo grupo (de) pode ter 0, 1 ou 2 pilhas boas. 1) Se tiver 0 então existe duas boas no grupo (abc) e duas boas em (fgh) 2) Se tiver 1 boa, então um dos grupos (abc) ou (fgh) tem duas boas (e o outro uma). Nesse caso, um dos doze testes acima teria funcionado. Logo, se não funcionou, podemos excluir essa hipótese. 3) Se tiver duas boas, então cada um dos grupos (abc) e (fgh) tem só 1 boa também. Se pensarmos primeiro no caso 3, podemos testar (ade), (bde), (cde) e uma vai funcionar. Se não funcionar, resta o caso 1, e os testes (abf), (abg) e (abh) devem funcionar - se não funcionar, então com certeza c funciona junto com fg ou fh, ou seja, temos mais dois testes, (cfg) e (cfh) Então no pior caso temos, 1+1+12+3+3+2 = 22 Estou certo ou há alguma falha no raciocínio? Abs a todos. Hugo. Em 13 de janeiro de 2012 23:00, Breno Vieira brenovieir...@hotmail.comescreveu: Como eu ja disse, achei 23: 1. Teste ABC, se nao funcionar sabemos que pelo menos uma entre A, B e C nao funciona. 2. Teste as combinacoes entre DEFGH (DEF,DEG,DEH,DFG,DFH,DGH,EFG,EFH,EGH,FGH), se nenhuma funcionar temos que tres entre DEFGH nao funcionam, portando duas entre ABC e duas entre DEFGH funcionam. 3. Sabemos que AB, AC ou BC sao formadas por duas que funcionam e que pelo menos uma entre D,E,F,G funciona, bastam entao mais 12 testes totalizando 23. PS:Ainda tem mais outros dois algoritmos um pouco mais complicados que eu fiz e que tambem chegam em 23. Quem da menos?
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] RE: [obm-l] RE: [obm-l] Re: [obm-l] Re: [obm-l] RE: [obm-l] Quantidade mínnima de tentativas
Tem razão, Pedro. Seriam 23 testes, então. Em 16 de janeiro de 2012 15:23, Pedro Nascimento pedromn...@gmail.comescreveu: Se no ultimo caso,no conunto fgh as que funcionam forem gh , nao precisaria testar cgh tbm? Em 16 de janeiro de 2012 10:36, Hugo Fernando Marques Fernandes hfernande...@gmail.com escreveu: Fiz assim: Considere três grupos: abc, de, fgh Testo o primeiro grupo (abc): se falhar este grupo tem 1 ou 2 pilhas boas. Testo o terceiro grupo (fgh): se falhar este grupo tem 1 ou 2 pilhas boas. Testo cada elemento do segundo grupo contra os pares formados pelos elementos dos outros grupos. São 12 testes, a saber: abd, acd, bcd, abe, ace, bce e tb fgd, fhd, ghd, fge, fhe, ghe Note que o segundo grupo (de) pode ter 0, 1 ou 2 pilhas boas. 1) Se tiver 0 então existe duas boas no grupo (abc) e duas boas em (fgh) 2) Se tiver 1 boa, então um dos grupos (abc) ou (fgh) tem duas boas (e o outro uma). Nesse caso, um dos doze testes acima teria funcionado. Logo, se não funcionou, podemos excluir essa hipótese. 3) Se tiver duas boas, então cada um dos grupos (abc) e (fgh) tem só 1 boa também. Se pensarmos primeiro no caso 3, podemos testar (ade), (bde), (cde) e uma vai funcionar. Se não funcionar, resta o caso 1, e os testes (abf), (abg) e (abh) devem funcionar - se não funcionar, então com certeza c funciona junto com fg ou fh, ou seja, temos mais dois testes, (cfg) e (cfh) Então no pior caso temos, 1+1+12+3+3+2 = 22 Estou certo ou há alguma falha no raciocínio? Abs a todos. Hugo. Em 13 de janeiro de 2012 23:00, Breno Vieira brenovieir...@hotmail.comescreveu: Como eu ja disse, achei 23: 1. Teste ABC, se nao funcionar sabemos que pelo menos uma entre A, B e C nao funciona. 2. Teste as combinacoes entre DEFGH (DEF,DEG,DEH,DFG,DFH,DGH,EFG,EFH,EGH,FGH), se nenhuma funcionar temos que tres entre DEFGH nao funcionam, portando duas entre ABC e duas entre DEFGH funcionam. 3. Sabemos que AB, AC ou BC sao formadas por duas que funcionam e que pelo menos uma entre D,E,F,G funciona, bastam entao mais 12 testes totalizando 23. PS:Ainda tem mais outros dois algoritmos um pouco mais complicados que eu fiz e que tambem chegam em 23. Quem da menos?
[obm-l] Fwd: [obm-l] Quantidade mínnima de tentativas
-- Forwarded message -- From: Ralph Teixeira ralp...@gmail.com Date: 2012/1/16 Subject: RE: [obm-l] Quantidade mínnima de tentativas To: obm-l@mat.puc-rio.br Hugo, nao desanime! Com um pequeno ajuste, sua solucao ainda dah 22 testes! (Eu tinha mandado isso para a lista, mas acho que foi barrado por causa de um anexo) Chutei o balde: coloquei as 70 opções para as 4 pilhas boas numa planilha Excel, em ordem lexicográfica, para ver bem o que está acontecendo. A cada passo, cobri as opções com os testes do Hugo usando cores bonitinhas (mando a planilha por E-mail para quem quiser, ajuda pacas a ver o que estamos fazendo). Então percebi algumas coisas na solução do Hugo... Resumindo cripticamente: 1. ABC e FGH (2 testes, eliminando 10 opções) 2a. (D ou E) com todos os pares em ABC (6t, -21op) 2b. (D ou E) com todos ou FGH (6t, -21op) 3a. ABE, BDE, CDE (2t, -9op) 3b. ABF, ABG (2t, -3op) 4. CFG, CFH, +CGH (-3t, -6op) Total: 22 testes, 70 opções. Note algo interessante: retirei ABH do passo 3b! Afinal, se ABH fosse bom, as pilhas boas seriam ABCH, ABDH, ABEH, ABFH ou ABGH. Mas em cada um desses casos, já teríamos uma combinação boa (respectivamente, em 1, 2a, 2a, 3b, 3b). Então ABH é desnecessário! Por outro lado, adicionei CGH no passo 4. O motivo é que a solução do Hugo não cobria os casos ACGH e BCGH, pelo menos não que eu tenha visto. Ou seja, deu 22 testes! Alguém dá menos? Abraço, Ralph 2012/1/16 Hugo Fernando Marques Fernandes hfernande...@gmail.com: Fiz assim: Considere três grupos: abc, de, fgh Testo o primeiro grupo (abc): se falhar este grupo tem 1 ou 2 pilhas boas. Testo o terceiro grupo (fgh): se falhar este grupo tem 1 ou 2 pilhas boas. Testo cada elemento do segundo grupo contra os pares formados pelos elementos dos outros grupos. São 12 testes, a saber: abd, acd, bcd, abe, ace, bce e tb fgd, fhd, ghd, fge, fhe, ghe Note que o segundo grupo (de) pode ter 0, 1 ou 2 pilhas boas. 1) Se tiver 0 então existe duas boas no grupo (abc) e duas boas em (fgh) 2) Se tiver 1 boa, então um dos grupos (abc) ou (fgh) tem duas boas (e o outro uma). Nesse caso, um dos doze testes acima teria funcionado. Logo, se não funcionou, podemos excluir essa hipótese. 3) Se tiver duas boas, então cada um dos grupos (abc) e (fgh) tem só 1 boa também. Se pensarmos primeiro no caso 3, podemos testar (ade), (bde), (cde) e uma vai funcionar. Se não funcionar, resta o caso 1, e os testes (abf), (abg) e (abh) devem funcionar - se não funcionar, então com certeza c funciona junto com fg ou fh, ou seja, temos mais dois testes, (cfg) e (cfh) Então no pior caso temos, 1+1+12+3+3+2 = 22 Estou certo ou há alguma falha no raciocínio? Abs a todos. Hugo. Em 13 de janeiro de 2012 23:00, Breno Vieira brenovieir...@hotmail.com escreveu: Como eu ja disse, achei 23: 1. Teste ABC, se nao funcionar sabemos que pelo menos uma entre A, B e C nao funciona. 2. Teste as combinacoes entre DEFGH (DEF,DEG,DEH,DFG,DFH,DGH,EFG,EFH,EGH,FGH), se nenhuma funcionar temos que tres entre DEFGH nao funcionam, portando duas entre ABC e duas entre DEFGH funcionam. 3. Sabemos que AB, AC ou BC sao formadas por duas que funcionam e que pelo menos uma entre D,E,F,G funciona, bastam entao mais 12 testes totalizando 23. PS:Ainda tem mais outros dois algoritmos um pouco mais complicados que eu fiz e que tambem chegam em 23. Quem da menos? = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
