From: eusoupedroso...@hotmail.com
To: obm-l@mat.puc-rio.br
Subject: RE: [obm-l] Re: [obm-l] Re: [obm-l] RE: [obm-l] Quantidade mínnima de
tentativas
Date: Fri, 13 Jan 2012 21:41:41 +0000
Pensei assim:
Separando a dupla AB temos 3 possibilidades:
1)A e B funcionam
2)Somente um dos dois funciona
3)Nenhum dos dois funcionam
Agora veremos com quantos testes conseguimos verificar cada hipótese
1) Supondo hipótese 1 verdadeira, existem duas que funcionam entre C D E F G H,
logo 5 testes bastam para essa hipótese
AB( C;D;E;F;G ) por exemplo
2) Supondo hipótese 2 verdadeira existem 3 que funcionam entre C D E F G H,
Assim podemos separar em duplas (CD;EF;GH) e dizer que?
2.1)ou exisste uma dupla com duas funcionando, e consequentemente uma sem
nenhum e uma com um.
2.2)ou cada dupla tem apenas uma funcionando.
2.1) Para testar 2.1) 6 testes bastam A(CD;EF;GH) e B(CD;EF;GH)
2.2) Para testar 2.2) 8 testes bastam, permutando duas duplas, por exemplo
A(CE;CF;DE;DF) e B(CE;CF;DE;DF)
3) Supondo a hipótese 3 verdadeira, sabemos que existem 4 que funcionam entre C
D E F G H, e de certa forma o problema é o mesmo porém com 6 pilhas ao invés de
8, assim sabemos que seguindo esse método teremos menos de 2*(5+6+8) = 38 casos
Para esse teste supomos:
3.1) C e D funcionam
3.2) C ou D funciona
3.3) C e D não funcionam
3.1) Supondo 3.1 verdadeiro precisamos de 3 testes CD(E;F;G), pois em E F G H
tem pelo menos 2 que funcionam
3.2) Supondo 3.2 verdadeiro precisamos de 4 testes C(EF;GH) e D(EF;GH), pois
em EF GH tem pelo menos uma dupla com duas que funcionam.
3.3) Tecnicamente não temos que testar mais nada, pois já sabemos que qualquer
combinação de E F G H irá funcionar, mas se quiser trocar de canal, mais um
teste é necessário, Assim 1+4+3+8+6+5 = 27
Obviamente não vejo uma maneira clara de provar que isso é o mínimo, logo, quem
dá menos?
> 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
> =========================================================================
