Soluções Doces do Dias das Bruxas

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: