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

2 participantes

Ir para baixo

Princípio da casa dos pombos Empty Princípio da casa dos pombos

Mensagem por Russell99 Sex 28 Ago 2020, 16:39

Prove que de qualquer conjunto de dez inteiros podemos escolher um subconjunto cuja soma é um múltiplo de 10.

Russell99
Iniciante

Mensagens : 35
Data de inscrição : 06/09/2019
Idade : 20
Localização : Breves-Pará-Brasil

Ir para o topo Ir para baixo

Princípio da casa dos pombos Empty Re: Princípio da casa dos pombos

Mensagem por MestreXifu Dom 30 Ago 2020, 19:50

Boa noite amigo! A ideia é olhar mod 10. Seja V o conjunto em questão e W esse subconjunto procurado.
Temos alguns casos que podemos "descartar" rapidamente:
1) Se todos os elementos deixam o mesmo resto por 10, então sua soma será múltipla de 10 e o problema acaba.
2) Notando que x ≡ 0 (mod 10) não pertence a W (pois daí era só pegar ele e o problema acabaria.
3) Se x  a (mod 10), então se existir um y  -a (mod 10) nosso problema também acaba (sua soma será congruente a 0 mod 10)
4) Por fim, ficamos com as seguintes possibilidades de congruência mod 10:
1,2,3,4,5,-4,-3,-2,-1. Precisamos escolher 10 elementos, e veja que pelo princípio da casa dos pombos pelo menos uma dessas congruências aparecerá 3 vezes, já que o 5 não pode aparecer 2 vezes (pois daí escolheríamos esses dois elementos e sua soma seria múltipla de 5). Daí temos que escolher mais 4 elementos dentre {1,2,3,4,-4,-3,-2,-1} e repeti-los até termos 9 elementos no mínimo (talvez não escolhemos o 5) , já que não poderemos escolher o elemento simétrico. Por exemplo, eu poderia escolher {1,-2,-3,4} e repetir o 1 três vezes, o -3 três vezes e o -4 quatro vezes: {1,1,1,-2,-3,-3,-3,-4,-4,5}.
   Acho que a partir desse desenvolvimento você pode olhar caso a caso (famoso exercício pro leitor hahahhah) supondo para cada vez qual elemento será repetido pelo menos 3 vezes, serão poucos casos (4), dada a simetria que chegamos.

Espero ter ajudado Very Happy

MestreXifu
Iniciante

Mensagens : 27
Data de inscrição : 24/07/2020
Idade : 19

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