Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.
2 Added explicit counterexamples when n<m.
source | link

Let us prove a slightly stronger statementthe 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 value m. Ifpositive integer $n \ge m$$m\le n$, there will always be a nonempty subset with sum divisible by m.

Suppose $n\ge 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 $0\le r_i\le m-1$, i.e., 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.

Let us prove a slightly stronger statement. 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 value m. If $n \ge m$ there will always be a subset with sum divisible by m.

Suppose $n\ge m$. 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$ . Note that $0\le r_i\le m-1$, i.e., 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.


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.

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.

1
source | link

Let us prove a slightly stronger statement. 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 value m. If $n \ge m$ there will always be a subset with sum divisible by m.

Suppose $n\ge m$. 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$ . Note that $0\le r_i\le m-1$, i.e., 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.


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.