Let $ n$ be an integer, $ n\geq 2$. Find all sets $ A$ with $ n$ integer elements such that the sum of any nonempty subset of $ A$ is not divisible by $ n+1$.
Problem
Source: Romanian TST 1 2008, Problem 1
Tags: modular arithmetic, number theory, relatively prime, combinatorics proposed, combinatorics
Valentin Vornicu
01.05.2008 23:45
Let $ A = \{a_1,\ldots,a_n\}$ be a set. We shall prove that $ a_2 \equiv a_3 \pmod {n + 1}$, and by rearranging the indexes, we will show that all the elements of $ A$ are congruent to some $ p \pmod {n + 1}$, such that $ \gcd(p,n + 1) = 1$. Obviously if that is the case, any subset of $ A$ has at most $ n$ elements, so its sum will be $ kp$, with $ 0 < k < n + 1$, so not divisible by $ n + 1$.
Consider the sums $ s_1 = a_1$, $ s_2 = a_1 + a_2$, $ \ldots$, $ s_n = a_1 + a_2 + \cdots + a_n$. Obviously none of these sums can be equal $ \pmod {n + 1}$ (because if they would taking the difference $ s_i - s_j = a_{j + 1} + \cdots + a_i \equiv 0\pmod{n + 1}$ we get a contradiction. Therefore they cover all the residues $ 1,2,\ldots,n$, modulo $ n + 1$. Consider now $ a_1 + a_3$. This is non zero, so it must be equal to some $ s_i$. But if $ i > 3$, then $ s_i - (a_1 + a_3) = a_2 + a_4 + \cdots + a_i$, which cannot be 0. If $ i = 3$, then $ a_2 \equiv 0\pmod {n + 1}$ contradiction, if $ i = 1$, then $ a_3\equiv 0\pmod {n + 1}$ contradiction, so the only possibility is $ a_1 + a_2 \equiv a_1 + a_3$, so $ a_2 \equiv a_3$. Similarly we obtain that all the elements in the set are congruent modulo $ n + 1$, and we are done.
lajanugen
15.09.2008 13:59
Let A= ( a1,a2,a3,……..,an ) Consider the sums a 1 a 1+a2 a 1+a2+a3 . . . . a1+a2+a3+……+an All these sums must have different non –zero remainders on division by n+1. Because if we assume two sums to have the same remainder on division by n+1 , then their difference, which is also a subset of A, would have to be divisible by n+1. Similarly, considering the sums a 2 a 1+a2 a 1+a2+a3 . . . . a1+a2+a3+……+an it could be proved that a1= a2 (mod n+1) Similarly, it could be proved that all members of A belong to the same residue class modulo n+1. Now let the remainder of these numbers on division by n+1 be r If gcd(n+1,r)=d>1, then there exists a positive integer s<n+1 such that sd=n+1 implying that n+1 divides sr which implies that the sum of any s members is divisible by n+1. Hence, A is such that all of its elements produce the same remainders on division by n+1 and this remainder is relatively prime to n+1. Also , if r were relatively prime to n+1 , then none of the numbers sr ; s<n+1 are divisible by n+1 Sorry about the notations, i couldn't use subscripts
mavropnevma
11.07.2011 17:00
Sorry to revive this old thread, but the problem has made some reappearance(s), and a full clear solution is now found at http://www.artofproblemsolving.com/Forum/viewtopic.php?f=56&t=417536&p=2353838#p2353838. Moreover, the original statement of the problem was using a multiset of $n$ integers (which thus were not necessarily required be distinct), with exactly the same conclusion, since just divisibility (and not equality) is involved.