Among n integer one can choose several (possibly one) whose sum is divided by n

This is a classic problem in number theory which can be easily solved by Pigeon Hole principle. Let be the sum of first integers. Thus we have different sums. Suppose none of these sums are divisible by . However any number not divisible by can have remainders between . Since none of these are divisible which mean two of them have the same remainder. Let they be . Therefore