Integer $n>2$ is given. Find the biggest integer $d$, for which holds, that from any set $S$ consisting of $n$ integers, we can find three different (but not necesarilly disjoint) nonempty subsets, such that sum of elements of each of them is divisible by $d$.
Problem
Source: Czech and Slovak Olympiad 2015, National Round, Problem 6
Tags: Divisibility, number theory, combinatorics, pigeonhole principle
01.04.2015 19:01
The model $S=\{n+1,2n+1,\ldots,n^2+1\}$ shows that we must have $d<n$, since the only non-empty subset having its sum of elements divisible by $n$ is $S$ itself. I claim $d=n-1$, and will use two quite well-known results. Lemma 1. Given a set of (at least) $N$ (distinct) integers, there exists a non-empty subset having its sum of elements divisible by $N$. This is an old Erdös result. Lemma 2. The only sets of $N-1$ (distinct) integers, with no non-empty subset having its sum of elements divisible by $N$, are those where all integers are congruent to a same residue modulo $N$, coprime with $N$. This has appeared a number of times on AoPS, and the proof is quite elementary. By Lemma 1, there exists a subset $\emptyset \neq A \subseteq S$ having its sum of elements divisible by $n-1$. Take an arbitrary $a\in A$. Again by Lemma 1, there exists a subset $\emptyset \neq B \subseteq S\setminus \{a\}$ having its sum of elements divisible by $n-1$, and clearly $B\neq A$. Take an arbitrary $b\in B$, thus $b\neq a$. If there exists a subset $\emptyset \neq C \subseteq S\setminus \{a,b\}$ having its sum of elements divisible by $n-1$, we are done; otherwise, by Lemma 2, there exists some $r$ coprime with $n-1$ such that $x\equiv r\pmod{n-1}$ for all $x\in S\setminus \{a,b\}$. If $a\equiv 0\pmod{n-1}$ or $b\equiv 0 \pmod{n-1}$ we can easily fulfill the requirements, so assume otherwise. This remark also solves the case $n=3$, so we may assume $n>3$. The subset $B$ is therefore made of $b$ and some number of elements from $S\setminus \{a,b\}$. As these are interchangeable, if not all of them are used, then we can easily find another subset $B'$ (different from $B$ and $A$) having its sum of elements divisible by $n-1$. We are left with the case $B = S\setminus \{a\}$, which forces $b\equiv r\pmod{n-1}$. The subset $A$ is therefore made of $a$ and some number of the other $n-1$ elements, congruent with $r$ modulo $n-1$. As these are interchangeable, and not all of them could have been used, then we can easily find other subsets $A'$ and $A''$ (different from $A$) having their sum of elements divisible by $n-1$. In fact, I remember a thread on AoPS pointing to a much stronger result than that of this problem.