Prooving by Pigeonhole principle

Question

I've been given a question to solve:

Given a set of non-negative distinct integers, and a value m, determine if there is a subset of the given set with sum divisible by m.

For this, I used the dynamic programming approach which is not optimized and takes O(m * m * n) where n is the no. of distinct elements.

But, It's optimized time-complexity is O(m^2). Here, is the solution.

But, while going through the explanation, I encountered this written:

If n > m there will always be a subset with sum divisible by m (which is easy to prove with pigeonhole principle). So we need to handle only cases of n <= m.

I did not understand this part and want to know, how will it be proved rather than trying it by taking examples.

Also, why is the equality present with n < m and not with n > m ?

Answer 1

This problem is a variant of subset sum problem and in subset sum problem we have a target sum to achieve, according to which we can size our DP table but in our case we do not have any specific target sum but we want a sum which is divisible by some $m$. In the process we can have arbitrary intermediate sums and we do not have a clear bound to how to size the DP table.

One naive approach would be to have the maximum sum possible in the set divided by $m$, and then we can subtract the mod of that division from this maximum sum. This can be an upper bound to our possible sums in the set, but this can be very large for bigger values.

The solution is divided in two parts ($n$ is the no of elements in set):

1. $n > m$, for $n > m$ we will always have a subset with sum divisible by $m$.

2. $n <= m$

For the first case where $n > m$, let us define the set as $X = {X_1, X_2, ..., X_n}$. Now if any value $X_i$ is divisible by $m$, the claim trivially holds. Now, let us consider partial sets as $P_i = \{first\ i\ values\ of\ set\}$ and modular sum

as $S_i = sum(P_i)%m$. So,

$S_1 = (X_1)%m$

$S_2 = (X_1 + X_2)%m$

$S_n = (X_1 + X_2 + ... + X_n)%m$

If any of these values is 0 then the claim trivially holds as we have achieved a sum which is divisible by $m$. Also, if any of these value repeats i.e. some $S_i = S_j$ where $j > i$, then also this claim holds. (why? we have added a multiple of m to Si to achieve $S_j$ (e.g. 5%3 = 2 and 8%3 = 2, but 8-5 = 3)).

So this says that from $S_1$ to $S_N$ we must have distinct values. The range of mod function is 1 to $m-1$. Since $n > m$, so for $S_1$ to $S_n$ some value should repeat from 1 to $m-1$. This is the pigeonhole principle in application.

For the second case we have the above solution. The mentality of this solution is that we will record all the mod values which can be obtained when partial sums are divided by $m$. If at any stage we capture the mod value to be zero then we are done. Also the bottom up procedure adds one element at each time.

Answer 2

Let the $n$ distinct positive integers are represented by $c_1,\ldots,c_n$. Now form a series of sums as;

\begin{align} S_1 =&\; c_1 \\ S_2 =&\; c_1 + c_2\\ \vdots & \\ S_n =&\; c_1 + \ldots c_n \end{align}

Now, use the pigeonhole principle on the $S_i$'s with $m$ holes and place them into the holes according to their result modulo $m$. We know that at least two $S_i$'s are sharing the same hole since $n>m$. Let call them $S_i$ and $S_j$.

$S_i \equiv S_j \bmod m \implies S_j -S_i \equiv 0 \bmod m \implies m| S_j-S_i$

By using the definition of $S_i$ and $S_j$ we can say that if $i<j$ then $m \;|\; a_{i+1} + \ldots + a_{j}$

if $n <= m$ we cannot prove it and even we can find counterexamples.

Answer 3

Let us prove the following stronger proposition. Notice that we do not require the given integers to be non-negative nor distinct. Also note that we do not require $n$ to be strictly greater than $m$.

Given an array of $n$ integers and a positive integer $m\le n$, there will always be a nonempty subset with sum divisible by m.

Here is a simple proof.

Let $a_i$ be the $i$-th element of the array, $0\le i\le m-1$.

Let $s_i=a_0+a_1+\cdots+a_i$ and (pigeon) $r_i=s_i\%m$, the remainder of $s_i$ divided by $m$. That is, $s_i-r_i$ is a multiple of $m$ and $0\le r_i\lt m$. Note that the number of all possible values of remainders (holes) is $m$. Thera are two cases.

• All $r_i$ are distinct. Since the number of $r_i$ (pigeons) is $m$, all holes must be occupied by a pigeon. That means $0=r_s$ for some $s$. That is, $a_0+\cdots+a_s$ is divisible by $m$.

• All $r_i$ are not distinct. Suppose $r_{i_1}=r_{i_2}$ for some $i_1<i_2$. Then $$(a_{i_1}+a_{i_1+1}+\cdots+a_{i_2-1})\%m=(s_{i_2}-s_{i_1})\%m=s_{i_2}\%m-s_{i_1}\%m=r_{i_2}-r_{i_1}=0$$

Proof is done.

Note that $m$ is best lower bound of $n$ to ensure a nonempty subset with sum divisible by $m$. If we allow $n\lt m$, it is possible that there is no subset with sum divisible by $m$. For example, we can have $m-1$ 1's. For any subset of $k>0$ numbers, its sum is $k$, which is not divisible by $m$. If we require them to be distinct, we can take $1, m+1, 2m+1, \cdots, (m-2)m+1$.

---

Thanks to the above stronger proposition, we need to handle only cases of $n \lt m$ instead cases of $n\le m$ in the original article.

Answer 4

“It’s easy to prove”, so the proof should be short.

Calculate the sum of the first k numbers modulo m, for 0 <= k <= m. There are m+1 sums, and only m possible values, so two sums are equal modulo m. Their difference is divisible by m.