China Mathematical Olympiad

$$N=\max \{m,m+n-\frac{1}{2}m[(m,n)+1]\}.$$

First we show that $N\ge \max \{m,m+n-\frac{1}{2}m[(m,n)+1]\}$. Let $d=(m,n)$, and write $m=d{m}_1$, $n=d{n}_1$. If $n>\frac{1}{2}m(d+1)$, there exists a complete residue system modulo $m$, $x_1,x_2,\dots ,x_m$, such that their residues modulo $n$ consist exactly of $m_1$ groups of $1,2,\dots ,d$. For example, the following $m$ numbers have the required property: $$i+d{n}_{1}j,i=1,2,\dots ,d,j=1,2,\dots ,m_1.$$ Finding another $k=n-\frac{1}{2}m(d+1)-1$ numbers $y_1,y_2,\dots ,y_k$ that are congruent to $1$ modulo $n$, the set $$A=\{x_1,x_2,\dots ,x_m,y_1,\dots ,y_k\}$$ contains a complete residue system modulo $m$, however none of its nonempty subsets has its sum of elements divisible by $n$. In fact, the sum of the (smallest nonnegative) residue modulo $n$ of all elements of $A$ is greater than zero and less than or equal to $m_1(1+2+\cdots +d)+k=n-1$. Thus $$N\ge m+n-\frac{1}{2}m(d+1),$$ i.e. $$N\ge \max \{m,m+n-\frac{1}{2}m[(m,n)+1]\}.$$

Next we show that $N=\max \{m,m+n-\frac{1}{2}m[(m,n)+1]\}$ has the required property. The following key fact is frequently used in the proof: among any $k$ integers, one can find a (nonempty) subset whose sum is divisible by $k$. Let $a_1,a_2,\dots ,a_k$ be integers, $S_i=a_1+a_2+\cdots +a_i$. If some $S_i$ is divisible by $k$, then the result is true. Otherwise there exist $1\le i<j\le k$, such that $S_i\equiv S_j(\mathrm{mod}k)$, then $S_j-S_i=a_{i+1}+\cdots +a_j$ is divisible by $k$, the result is again true. The following fact is an easy corollary of the previous result: among any $k$ integers, each of which is a multiple of $a$, one can find a (nonempty) subset whose sum is divisible by $ka$.

Returning to the problem, we shall discuss two cases.

Case 1: $n\le \frac{1}{2}m(d+1)$, and $N=m$. We call a finite set of integers a $k$-set if the sum of all its elements is divisible by $k$. Let $x_1,x_2,\dots ,x_m$ be a complete residue system modulo $m$. Clearly we can divide these numbers into $m_1$ groups, each group consisting of a complete residue system modulo $d$. Let $y_1,y_2,\dots ,y_d$ be a complete residue system modulo $d$, and $y_i\equiv i(\mathrm{mod}d)$. If $d$ is odd, we can divide each group into $\frac{d+1}{2}$ $d$-sets, for example: $\{y_1,y_{d-1}\},\dots ,\{y_{\frac{d-1}{2}},y_{\frac{d+1}{2}}\},\{y_d\}$. We get $\frac{1}{2}{m}_1(d+1)$ $d$-sets. Since $n_1\le \frac{1}{2}{m}_1(d+1)$, we can choose some of these $d$-sets such that the sum of their elements is divisible by $n_{1}d(=n)$. If $d$ is even, similarly, a complete residue system modulo $d$ can be divided into $\frac{d}{2}$ $d$-sets, with $y_{\frac{d}{2}}$ remaining. Two remaining numbers can form another $d$-set. In the end we divide $x_1,x_2,\dots ,x_m$ into $\frac{1}{2}{m}_{1}d+\left[\frac{m_1}{2}\right]$ $d$-sets (possibly with a number left if $m_1$ is odd). Since $n_1\le \frac{1}{2}{m}_1(d+1)=\frac{1}{2}{m}_{1}d+\frac{m_1}{2}$, we have $n_1\le \frac{1}{2}{m}_{1}d+\left[\frac{m_1}{2}\right]$, again we can find some of these $d$-sets such that the sum of all their elements is divisible by $n_{1}d=n$.

Case 2: $n>\frac{1}{2}m(d+1)$, $N=m+n-\frac{1}{2}m(d+1)$. Let $A$ be an $N$-element set, containing a complete residue system modulo $m$, $x_1,x_2,\dots ,x_m$, with some other $n-\frac{1}{2}m(d+1)$ numbers. If $d$ is odd, as shown in case 1, we may divide $x_1,x_2,\dots ,x_m$ into $\frac{1}{2}{m}_1(d+1)$ $d$-sets. Divide the remaining $n-\frac{1}{2}m(d+1)$ numbers arbitrarily into $n_1-\frac{1}{2}{m}_1(d+1)$ groups, each with $d$ numbers. Among each group of $d$ numbers one may find a $d$-set, therefore we have another $n_1-\frac{1}{2}{m}_1(d+1)$ $d$-sets, and totally $n_1$ $d$-sets. If $d$ is even, as discussed in case 1, we may divide $x_1,x_2,\dots ,x_m$ into $\frac{1}{2}{m}_{1}d+\lfloor \frac{m_1}{2}\rfloor$ $d$-sets. If $m_1$ is odd, we are left with a number $x_i$ with $d\mid x_i-\frac{d}{2}$. Dividing the other $n-\frac{1}{2}m(d+1)$ numbers arbitrarily into $2n_1-m_1(d+1)$ groups, each with $\frac{d}{2}$ numbers. From each group we can find a $\frac{d}{2}$-set; from any two $\frac{d}{2}$-sets, we can find a $d$-set. If $m_1$ even, then we can find another $n_1-\frac{1}{2}{m}_1(d+1)$ $d$-sets, and totally $n_1$ $d$-sets. If $m_1$ is odd, $\{x_i\}$ is a $\frac{d}{2}$-set, we have $2n_1-m_1(d+1)+1$ $\frac{d}{2}$-sets, and also $n_1-\frac{1}{2}{m}_1(d+1)+\frac{1}{2}$ $d$-sets. Again we can find $n_1$ $d$-sets. Finally we can choose some of these $n_1$ $d$-sets, such that the sum of all their elements is divisible by $n_{1}d(=n)$.