[obm-l] off topic (livro de geometria)
Boa tarde. Alguém saberia me dizer se o livro de geometria Irmãos Marista é realmente bom? Abraços
RE: [obm-l] Soma e produto
Bom, vamos lá Primeiramente vamos usar 2 notações: Soma Única - Quando o produto de dois númeroos a e b do conjunto {2, ... 20} só tem uma possível soma.Ex: 38 tem soma única 21 pois os únicos números a e b do conjunto que têm o produto 38 é 19 e 2, já 18 tem somas 11 e 9 Produto único - Quando a soma de dois números a e b do conjunt {2, ... 20} só tem um possível produto.Ex: 4 têm produto único A única razão para Adriano dizer a Carla que ela não é capaz de saber a soma desses números é porque nuenhum dentre quaisquer dos possíveis produtos de tal soma tem soma única. Mas um produto só tem soma única se tiver 4 divisores (2 se não contarmos 1 e o próprio número). Ou seja , ou os produtos são 2³, 3³, 5³ ou qualquer produto entre 2 dos elementos do conjunto {2, 3, 5, 7, 11, 13, 17, 19} As somas que podemos descartar são: {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38} O 40 podemos eliminar pois tem produto únicoO 39 podemos eliminar pois tem produto únicoo 37 tem produtos 20.17 19,18, ambos com soma únicaO 35 tem produtos 20.15, 19.16, 18.17, ambos com soma únicaO 33 tem produtos 20.13, 19.14, 18.15, 17.16, ambos com soma únicaO 31 tem produtos 20.11, 19.12, 18.13, 17.14, 16.15, ambos com soma única Restaram O 12, 21, 23, 25, 27, 29 Vamos agora para a segunda afirmaçãoA única razão para Carla dizer a Antônio que ela agora é capaz de descobrir sua soma é porque agora, devido ao passo 1, seu produto ficou com soma única Abrindo os Produtos do 12 que não tem soma única - (10.2. 5 4), (8.4, 16.2)Escluindo: () Produtos do 21 que não tem soma única - (18.3, 9.6), (16.5, 10.8, 20. 4), (15.6, 18 5, 10.9), (12.9, 18.6)Excluindo: (18.3) , (16.5), (15.6, 18.5), (12.9) Produtos do 23 que não tem soma única - (20.3, 15.4, 12.5, 10.6), (18.5, 16.6, 10.9), (16.7, 14.8), (15.8, 20.6, 12.10), (14.9, 18.7)Excluindo: (20.3), (18.5), (16.7), (15.8), (14.9, 18.7) Produtos do 25 que não tem soma única - (20.5, 10.10), (18.7, 14.9), (16.9, 18.8, 12.12)Excluindo: (20.5), (18.7, 14.9), (16.9) Produtos do 27 que não tem soma única - (20.7, 14.10), (15.12, 18.10, 20.9)Excluindo: (20.7), (15.12, 20.9) Produtos do 29 que não tem soma única - (20.9, 18.10, 15.12)Excluindo: (20.9, 15.12) Ou seja, a soma é 27 e o produto é 20.7, os números são (20, 7) Vamos agora para a terceira afirmaçãoA única razão para Antônio dizer a Carla que ele agora é capaz de descobrir seu produto é porque agora, sua soma só tem um produto com soma única O único par que satisfaz todas as afirmações é o (20, 7) Portanto os númeors escolhidos foram (20, 7) UFAA! Espero que entenda a minha explicação (às vezes nem eu mesmo a entendo) []'sJoão From: marconeborge...@hotmail.com To: obm-l@mat.puc-rio.br Subject: [obm-l] Soma e produto Date: Thu, 19 Jan 2012 00:07:30 + Alguem elege dois numeros,nao necessariamente distintos,no conjunto de numeros naturais 2,...,20.O valor da soma destes numeros é dado somente a Adriano(A) e o valor do produto dos numeros é dado unicamente a Karla(K) Pelo telefone A diz a K:´´nao é possivel que descubras minha soma´´ Uma hora mais tarde,K diz a A:´´Ah! sabendo disso,ja sei quanto vale a sua soma´´! Mais tarde A chama outra vez a K e lhe informa:´´Poxa,agora eu tambem conheço o teu produto´´! Quais numeros foram eleitos?
RE: [obm-l] Soma e produto
Corrigindo 2 coisas: Quando eu falo: Mas um produto só tem soma única se tiver 4 divisores (2 se não contarmos 1 e o próprio número). Ou seja , ou os produtos são 2³, 3³, 5³ ou qualquer produto entre 2 dos elementos do conjunto {2, 3, 5, 7, 11, 13, 17, 19} Corrija por:Mas um produto só tem soma única se tiver 3 ou 4 divisores (1 ou 2 se não contarmos 1 e o próprio número). Ou seja , ou os produtos são 2³, 3³ ou qualquer produto entre 2 dos elementos do conjunto {2, 3, 5, 7, 11, 13, 17, 19} Quando eu falo:Ou seja, a soma é 27 e o produto é 20.7, os números são (20, 7) Deixe essa afirmaação para o final []'sJoão From: joao_maldona...@hotmail.com To: obm-l@mat.puc-rio.br Subject: RE: [obm-l] Soma e produto Date: Thu, 19 Jan 2012 16:11:44 -0200 Bom, vamos lá Primeiramente vamos usar 2 notações: Soma Única - Quando o produto de dois númeroos a e b do conjunto {2, ... 20} só tem uma possível soma.Ex: 38 tem soma única 21 pois os únicos números a e b do conjunto que têm o produto 38 é 19 e 2, já 18 tem somas 11 e 9 Produto único - Quando a soma de dois números a e b do conjunt {2, ... 20} só tem um possível produto.Ex: 4 têm produto único A única razão para Adriano dizer a Carla que ela não é capaz de saber a soma desses números é porque nuenhum dentre quaisquer dos possíveis produtos de tal soma tem soma única. Mas um produto só tem soma única se tiver 4 divisores (2 se não contarmos 1 e o próprio número). Ou seja , ou os produtos são 2³, 3³, 5³ ou qualquer produto entre 2 dos elementos do conjunto {2, 3, 5, 7, 11, 13, 17, 19} As somas que podemos descartar são: {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38} O 40 podemos eliminar pois tem produto únicoO 39 podemos eliminar pois tem produto únicoo 37 tem produtos 20.17 19,18, ambos com soma únicaO 35 tem produtos 20.15, 19.16, 18.17, ambos com soma únicaO 33 tem produtos 20.13, 19.14, 18.15, 17.16, ambos com soma únicaO 31 tem produtos 20.11, 19.12, 18.13, 17.14, 16.15, ambos com soma única Restaram O 12, 21, 23, 25, 27, 29 Vamos agora para a segunda afirmaçãoA única razão para Carla dizer a Antônio que ela agora é capaz de descobrir sua soma é porque agora, devido ao passo 1, seu produto ficou com soma única Abrindo os Produtos do 12 que não tem soma única - (10.2. 5 4), (8.4, 16.2)Escluindo: () Produtos do 21 que não tem soma única - (18.3, 9.6), (16.5, 10.8, 20. 4), (15.6, 18 5, 10.9), (12.9, 18.6)Excluindo: (18.3) , (16.5), (15.6, 18.5), (12.9) Produtos do 23 que não tem soma única - (20.3, 15.4, 12.5, 10.6), (18.5, 16.6, 10.9), (16.7, 14.8), (15.8, 20.6, 12.10), (14.9, 18.7)Excluindo: (20.3), (18.5), (16.7), (15.8), (14.9, 18.7) Produtos do 25 que não tem soma única - (20.5, 10.10), (18.7, 14.9), (16.9, 18.8, 12.12)Excluindo: (20.5), (18.7, 14.9), (16.9) Produtos do 27 que não tem soma única - (20.7, 14.10), (15.12, 18.10, 20.9)Excluindo: (20.7), (15.12, 20.9) Produtos do 29 que não tem soma única - (20.9, 18.10, 15.12)Excluindo: (20.9, 15.12) Ou seja, a soma é 27 e o produto é 20.7, os números são (20, 7) Vamos agora para a terceira afirmaçãoA única razão para Antônio dizer a Carla que ele agora é capaz de descobrir seu produto é porque agora, sua soma só tem um produto com soma única O único par que satisfaz todas as afirmações é o (20, 7) Portanto os númeors escolhidos foram (20, 7) UFAA! Espero que entenda a minha explicação (às vezes nem eu mesmo a entendo) []'sJoão From: marconeborge...@hotmail.com To: obm-l@mat.puc-rio.br Subject: [obm-l] Soma e produto Date: Thu, 19 Jan 2012 00:07:30 + Alguem elege dois numeros,nao necessariamente distintos,no conjunto de numeros naturais 2,...,20.O valor da soma destes numeros é dado somente a Adriano(A) e o valor do produto dos numeros é dado unicamente a Karla(K) Pelo telefone A diz a K:´´nao é possivel que descubras minha soma´´ Uma hora mais tarde,K diz a A:´´Ah! sabendo disso,ja sei quanto vale a sua soma´´! Mais tarde A chama outra vez a K e lhe informa:´´Poxa,agora eu tambem conheço o teu produto´´! Quais numeros foram eleitos?
[obm-l] Re: [obm-l] Re: [obm-l] Binômio de Newton
Vou fazer mais que isto: quantos coeficientes ímpares aparecem em (1+x)^n? Aqui, trataremos apenas de polinômios de coeficientes naturais. Temos (1+x)^2 = 1 +2x+x^2 =1+x^2+2p(x), em que p é um polinômio qualquer. Novamente, (1+x)^4=(1+x^2+2p(x))^2 = (1+x^2)^2+2p(x), em que p é um polinômio qualquer. Assim, (1+x)^4=1+x^4+2p(x). Por uma indução fácil, (1+x)^(2^n)=1+x^(2^n)+2p(x) em que p é um polinômio qualquer. Provamos então o que o Ralph disse. Mas vamos além, como prometi. Se n=2^a+2^b, temos (1+x)^(2^a)*(1+x)^(2^b) = (1+x^A+2M)(1+x^B+2N)=(1+x^A+x^B+x^AB+2P). Por indução, o tanto de coeficientes ímpares será justamente o tanto de 1s na representação binária de n. Em 18 de janeiro de 2012 22:53, Ralph Teixeira ralp...@gmail.com escreveu: Pense no triangulo de Pascal modulo 2, isto eh, soh marcando pares (0) e impares (1): 1 11 101 10001 110011 1010101 ... Etc. Ha varios padroes a serem explorados ali, varias repeticoes de triangulos anteriores, que podem ser demonstradas por inducao, por exemplo. Em particular, voce soh pode ter ...1 na linha n se tiver 1001 na linha n+1. Entao voce pode tentar mostrar que 1...0001 ocorre sse na linha n=2^s. Ajuda? Abraco, Ralph 2012/1/18 marcone augusto araújo borges marconeborge...@hotmail.com: Seja n um inteiro positivo.Demonstrar que todos os coeficientes do desenvolvimento do binomio de Newton (a+b)^n sao impares se,e somente se,n é da forma 2^s - 1. Agradeço a quem puder ajudar -- /**/ 神が祝福 Torres = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] Fwd: [acm-ufrj] Fwd: [obm-l] Re: [obm-l] Fwd: [obm-l] Quantidade mínnima de tentativas
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 lucas.piere...@gmail.com 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: acm-u...@googlegroups.com 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