Bom, agora que o Ralph resolveu diminuir o número de tentativas, acho que é chegada a hora de dar uma versão um pouco mais "teoria dos grafos" como o proponente inicial queria.
Seguinto a solução do Ralph (a primeira), temos 70 = C(8,4) possibilidades para a configuração das pilhas em boas / ruins. Cada teste elimina, no máximo, 5 possibilidades. Pense assim: cada configuração é identificada pela seqüência de letras que representam as pilhas que funcionam. Se você testou ABC, e não acendeu, com certeza ABCD, ABCE, ABCF, ABCG nem ABCH são as 4 pilhas que funcionam. No final dos testes, se você tem uma trinca xyz que você sabe que funciona, isso quer dizer que a quadra de 4 pilhas é uma entre xyzt, e há 5 possibilidades para t. Cada teste, portanto, "cobre" uma parte das quadras (5 no máximo), e no final você terá no máximo 5 quadras cobertas (e se for exatamente esse caso, essas quadras têm interseção *tripla*), ou seja, você cobriu 65 quadras, com um máximo de 5 quadras por teste, isso dá 13 testes no mínimo. Vamos tentar fazer um grafo com o problema. Considere 70 + 56 vértices, correspondendo às 70 quadras e 56 trincas (= testes) possíveis a fazer. O objetivo é cobrir o máximo dos vértices das quadras, usando o mínimo dos vértices das trincas. Assim, podemos pensar que o teste ABC retira o vértice ABC e os 4 vértices ABCD, ABCE, ABCF, ABCG e ABCH do grafo. Mas pra ser um grafo, não tem graça se só forem vértices (porque aí basta pensar em conjuntos, né). Vamos botar umas arestas no grafo. Eu acho que uma solução natural seria ligar cada tripla com as 5 quadras que ela "apaga" quando a gente testa a tripla. Assim, cada quadra está ligada com as 4 trincas que você pode obter retirando uma das letras. E quando é que a gente sabe que uma trinca não funciona? Estamos invertendo o problema, mas a idéia é essa: se as 5 quadras ligadas numa trinca já tiverem sido "apagadas", então a trinca não é boa. Porquê? Basta pensar de novo no ABC: se 5 combinações não deram certo, com certeza é porque há uma pilha ruim em ABC. A pergunta que resta é ver qual é saber quando uma trinca funciona. É claro que quando restam apenas 5 quadras não apagadas em torno de uma mesma trinca, ela tem que funcionar. Acho que vale a pena tentar mostrar que isso é uma condição necessária (ou seja, ter no máximo uma trinca que esteja ligada a 5 quadras que ainda não foram apagadas, e qualquer outra configuração ser uma "sub-configuração" disso). Se o que eu falei está certo, a gente tem um limite mínimo de 13 *de verdade* (o 13 antes era apenas "seguindo o algoritmo"). E depois a gente tem que contar como os "recobrimentos" se recobrem a si mesmos para ir aumentando pouco a pouco o limite mínimo. Uma idéia nessa linha: Para um recobrimento dado pela trinca xyz intersectar um outro pqr, tem que haver um par comum. A cobertura "maximalmente espaçada" é portanto dada por trincas que não tem pares em comum (mas ela provavelmente não vai cobrir as 70 quadras). Começando com ABC, isso exclui todas que têm AB, AC ou BC. (são 15). Pegue em seguida BDE, CEF, BFG, CGH, ADH (ou BDH). Fizemos portanto 6 testes "ótimos". (Há 8*7/2 = 28 pares, perdemos 3 a cada vez, deve dar pra fazer 9 testes ótimos, mas só o fato de não ser divisível perfeitamente me deixa pensando). No nosso caso, devemos tentar casar além desses os pares: AE, AF, AG, BH, CD, DF, DG, EG, EH, FH. Isso sugere AEG, mas repare que é o único que pode ser formado (os 3 pares têm que estar na lista). Problema intermediário: será que a gente consegue achar o maior número de coberturas "disjuntas" ? Será que a configuração que a gente obtém assim é "a melhor possível" ? Veja bem, mudando de estratégia, talvez a gente não comece "cobrindo tudo", mas seja mais eficiente "no final", porque depois de "apertar" as coberturas, talvez a gente tenha que usar várias vezes uma trinca para excluir uma ou duas quadras apenas... Será que essa estratégia pelo menos mantém a "simetria" da situação? Ou será que de qualquer forma fica assimétrico? Será que dá para minimizar a perda simetria? Agora, o que é difícil de ver MESMO é o que resta como grafo... Esse comecinho eu fiz porque eu desenhei todos os hexágonos do tipo ABC - ABCD - ABD - ABDE - ABE - ABCE - ABC que partem de ABC (e variando D e E) formando uma configuração simétrica de pentágono para os 5 raios que partem de ABC e tentando o máximo de simetria possível, mas como é ímpar acabou que a última parte (ligar as triplas que partem de ABCG com as de ABCH pelas "outras quadras") ficou meio invertida. 2012/1/17 Ralph Teixeira <[email protected]>: > ---------- 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 > ========================================================================= -- 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 =========================================================================
