Ensino Médio ⇒ (FB) Princípio de Dirichlet Tópico resolvido

[Deleted User 23699]

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.

[Deleted User 25040]

[tex3]S_k = a_1 + a_2 + ... + a_k[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]S_i-S_j=a_{j+1}+...+a_i\equiv(\mod n)[/tex3]

satisfaz o enunciado.