Let n > 3 be a given integer. Find the largest integer d (in terms of n) such that for any set S of n integers, there are four distinct (but not necessarily disjoint) nonempty subsets, the sum of the elements of each of which is divisible by d.
Problem
Source: SMO 2015 open
Tags: number theory
04.09.2020 05:07
To prove it is impossible for $d\ge n$, take a set so that each of its elements is congruent to $1$ modulo $n.$ To prove it is impossible for $d=n-1,$ take a set so that one of the elements is $0,$ while the rest are congruent to $1$ modulo $n.$. We will show that $d=n-2$ satisfies the given condition. Lemma: Any set of $n$ integers has nonempty subset whose sum is divisible by $n.$ Let $S=\{a_1,...,a_n\}$ be a set of $n$ integers. By the lemma, there is a subset $T_1\subseteq \{a_1,...,a_{n-2}\}$ whose sum is divisible by $d.$ Take $a_i \in T_1.$ Choose subset $T_2\subseteq S\setminus \{a_i,a_{n-1}\}$ whose sum is divisible by $d.$ If $T_1$ and $T_2$ are disjoint, pick $a_i \in T_1, a_j \in T_2.$ By the lemma, there exists a subset $T_3\subseteq S\setminus \{a_i,a_j\}$ whose sum is divisible by $d.$ Clearly, $T_1,T_2, T_1 \cup T_2$ and $T_3$ are four distinct sets satisfying the given condition. Otherwise, there are no two disjoint subsets of $S$ whose sums are both divisible by $d.$ Pick $a_i \in T_1, a_j \in T_2.$ By the lemma, there exists a subset $T_3\subseteq S\setminus \{a_i,a_j\}.$ whose sum is divisible by $d.$ Then we can choose two distinct elements $a_r$ and $a_s$ so that $\{a_r,a_s\} \cap T_i \neq \emptyset$ for $i=1,2,3.$ Use the lemma again for $S\setminus \{a_r,a_s\}$ to find the fourth subset satisfying the condition.