Prove that among any given $n + 1$ positive integers, there are always two whose difference is divisible by $n$
My Answer:
Using Pigeonhole principle:
From a set of at least $2$ different $n+1$ positive integers the difference between $n+1$ integers will always have a case where it is divisible by $n$. Because if there is $n+1$ integers which can be pigeons in this case then there must be at least $n$ holes where $n+1$ integers can divide by $n$. Although this does not mean all $n+1$ integers can be divisible by $n$ but there are cases where they can be.
Examples:
- $(16 - 13) / 2$ is not divisible by $n$ for $n+1$ integers, where $n = 2$.
- $(15 - 13) / 2 = 1$ is divisible by $n$, where $n = 2$.
- $(13-12) + (16-14) / 4$ is not divisible by $n$, where $n = 4$.