0
$\begingroup$

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$.
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

While the pigeonhle principle can be used here, the proof you give is not very clear.

Try using as the holes the set of integers mod $n$. Then for each of the $n+1$ given integers $m_k$ create a "pigeon" by mapping $m_k \mapsto (m_k \mod n)$.

Any two $m_k$ with the same values mod $n$ will have a difference divisible by $n$.

Now if no difference is divisible by $n$ you have fit $n+1$ pigeons into $n$ holes, which is a contradiction.

$\endgroup$
4
  • $\begingroup$ So basically you used proof by contradiction using pigeonhole principle to show how it can be true because of the final case where no difference can be divisble by n means u can fit n+1 pigeons into n holes which contradicts the pigeonhole principle correct? $\endgroup$
    – geforce
    Oct 9, 2014 at 16:57
  • $\begingroup$ Yes. Some real purist mathematicians dislike proof by contradiction, but when you use the pigeonhole principle it almost always comes down to a proof by contradiction -- "... and there were not enough holes to have done such-and-thus". $\endgroup$
    – Mark Fischler
    Oct 9, 2014 at 16:58
  • $\begingroup$ Ok thanks very much Mark that makes sense. $\endgroup$
    – geforce
    Oct 9, 2014 at 17:00
  • $\begingroup$ @MarkFischler what do 'purist' mathematicians find wrong with proof by contradiction? Is it because it's a little brute force? $\endgroup$
    – Sherlock Holmes
    Oct 11, 2014 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.