Soluções Doces do Dias das Bruxas

0 Flares Facebook 0 0 Flares ×

Solução por Lucca Siaudzionis

Primeiramente, vamos definir:

  • s_1 = a_1
  • s_2 = a_1 + a_2
  • s_3 = a_1 + a_2 + a_3
  • ...
  • s_k = a_1 + a_2 + ... + a_k

Se, para algum i, s_i \equiv 0 \ (mod \ c), já achamos nosso subconjunto e o problema acabou! Vamos então supor que não exista nenhum i que satisfaça tal propriedade.

Logo, temos (c-1) possíveis valores para os restos que os s_i's podem deixar na divisão por c (os números de 1 a c-1) e temos n valores para s_i, com n > c-1. Desta forma, pelo princípio das casas de pombo, existem dois números distintos i e j tal que s_i \equiv s_j \ (mod \ c), desta maneira, temos (supondo i < j):

s_j \equiv s_i \ (mod \ c) \Rightarrow s_j - s_i \equiv 0 \ (mod \ c) \Rightarrow a_{i+1} + a_{i+2} + ... + a_j \equiv 0 \ (mod \ c)

Desta forma, achamos nosso subconjunto!

Vamos então ao código:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: