This is a question of an assignment I am trying to solve but unable to think how to use pigeonhole principle.
Question is Let $S=\{1, 2, \ldots,n\}$ and let $r$ be an integer not belonging to $S$. Let $T=S \cup \{r\}$. Show that there exists an $x \in S$ such that sum of all elements $T\setminus\{x\}$ is divisible by $n$.
Can someone please tell how to solve this problem.
On
You go through element in $S$, removing it, calculating the sum and checking if it is divisible by $n$. You are guaranteed to find one because of the following reason -
First consider the sum $s_1$ of all the elements in $T \setminus \{1\}$. If we are lucky, $s_1 \equiv 0 \pmod n$. If not let $s_1 \equiv r \pmod n$ for some $1\leq r<n$.
Then consider $s_2$ which is the sum of all elements in $T \setminus \{2\}$.Make an observation that $s_2 \equiv r+1 \pmod n$, since $s_2-s_1=1$.
So at each stage the difference in sums is $1$. So, after the first pick, we will certainly find such a sum since there $n-1$ numbers we can exhaust and we will definitely find a suitable number to remove in $n-r$ steps where $r \geq 1$.
Non-pigeonhole solution: The sum of the elements in $S$ is $n(n+1)/2+r.$ If $n$ is odd, just remove $r$ so that the sum is $n \cdot \frac{n+1}{2},$ which is divisible by $n.$
If $n=2m$ is even, then we require $0 \equiv m(2m+1) + r - x = m+r - x \mod 2m,$ so just choose $x=m+r \mod 2m,$ or $x=2m$ if $m+r\equiv 0 \mod 2m.$
Edit: Check rtybase's comment.