[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Problema sobre existência de subconjunto divisível
Achei uma solucao aqui : http://mathoverflow.net/questions/16721/egz-theorem-erdos-ginzburg-ziv Em 22 de outubro de 2012 09:02, terence thirteen peterdirich...@gmail.com escreveu: Lembrei vagamente deste problema, mas acho que ele é mais complicado do que imaginamos. Lembro que num livro de Ross Honsberger, talvez o Math. Gems III, ele coloca uma demonstração para n sendo potência de 2, usando uma espécie de indução. E afirma que é verdadeiro no caso geral mas sem demonstrar. Vou ver se o pessoal do MathLinks pode dar uma luz... Em 19 de outubro de 2012 22:00, terence thirteen peterdirich...@gmail.com escreveu: Em 19 de outubro de 2012 21:44, Gabriel Dalalio gabrieldala...@gmail.com escreveu: Parece que realmente sempre existe, mas ainda estou em busca de uma prova ou alguém que saiba provar... E também quero obter um algoritmo para achar uma dessas subsequencias... Em 19 de outubro de 2012 16:50, Pedro Nascimento pedromn...@gmail.com escreveu: *subconjuntos com a dada propriedade Em 19 de outubro de 2012 16:48, Pedro Nascimento pedromn...@gmail.com escreveu: Alguem conseguiu algo nesse problema? Parece uma boa conjectura, cheguei a simular so pra ver o comportamento, a quantidade de subconjuntos em um caso aleatorio eh beem grande e cresce rapido com n. Em 15 de outubro de 2012 21:53, Gabriel Dalalio gabrieldala...@gmail.com escreveu: Eu pensei em casa dos pombos mas não consegui muita coisa, arranjar um subconjunto qualquer que a soma seja divisível por n é facil, o problema é ter exatamente n elementos. Em 15 de outubro de 2012 20:24, terence thirteen peterdirich...@gmail.com escreveu: Em 15 de outubro de 2012 18:49, Gabriel Dalalio gabrieldala...@gmail.com escreveu: Eae galera, beleza? Eu estou pensando na seguinte situação: É dado um conjunto de inteiros de 2n elementos. Sempre existe um subconjunto de n elementos tal que sua soma é divisível por n? Talvez um casa-dos-pombos? Pensei em algo neste estilo: para cada n-conjunto do conjunto de 2n elementos, pareie com seu complementar. A ideia seria provar que a soma 0 módulo n tem que surgir obrigatoriamente em algum momento. Vou pensar um tanto mais nisso aí... E será que sempre existem pelo menos dois subconjuntos diferentes com essa propriedade? Eu só consegui achar exemplos com no mínimo dois subconjuntos possíveis, por exemplo, um conjunto formado por n elementos 0 e n elementos 1. Alguém sabe responder essas perguntas? Obrigado, Gabriel Dalalio -- /**/ 神が祝福 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 = -- /**/ 神が祝福 Torres -- /**/ 神が祝福 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 = -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Problema sobre existência de subconjunto divisível
Lembrei vagamente deste problema, mas acho que ele é mais complicado do que imaginamos. Lembro que num livro de Ross Honsberger, talvez o Math. Gems III, ele coloca uma demonstração para n sendo potência de 2, usando uma espécie de indução. E afirma que é verdadeiro no caso geral mas sem demonstrar. Vou ver se o pessoal do MathLinks pode dar uma luz... Em 19 de outubro de 2012 22:00, terence thirteen peterdirich...@gmail.com escreveu: Em 19 de outubro de 2012 21:44, Gabriel Dalalio gabrieldala...@gmail.com escreveu: Parece que realmente sempre existe, mas ainda estou em busca de uma prova ou alguém que saiba provar... E também quero obter um algoritmo para achar uma dessas subsequencias... Em 19 de outubro de 2012 16:50, Pedro Nascimento pedromn...@gmail.com escreveu: *subconjuntos com a dada propriedade Em 19 de outubro de 2012 16:48, Pedro Nascimento pedromn...@gmail.com escreveu: Alguem conseguiu algo nesse problema? Parece uma boa conjectura, cheguei a simular so pra ver o comportamento, a quantidade de subconjuntos em um caso aleatorio eh beem grande e cresce rapido com n. Em 15 de outubro de 2012 21:53, Gabriel Dalalio gabrieldala...@gmail.com escreveu: Eu pensei em casa dos pombos mas não consegui muita coisa, arranjar um subconjunto qualquer que a soma seja divisível por n é facil, o problema é ter exatamente n elementos. Em 15 de outubro de 2012 20:24, terence thirteen peterdirich...@gmail.com escreveu: Em 15 de outubro de 2012 18:49, Gabriel Dalalio gabrieldala...@gmail.com escreveu: Eae galera, beleza? Eu estou pensando na seguinte situação: É dado um conjunto de inteiros de 2n elementos. Sempre existe um subconjunto de n elementos tal que sua soma é divisível por n? Talvez um casa-dos-pombos? Pensei em algo neste estilo: para cada n-conjunto do conjunto de 2n elementos, pareie com seu complementar. A ideia seria provar que a soma 0 módulo n tem que surgir obrigatoriamente em algum momento. Vou pensar um tanto mais nisso aí... E será que sempre existem pelo menos dois subconjuntos diferentes com essa propriedade? Eu só consegui achar exemplos com no mínimo dois subconjuntos possíveis, por exemplo, um conjunto formado por n elementos 0 e n elementos 1. Alguém sabe responder essas perguntas? Obrigado, Gabriel Dalalio -- /**/ 神が祝福 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 = -- /**/ 神が祝福 Torres -- /**/ 神が祝福 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] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Problema sobre existência de subconjunto divisível
Em 19 de outubro de 2012 21:44, Gabriel Dalalio gabrieldala...@gmail.com escreveu: Parece que realmente sempre existe, mas ainda estou em busca de uma prova ou alguém que saiba provar... E também quero obter um algoritmo para achar uma dessas subsequencias... Em 19 de outubro de 2012 16:50, Pedro Nascimento pedromn...@gmail.com escreveu: *subconjuntos com a dada propriedade Em 19 de outubro de 2012 16:48, Pedro Nascimento pedromn...@gmail.com escreveu: Alguem conseguiu algo nesse problema? Parece uma boa conjectura, cheguei a simular so pra ver o comportamento, a quantidade de subconjuntos em um caso aleatorio eh beem grande e cresce rapido com n. Em 15 de outubro de 2012 21:53, Gabriel Dalalio gabrieldala...@gmail.com escreveu: Eu pensei em casa dos pombos mas não consegui muita coisa, arranjar um subconjunto qualquer que a soma seja divisível por n é facil, o problema é ter exatamente n elementos. Em 15 de outubro de 2012 20:24, terence thirteen peterdirich...@gmail.com escreveu: Em 15 de outubro de 2012 18:49, Gabriel Dalalio gabrieldala...@gmail.com escreveu: Eae galera, beleza? Eu estou pensando na seguinte situação: É dado um conjunto de inteiros de 2n elementos. Sempre existe um subconjunto de n elementos tal que sua soma é divisível por n? Talvez um casa-dos-pombos? Pensei em algo neste estilo: para cada n-conjunto do conjunto de 2n elementos, pareie com seu complementar. A ideia seria provar que a soma 0 módulo n tem que surgir obrigatoriamente em algum momento. Vou pensar um tanto mais nisso aí... E será que sempre existem pelo menos dois subconjuntos diferentes com essa propriedade? Eu só consegui achar exemplos com no mínimo dois subconjuntos possíveis, por exemplo, um conjunto formado por n elementos 0 e n elementos 1. Alguém sabe responder essas perguntas? Obrigado, Gabriel Dalalio -- /**/ 神が祝福 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 = -- /**/ 神が祝福 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 =
