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?

  • $\begingroup$ I usually see this problem solved using the pigeonhole principle, I also do not see how induction would work. $\endgroup$ Jun 12 '20 at 21:25
  • $\begingroup$ This is the same as the "donation problem" that was posted several times yesterday, isn't it? math.stackexchange.com/questions/3713283/… $\endgroup$ Jun 13 '20 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...

  • $\begingroup$ 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 $\endgroup$
    – user799269
    Jun 12 '20 at 23:34
  • $\begingroup$ @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. $\endgroup$ Jun 12 '20 at 23:48
  • $\begingroup$ I have updated my question, can you please check my work? $\endgroup$
    – user799269
    Jun 13 '20 at 0:26
  • $\begingroup$ @Maddow That's it! $\endgroup$ Jun 13 '20 at 0:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy