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

Question

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

I'm unable to find the correct approach to solve this. I'm sure the Pigeonhole Principle will be useful here, but I don't know how to correctly apply it within the proof. Can someone point me in the right direction?

Answer 1

Let's try to do it, no induction involved.

Suppose you augment your initial list $A = [a_1, a_2, ..., a_m]$ with a new element at the beginning $a_0 = 0$, $A' = [a_0, a_1, ..., a_m]$.

Now build partial sums of $A'$, such that $P_i = \sum_0^i a_j$. Notice that the sums of elements in the initial list from positions $b$ to position $e$ is $\sum_b^e a_i = P_e - P_{b - 1}$. Notice $P_0 = 0$ is defined since we added $a_0$. This is a very common trick when you care about the sums of intervals.

Back to the problem, you need to proof there exist two index $i < j$ such that $c | (P_j - P_i)$. This is equivalent to say that there exist two index $i < j$ such that $P_i \equiv P_j \mod c$. We only care about remainder of each element in $P$ if they are divided by $c$, and moreover we should only show that at least two elements have the same remainder.

Now notice the number of different remainders given $c$ is at most $c$ and the length of the list $P$ is $|P| = m + 1$. Since $c \le m < |P|$ by the Pigeonhole principle you can guarantee at least two elements in $P$ have the same remainder.

Answer 2

Let P(m) denote the statement we are trying to prove: Given a positive-integer array A of size m and a c in [m] there is a (contiguous) subarray whose sum modulo c is 0.

Let us say that such subarrays satisfy P(m).

P(1) is trivial since c = 1.

Assume P(m). Let's try to prove for P(m+1).

If c <= m, then ignore the last element of the array and notice that any subarray that satisfies P(m) also satisfies P(m+1).

Assume c == m+1.

Consider the m+1 sums: S1 = A[1]%(m+1), S2 = (A[1] + A[2])%(m+1),.... S_(m+1) = (A[1] + A[2] + ... + A[m+1])%(m+1)

If one of the S_i == 0, then, sub-array A[1..i] satisfies P(m+1).

If none of the S_i are 0, each S_i can only take on one of the m values in the range {1,2,...,m}. By Pigeonhole Principle, there must be indices i < j such that S_i == S_j and A[i+1 ... j] satisfies P(m+1).