# Given an array $A$ and an index $i$, prove there always exists a subarray whose sum $\pmod {i} = 0$.

Given is an array $$A$$ of positive integers with size $$n$$ and an array index $$i$$ (indexing starts at $$1$$). Prove using mathematical induction over $$n$$ that there always exists a contiguous subarray $$S$$ in $$A$$ such that the (sum of the elements of $$S$$) $$\pmod {i} = 0.$$

I get stuck halfway through the inductive step. Here is my work:

Let $$p(n)$$ denote the statement we're proving.

Base case: For $$n = 1$$ the statement holds (every positive integer mod $$1 = 0$$), so the subarray $$S$$ is the array $$A$$ itself.

Induction assumption: Suppose $$p(n)$$ is true.

Inductive step: For an array of size $$n+1$$ we consider the following two cases:

Case (1): $$i \in \{1, 2, ..., n\}$$. It follows directly from the inductive assumption that $$p(n+1)$$ is true (since $$i \neq n+1$$).

Case (2): $$i = n+1$$ (...).

This is where I get stuck, how would you argue that $$S$$ exists here?

• I usually see this problem solved using the pigeonhole principle, I also do not see how induction would work. Jun 12, 2020 at 21:25
• This is the same as the "donation problem" that was posted several times yesterday, isn't it? math.stackexchange.com/questions/3713283/… Jun 13, 2020 at 1:55

All you have left is case $$(2)$$. This case cannot (as far as I can tell) be solved inductively, but it can be solved with the pigeonhole principle. I will give you a hint as to how this can be done.

The sum of a contiguous sub-array can be written as the difference of two prefix sums, e.g, $$a_3+a_4+a_5=(a_1+a_2+a_3+a_4+a_5)-(a_1+a_2)$$ Furthermore, the contiguous sum is equivalent $$\pmod {n+1}$$ to zero if and only if the two prefix sums are equivalent to each other $$\pmod {n+1}$$. So you just need to show there exist two equal prefix sums. The pigeonhole principle naturally applies to showing there exist two equal things...

• For this to work, wouldn't I need more prefix sums than there is? As far as I understand, an array of size $n$ has $n$ prefix sums. In order to use the pigeonhole principle, we'd need more prefix sums "than we can fit". How do I get this last sum? Sorry if I'm totally misunderstanding this
– user799269
Jun 12, 2020 at 23:34
• @Maddow You are right, that is a problem you must overcome! You will see what happens if you look at a small example; find a list of length $4$ whose prefix sums are all different modulo $4$, see why this still has a consecutive sum which is $0$ modulo $4$, then generalize. Jun 12, 2020 at 23:48
• I have updated my question, can you please check my work?
– user799269
Jun 13, 2020 at 0:26
• @Maddow That's it! Jun 13, 2020 at 0:47