Amigo meu consegui ter uma ideia pra esse problema, to encaminhando aqui embaixo. Entao aparentemente a resposta eh 20 =p
---------- Mensagem encaminhada ---------- De: Lucas Pierezan Magalhães <[email protected]> Data: 19 de janeiro de 2012 23:26 Assunto: Re: [acm-ufrj] Fwd: [obm-l] Re: [obm-l] Fwd: [obm-l] Quantidade mínnima de tentativas Para: [email protected] então, de fato dá pra resolver o problema com uma generalização do teorema de turán. Parece que a resposta é 20. O link da Eureka não funcionou aqui mas tenho esse que explica a redução no caso "fácil" (2 pilhas para funcionar) : web.viu.ca/bigelow2/Problem%201125%20Solution.pdf Seja n pilhas , b boas e precisa de f para funconar. O problema das pilhas é equivalente ao problema de determinar o maior número de hiperarestas (todas de tamanho f) que você pode colocar em um hipergrafo (com n vértices) sem que apareça uma clique de tamanho b. (explicação de pq no final do email) Acontece que esse problema para f > 2 está em aberto [1]. (Para f=2 é o turán's theorem) Até o caso b = 4 e f = 3 (que é o caso do problema dado) está em aberto! Mas existe uma conjectura de uma fórmula e está provado que funciona para n <= 13 [2]. Por essa fórmula chega-se a conclusão que dá pra fazer com 20 testes! É possível também (para esse caso b=4 e f=3) descobrir como os testes devem ser feitos para bater com a fórmula da conjectura [3]. Equivalência dos problemas : Imagine que você começa tem os n vértices e todas as hiperarestas (ou seja todos os C(n,f) testes possíveis) . Cada vez que você faz um teste (que é escolher f vértices) você retira a hiperaresta que é o conjunto dos f vértices que você testou junto. Depois de t testes você termina com um subgrafo H que é composto por todas as hiperarestas que são os conjuntos de testes que você não realizou. 1 - Se você faz t testes H tem C(n,f) - t hiperarestas. 2 - Se você necessariamente descobre a solução dps de t testes então não pode haver "clique" de tamanho b em H (caso contrário as pilhas boas poderiam ser exatamente essas b pilhas que você não fez nenhuma teste composto por selecionar subconjunto de temanho f dessas b boas). 3 - Se existe grafo H com C(n,f) - t hiperarestas e este não tem clique de tamanho b essas t hiperarestas que você removeu são t testes que quando realizados algum teria que funcionar (caso contrário teria K_b em H). Minimizar t é maximizar o número de arestas de H. Logo, achar o t mínimo corresponde a achar um grafo H com o maior número de arestas possives e que não tem K_b dentro dele. Referências: [1] shell.cas.usf.edu/~bnagle/boca.pdf [2] http://www.math.cornell.edu/~froh/sum3a.html [3] www.math.cornell.edu/~froh/*turan*conj.pdf
