---------- Forwarded message ---------- From: Ralph Teixeira <[email protected]> Date: 2012/1/16 Subject: RE: [obm-l] Quantidade mínnima de tentativas To: [email protected]
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 <[email protected]>: > 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 <[email protected]> > 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 =========================================================================
