Olá a todos da lista
Primeiramente muito obrigado ao Ralph, Bruno, Hugo e todos os outros que me
ajudaram nesse problema
Eu estava viajando e só fui ver hoje as resoluções, aliás fantásticas
Um problema similar a este está na revista eureka! 24
http://www.obm.org.br/export/sites/default/revista_eureka/docs/Eureka_24.pdf
(para quem ainda não viu)
A diferença que que no caso o rádio funcionava com 2 pilhas (não 3)
Dei uma lida em teoria dos grafos para tentar resolver o problema
Enfim, na resolução Gabriel fornece um meio (um algoritimo) para se resolver o
problema com 7 testes e depois prova que com 6 testes é possível que as pilhas
carregadas não sejam usadas.Para isso ele usa teoria dos grafos deste modo:
Constrói um grafo com 8 vértices em que cada aresta que liga os vértices (a, b)
sinaliza que a não foi testada com b. Logo se fosse possível com 6 tentativas,
Dado um grafo qualquer desse modo e tirando 6 arestas nunca poderia ser
possível que todas as arestas que ligassem 2 pilhas carregadas estivessem
dentro desse grafo. Mas tal grafo tem 22 arestas e qualquer grafo com mais de
21 tem um K4 (ou seja, se os vértices do K4 fossem as pilhas carregadas, elas
não seriam testadas juntas).
Pensei em um modo de generalizar o problema, ou seja, em vez de uma aresta
sinalizar não testar as pilhas (a, b), que fosse um triângulo (ou um K3)Mas
ainda não cheguei a nada. Na verdade seria um ótimo modo de provar que não é
possível com menos que k pilhas, por exemplo
Alguém chegou a algo?
[]'sJoão
Date: Tue, 17 Jan 2012 13:35:02 -0200
Subject: [obm-l] Re: [obm-l] Fwd: [obm-l] Quantidade mínnima de tentativas
From: hfernande...@gmail.com
To: obm-l@mat.puc-rio.br
Valeu, Ralph... Agora sim, são 22... será que ainda dá pra baixar mais? Depois
vou tentar mais um pouco. Abraços e obrigado pela correção.
Hugo.
Em 16 de janeiro de 2012 22:31, Ralph Teixeira <ralp...@gmail.com> escreveu:
---------- 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
=========================================================================
