PiR2
Gostaria de reagir a esta mensagem? Crie uma conta em poucos cliques ou inicie sessão para continuar.

Princípio da Casa dos Pombos

3 participantes

Ir para baixo

Princípio da Casa dos Pombos Empty Princípio da Casa dos Pombos

Mensagem por Não_Grita Dom 14 Jul 2019, 16:29

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

Ir para o topo Ir para baixo

Princípio da Casa dos Pombos Empty Re: Princípio da Casa dos Pombos

Mensagem por radium226 Dom 14 Jul 2019, 17:07

O enunciado é esse mesmo? Quero dizer, o conjunto {18,33,22,77} invalida isso, se entendi corretamente

radium226
Recebeu o sabre de luz
Recebeu o sabre de luz

Mensagens : 117
Data de inscrição : 13/01/2019
Idade : 21
Localização : São Bernardo do Campo - SP

Ir para o topo Ir para baixo

Princípio da Casa dos Pombos Empty Re: Princípio da Casa dos Pombos

Mensagem por Não_Grita Dom 14 Jul 2019, 17:09

10 inteiros, esqueci

Não_Grita
Iniciante

Mensagens : 2
Data de inscrição : 14/07/2019
Idade : 18
Localização : Imperatriz Maranhão Brasil

Ir para o topo Ir para baixo

Princípio da Casa dos Pombos Empty Re: Princípio da Casa dos Pombos

Mensagem por radium226 Dom 14 Jul 2019, 17:55

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
Recebeu o sabre de luz

Mensagens : 117
Data de inscrição : 13/01/2019
Idade : 21
Localização : São Bernardo do Campo - SP

Ir para o topo Ir para baixo

Princípio da Casa dos Pombos Empty Re: Princípio da Casa dos Pombos

Mensagem por Mateus Meireles Dom 14 Jul 2019, 22:13

Olá,

O conjunto tem 2^{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.

____________________________________________
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
Mateus Meireles
Matador
Matador

Mensagens : 763
Data de inscrição : 14/07/2018
Idade : 27
Localização : Fortaleza/CE

Ir para o topo Ir para baixo

Princípio da Casa dos Pombos Empty Re: Princípio da Casa dos Pombos

Mensagem por radium226 Seg 15 Jul 2019, 09:39

Passei um pouco longe Neutral Excelente solução mateus (:

radium226
Recebeu o sabre de luz
Recebeu o sabre de luz

Mensagens : 117
Data de inscrição : 13/01/2019
Idade : 21
Localização : São Bernardo do Campo - SP

Ir para o topo Ir para baixo

Princípio da Casa dos Pombos Empty Re: Princípio da Casa dos Pombos

Mensagem por Conteúdo patrocinado


Conteúdo patrocinado


Ir para o topo Ir para baixo

Ir para o topo

- Tópicos semelhantes

 
Permissões neste sub-fórum
Não podes responder a tópicos