Arrumei um jeito com 27 tentativas mas não to conseguindo enviar e-mail para o grupo, se este teste passar envio a solução
> Date: Thu, 12 Jan 2012 15:36:44 +0100 > Subject: [obm-l] Re: [obm-l] Re: [obm-l] RE: [obm-l] Quantidade mínnima de > tentativas > From: bernardo...@gmail.com > To: obm-l@mat.puc-rio.br > > 2012/1/12 Bernardo Freitas Paulo da Costa <bernardo...@gmail.com>: > > 2012/1/12 Ralph Teixeira <ralp...@gmail.com>: > >> Nao precisa testar 53 trincas nao! Rapidinho, arrumo um algoritmo com > >> 38 testes... > >> > >> Sejam ABCDEFGH as 8 pilhas, seja X o conjunto das 4 que funcionam. Ha > >> C(8,4)=70 possibilidades para X. > >> > >> Agora, voce testa ABC; se NAO funcionar, isto jah elimina 5 > >> possibilidades para X (a saber, ABCD, ABCE, ABCF, ABCG, ABCH). > >> Teste CDE. Se nao funcionar, eliminamos ACDE, BCDE, CDEF, CDEG e CDEH. > >> EFG elimina mais 5; GHA elimina mais 5. > >> Tente agora ADF, CFH, EHB e GBD. Se nada disso funcionar, jah > >> eliminamos no total 40 possibilidades -- ateh aqui, todas disjuntas! > >> Explicitamente, sobram apenas as seguintes 30 possibilidades para X: > >> ABDE ABDH ABEF ABEG ABFG ABFH ACDG ACDH ACEF ACEG ACEH ACFG ADEG ADEH AEFH > >> BCDF BCDH BCEF BCEG BCFG BCGH BDEF BDFH BFGH CDFG CDGH CEGH DEFH DEGH DFGH > >> > >> Mesmo que voce agora escolha uma trinca de cada um desses 30 > >> conjuntos, seria um total de 8+30=38 testes. Mas ainda dah para > >> diminuir bastante, jah que varias trincas aparecem em varias dessas > >> quadras! > >> > >> Quem dah menos? :) > > 32 > > > >> Abraco, > >> Ralph > > > > Eu acho que é outra idéia (que eu acho também dá pra ser "escovada"), > > então aí vai: > > > > O princípio é "manter a simetria" (circular) das pilhas. > > Teste ABC, BCD, CDE, ... GHA, HAB. (8 testes). > > Se nada disso der certo, não tem 3 pilhas boas em série, que eu noto > > "bbb". Portanto, bb => a próxima é r. > > > > Teste em seguida ABD, BCE, ... GHB, HAC. > > Se nada disso der certo, não tem também "bbrb", portanto "bb => rr". > > > > Para a "simetria", teste ACD, BDE, ..., GAB, HBC. > > Isso impede "brbb", portanto "brb => r" > > > > Para fechar a simetria, teste ABE, BCF, ..., GHC, HAD. > > Isso impede "bbrrb", logo "bb => rrr". > > > > Agora, se houvesse um "bb" em algum momento, teríamos logo depois um > > rrr. A situação é a seguinte: > > bb rrr ??? > > > > Sabemos que temos que colocar 2 bons, nos ??? que sobram. Só que o > > último também não pode ser um b (afinal de contas, não há 3 bons > > consecutivos). Portanto, é um "bb rrr bb r", que também é impossível > > visto que temos um bb r b cíclico. > > > > Assim, não há "bb", e portanto podemos ficar com as 6 primeiras que > > haverá 3 bons e 3 ruins. Há 20 = C(6,3) combinações possíveis para as > > 6 pilhas. Mas acontece que a gente já testou > > ABC, BCD, CDE, DEF (4) > > ABD, BCE, CDF (3) > > ACD, BDE, CEF (3) > > ABE, BCF (2) > > 12 possibilidades que não deram certo. Restam apenas 8, uma delas com > > certeza vai dar. > > > > O que dá 8+8+8+8 ("simétricos") + 8 (restos dos 6 que a gente não testou). > Opa, ninguém viu o erro, mas 5*8 = 40. Que é pior do que a solução do Ralph. > > MAAAAAAS, eu acho que dah pra corrigir e ainda ficar um pouco melhor > do que os 38. > > Assim: quase no final, a gente jah excluiu bbb, bbrb, brbb, portanto > se houver um "bb", tem que ser seguido (e precedido) de dois ruins. O > que quer dizer que a unica configuraçao possivel com um "bb" é > bbrrbbrr (+ permutaçao circular, sempre). > Agora, a gente para com a simetria. Basta testar ABE, BCF, CDG (que é > o aeroporto de Paris) e DEH. Brincadeiras à parte, se nenhuma dessas 4 > acender, é que não temos bbrrbbrr (que é simétrica na metade, por isso > basta testar 4 das oito configuraçoes). Agora, escolha ABCDEF e teste > os 8 que sobraram. O mais legal é que não tanto faz pegar ABCDEF ou > qualquer permutação circular disso, porque do ultimo teste, que é > "assimétrico", soh temos 2 testes para alguns grupos, mas nao todos > (por exemplo, DEFGHA soh tem 1 teste). Corrigindo a minha aritmética, > dah 36 testes > > > A minha solução é meio "força bruta" comparada à do Ralph (que deve > > ser mais fácil de "optimizar", mas sei lá. De repente eu dei sorte com > > o método. > > > > Abraços, > > -- > > Bernardo Freitas Paulo da Costa > > > > -- > Bernardo Freitas Paulo da Costa > > ========================================================================= > Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~obmlistas/obm-l.html > =========================================================================