Ensino Médio ⇒ (FB) Princípio de Dirichlet Tópico resolvido
Moderador: [ Moderadores TTB ]
-
- Última visita: 31-12-69
Out 2021
16
17:44
(FB) Princípio de Dirichlet
Sejam a1, a2, a3... an uma sequência de inteiros não necessariamente distintos. Prove que existe um subconjunto desses números cuja soma é divisível por n.
-
- Última visita: 31-12-69
Out 2021
16
18:06
Re: (FB) Princípio de Dirichlet
[tex3]S_k = a_1 + a_2 + ... + a_k[/tex3]
se alguma dessa somas for 0 mod n estamos feitos então suponha que nenhuma é divisível por n.
vamos ter n números (S_1, S_2, ..., S_n) e n-1 restos (todos menos o 0) possíveis portanto vamos ter
[tex3]S_i\equiv S_j(\mod n)[/tex3] com i diferente de j, suponha sem perda de generalidade i > j então a soma
[tex3]S_i-S_j=a_{j+1}+...+a_i\equiv(\mod n)[/tex3] satisfaz o enunciado.
se alguma dessa somas for 0 mod n estamos feitos então suponha que nenhuma é divisível por n.
vamos ter n números (S_1, S_2, ..., S_n) e n-1 restos (todos menos o 0) possíveis portanto vamos ter
[tex3]S_i\equiv S_j(\mod n)[/tex3] com i diferente de j, suponha sem perda de generalidade i > j então a soma
[tex3]S_i-S_j=a_{j+1}+...+a_i\equiv(\mod n)[/tex3] satisfaz o enunciado.
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg