Olimpíadas ⇒ Princípio da Casa dos Pombos Tópico resolvido
Moderador: [ Moderadores TTB ]
-
goncalves3718
- Mensagens: 816
- Registrado em: Qui 26 Dez, 2019 15:26
- Última visita: 11-04-23
Set 2020
21
15:36
Princípio da Casa dos Pombos
Demonstrar pelo Princípio da Casa dos Pombos que qualquer conjunto de [tex3]n[/tex3]
inteiros possui um subconjunto não vazio cuja soma dos elementos é divisível por [tex3]n[/tex3]
.
Set 2020
22
15:26
Re: Princípio da Casa dos Pombos
Considere o conjunto com n elementos: [tex3]\{a_1,a_2,a_3,a_4,...,a_n\} [/tex3]
E as somas:
[tex3]\begin{cases}
s_1=a_1 \\
s_2=a_1+a_2 \\
s_3=a_1+a_2+a_3 \\
s_4=a_1+a_2+a_3+a_4 \\
.... \\
s_n= a_1+a_2+a_3+a_4+a_5+...+a_n
\end{cases}[/tex3]
Se algum [tex3]s_k [/tex3] para [tex3]1 \leq k \leq n [/tex3] é divisível por n, então está feito.
Se nenhum [tex3]s_k [/tex3] é divisível por n, então existem apenas n-1 restos possíveis na divisão por n: 1,2,3,4,...,n-1.
São n-1 restos possíveis, para n somas [tex3]s_k [/tex3] . Ou seja, pelo menos duas somas [tex3]s_k [/tex3] têm o mesmo resto na divisão por n, então basta subtraí-las e formará uma soma divisível por n.
E as somas:
[tex3]\begin{cases}
s_1=a_1 \\
s_2=a_1+a_2 \\
s_3=a_1+a_2+a_3 \\
s_4=a_1+a_2+a_3+a_4 \\
.... \\
s_n= a_1+a_2+a_3+a_4+a_5+...+a_n
\end{cases}[/tex3]
Se algum [tex3]s_k [/tex3] para [tex3]1 \leq k \leq n [/tex3] é divisível por n, então está feito.
Se nenhum [tex3]s_k [/tex3] é divisível por n, então existem apenas n-1 restos possíveis na divisão por n: 1,2,3,4,...,n-1.
São n-1 restos possíveis, para n somas [tex3]s_k [/tex3] . Ou seja, pelo menos duas somas [tex3]s_k [/tex3] têm o mesmo resto na divisão por n, então basta subtraí-las e formará uma soma divisível por n.
Ninguém pode ser perfeito, mas todos podem ser melhores. [\Bob Esponja]
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg
-
- 0 Respostas
- 3429 Exibições
-
Última msg por JotaV
-
- 1 Respostas
- 775 Exibições
-
Última msg por MateusQqMD
-
- 1 Respostas
- 4146 Exibições
-
Última msg por deOliveira
-
- 1 Respostas
- 601 Exibições
-
Última msg por eivitordias
