Princípio da Casa dos Pombos
3 participantes
Página 1 de 1
Princípio da Casa dos Pombos
Prove que todo conjunto de 10 inteiros positivos com 2 digitos cada pode ser dividido em dois subconjuntos disjuntos com a mesma soma
Última edição por Não_Grita em Dom 14 Jul 2019, 17:11, editado 2 vez(es)
Não_Grita- Iniciante
- Mensagens : 2
Data de inscrição : 14/07/2019
Idade : 18
Localização : Imperatriz Maranhão Brasil
Re: Princípio da Casa dos Pombos
O enunciado é esse mesmo? Quero dizer, o conjunto {18,33,22,77} invalida isso, se entendi corretamente
radium226- Recebeu o sabre de luz
- Mensagens : 117
Data de inscrição : 13/01/2019
Idade : 21
Localização : São Bernardo do Campo - SP
Re: Princípio da Casa dos Pombos
10 inteiros, esqueci
Não_Grita- Iniciante
- Mensagens : 2
Data de inscrição : 14/07/2019
Idade : 18
Localização : Imperatriz Maranhão Brasil
Re: Princípio da Casa dos Pombos
Isso parece ser bem complicado, eu vou dar sugestões pra você e pra quem quiser fazer: temos um conjunto com 10 elementos, cada um com valores 10\leq a_j \leq 99 , isso significa que a soma de todos eles tem que ser um valor entre 10+11+12+...+19=145 (perceba que, por se tratar de conjuntos, os elementos tem que ser todos diferentes) e 99+98+97+...+99=945, ou seja, 145\leq S \leq 945 . Acho que esse intervalo da soma é importante porque nos permite tratar o problema como uma distribuição de bolinhas em 10 caixas(elementos) de modo que todas as caixas tenham quantidades diferentes de bolinhas.
radium226- Recebeu o sabre de luz
- Mensagens : 117
Data de inscrição : 13/01/2019
Idade : 21
Localização : São Bernardo do Campo - SP
Re: Princípio da Casa dos Pombos
Olá,
O conjunto tem2^{10} - 1 = 1023 subconjuntos não vazios. Por outro lado, a soma dos elementos do conjunto é, no máximo, 90 + 91 + 92 + ... + 99 = 945. Portanto, pelo princípio da casa dos pombos, pelo menos dois subconjuntos do conjunto em questão, A e B, digamos, têm a mesma soma de elementos. Assim, A \ (AՈB) e B \ (AՈB) são disjuntos e continuam tendo a mesma soma de elementos.
Essa questão caiu em uma prova minha uma vez e eu tinha essa resolução aqui.
O conjunto tem
Essa questão caiu em uma prova minha uma vez e eu tinha essa resolução aqui.
____________________________________________
Links úteis:
Regras do fórum |
Como colocar imagens nas mensagens |
Como inserir códigos LaTex nas mensagens |
“A dedicação é a mãe da boa sorte.”
Mateus Meireles- Matador
- Mensagens : 763
Data de inscrição : 14/07/2018
Idade : 27
Localização : Fortaleza/CE
Re: Princípio da Casa dos Pombos
Passei um pouco longe Excelente solução mateus (:
radium226- Recebeu o sabre de luz
- Mensagens : 117
Data de inscrição : 13/01/2019
Idade : 21
Localização : São Bernardo do Campo - SP
Tópicos semelhantes
» Casa dos pombos
» Casa dos Pombos
» casa dos Pombos
» Princípio da casa dos pombos
» Teoria da Casa dos Pombos
» Casa dos Pombos
» casa dos Pombos
» Princípio da casa dos pombos
» Teoria da Casa dos Pombos
Página 1 de 1
Permissões neste sub-fórum
Não podes responder a tópicos
|
|