# (Discrete Math) I'm having a really hard time with this problem as I'm new to the subject. Any help is appreciated. [duplicate]

Using the pigeonhole principle, prove that among any n+ 1 integers you can find two integers so that their difference is divisible by n. You will want the “holes” to be the remainder when you divide a value by n.

• you can look at: math.stackexchange.com/questions/958636/… Aug 22, 2020 at 20:07
• Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or be closed. To prevent that, please edit the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. Aug 22, 2020 at 20:20
• So $n+1$ pigeons and $n$ holes. Sounds good. Aug 22, 2020 at 20:21

## 1 Answer

Consider the set $$A$$ with $$3$$ numbers. The possible differences are $$3$$.

If $$A$$ contains all even or all odd, the differences are all even. If it contains 1 even and two odd or if it contains 1 odd and two even 1 difference is even.

A similar claim can be made if $$A$$ contains $$4$$ numbers and the possible differences are $$6$$. The original $$4$$ numbers can give a remainder of $$0,1,2$$ when divided by $$3$$. Differences contain at least $$1$$ case when the remainder is $$0$$, because $$A$$ contains $$6$$ elements.

If $$A$$ has $$n+1$$ numbers, the possible pairs are $$d=\frac{n(n+1)}{2}$$.

The possible differences are $$d$$ as well.

The elements in $$A$$ can have remainders $$0,1,2,\ldots,n-1$$ when divided by $$n$$ and when subtracting there is at least $$1$$ who has remainder $$0$$, that means that is divisible by $$n$$.

Hope this is clear.