A set $S$ of $n-1$ natural numbers is given ($n\ge 3$). There exist at least at least two elements in this set whose difference is not divisible by $n$. Prove that it is possible to choose a non-empty subset of $S$ so that the sum of its elements is divisible by $n$.
Problem
Source: Baltic Way 2004, problem 9
Tags: pigeonhole principle, number theory unsolved, number theory
Peter Scholze
20.11.2004 21:21
here's a generalization: lemma: let $T$ be a set of $k$ natural numbers. if there is no way to choose a non-empty subset of $T$ such that the sum of elements is divisible by $n$, then there are at least $k$ different sums of elements of non-empty subsets of $T$ modulo $n$ and it are $k$ iff all elements of $T$ are equal modulo $n$. proof: reduce everything modulo $n$. we don't get a zero by the condition; let the elements be $a_1,...,a_k$. if $a_1+...+a_i=a_1+...+a_j$ for some $i\neq j$, we would have a zero sum. thus, all the sums $a_1+...+a_i$ are different giving $k$ different values. now assume it are only $k$. if $a_2\neq a_1$ we have $a_2=a_1+...+a_i$ for some $i\geq 2$ giving a zero sum, contradiction; thus $a_2=a_1$. by reordering the numbers, we get all numbers to be equal. now, let $T=S$ where $k=n-1$. the lemma implies that there are at least $n$ different sums of non-empty subsets of $S$; by the pigeonhole principle, we get a zero sum.
me@home
04.10.2008 06:14
Assume there is a set of naturals so that the special subset doesn't exist.
Let $ a_1,...,a_{n-1}$ be the given naturals reduced mod $ n$, with $ a_3\not=a_2$ (guaranteed to exist by the statement). Then each is distinct and nonzero (otherwise the subset would be that element). Thus $ \{0,a_1,a_1+a_2,\cdots,a_1+\cdots+a_{n-1}\}=\{0,1,2,\cdots,n-1\}$.
Let $ f(\textbf{a}): =\{0,a_1,a_1+a_2,...,a_1+\cdots+a_{n-1}\}$
Consider the sets $ A: =f(a_1,a_2,a_3,\cdots,a_n)$ and $ B: =f(a_1,a_3,a_2,a_4,\cdots,a_n)$. Among each, no two elements are equal, because then their difference is the sum of a subset and therefore nonzero.
Thus $ A=B=\{0,1,2,\cdots,n-1\}$, and every element of $ A$ besides the second is virtually identical to the corresponding element in $ B$; thus the second must also be equal, so $ a_1+a_2=a_1+a_3$.
This contradicts our assumption.
Takeya.O
19.08.2016 06:44
Let $S=\{a_1,\dots a_{n-1}\}$.We consider following $n$ numbers. $a_1$ $a_2$ $a_1+a_2$ $a_1+a_2+a_3$ $\dots$ $a_1+\dots +a_{n-1}$ If there is $\equiv 0 \mod{n}$, we can prove.If not, by PHP, there are two numbers which are congruent to each other in $\mod{n}$.These are not $(a_1,a_2)$.Consider the difference between two numbers,then we can prove.$\blacksquare$