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:

https://gist.github.com/luccasiau/7ed888e0339d3ecff20e