6. Let $n>2$ be a natural number. Determine the largest integer $d$ for which the following statement holds: From any $n$-element set of integers, one can select three different non-empty subsets such that the sum of the elements in each of them is an integer multiple of $d$. (The selected subsets may have common elements.)

(Jaromír Šimša)
Solution. The given statement does not hold for any $d \geqq n$: it suffices to consider an $n$-element set composed of integers that give a remainder of 1 when divided by $d$. In the case of $d=n$, the only "suitable" subset is the entire $n$-element set; in the case of $d>n$, no such subset exists.

In the second part of the solution, we will show that the statement holds for $d=n-1$. In the following exposition, all considered sets will be non-empty, their elements will be integers, and $s(\mathbf{X})$ will denote the sum of all elements of the set $X$.

First, we prove (a known) statement that if $\mathrm{X}$ has at least $d$ elements, then there exists $\mathrm{Y} \subset \mathrm{X}$ with the property $d \mid s(\mathrm{Y})$. Indeed, if we select $d$ different elements $x_{1}, \ldots, x_{d} \in \mathbf{X}$, then in the case where none of the $d$ sums

$$
x_{1}, x_{1}+x_{2}, \ldots, x_{1}+x_{2}+\ldots+x_{d}
$$

is a multiple of $d$, two of them give the same remainder when divided by $d$; their difference is then a multiple of the number $d$, which is the sum $s(Y)$ for a suitable subset $Y$.

Let's return to the proof of the statement from the problem for $d=n-1$. Let $\mathrm{X}$ be any set with $n$ elements. According to the proven fact, we can find a set $X_{1} \subset X$ such that $n-1 \mid s\left(\mathbf{X}_{1}\right)$. Choose some $x_{1} \in \mathbf{X}_{1}$ and for the $(n-1)$-element set $\mathbf{X}^{\prime}=\mathbf{X} \backslash\left\{x_{1}\right\}$, we use the fact again: there exists a set $\mathbf{X}_{2} \subset \mathbf{X}^{\prime}$ such that $n-1 \mid s\left(\mathbf{X}_{2}\right)$. Since $x_{1} \in \mathrm{X}_{1}$ and $x_{1} \notin \mathrm{X}_{2}$, we have already selected two different subsets of the set $\mathrm{X}$ with the required property. The third subset $\mathrm{X}_{3} \subset \mathrm{X}$ satisfying $n-1 \mid s\left(\mathrm{X}_{3}\right)$ we now find as follows: in the case $X_{1} \cap X_{2}=\emptyset$, we choose $X_{3}=X_{1} \cup X_{2}$; in the opposite case, where $X_{1} \cap X_{2} \neq \emptyset$, we choose $x_{2} \in \mathrm{X}_{1} \cap \mathrm{X}_{2}$ and apply the same fact again - this time to the $(n-1)$-element set $\mathbf{X}^{\prime \prime}=\mathbf{X} \backslash\left\{x_{2}\right\}$ - and find the desired $\mathbf{X}_{3} \subset \mathbf{X}^{\prime \prime}$.

Answer. The largest $d$ is equal to $n-1$.

Note. For the value $d=n-1$, it can happen that the required property will be satisfied by exactly three (different) subsets of the $n$-element set $X$. This occurs when the numbers in the $n$-element set $\mathrm{X}$ give remainders of $1,1,1, \ldots, 1,0$ when divided by $n-1$. One suitable set will have one element, another will have $n-1$ elements, and the third will have (all) $n$ elements.

[^0]:    1 We could, of course, have written $n=p q r \geqq 17 \cdot 19 \cdot 55=17765$ directly. The given calculation only demonstrates how to derive the necessary estimate $n \geqq 10000$ without the tedious multiplication.

[^1]:    2 Thanks to the triangle inequality $a+b>c$ for any triangle satisfying $c=2 b$, we have $a>b$, so all such triangles satisfy the assumed inequality $|A C| \leqq|B C|$.