1
$\begingroup$

I understand the pigeonhole principle is needed here and I see the solution in the back of the book, but the explanation is week. If anyone could explain step-by-step that would be awesome!

$\endgroup$

closed as off-topic by Daniel, Harish Chandra Rajpoot, user147263, N. F. Taussig, yoknapatawpha Oct 28 '15 at 13:36

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Daniel, Harish Chandra Rajpoot, yoknapatawpha
If this question can be reworded to fit the rules in the help center, please edit the question.

3
$\begingroup$

Assuming the problem as it is currently written is written incorrectly and that the intended problem is the following:

Given a set of $18$ integers $x_1,x_2,\dots,x_{18}$, there will exist two integers $x_i, x_j$ with $1\leq i<j\leq 18$ such that $x_i-x_j$ is divisible by $17$.

By the quotient remainder theorem, each of the integers $x_i$ can be written in a unique way as $17q_i+r_i$ where $q_i$ and $r_i$ are both integers and $0\leq r_i<17$. We treat the values of $r_i$ as the holes and the elements in our set as the pigeons. There are then $17$ holes and $18$ pigeons.

By the pigeon-hole principle, there must be two terms with the same remainder. Without loss of generality, suppose that it was $x_i$ and $x_j$ where $x_i=17q_i+r$ and $x_j=17q_j+r$. Then $x_i-x_j = 17q_i+r-17q_j-r = 17(q_i-q_j)$ is therefore divisible by $17$.


The way it is currently worded (Show that for every set of 18 integers there will be two that are divisible by 17) is false. We can have a set of $18$ integers such that none of them are divisible by $17$, for example the set $\{1,2,3,4,\dots,16,18,19\}$.

Even if we were to add additional constraints that each of the integers is consecutive, we have the counterexample $\{1,2,3,\dots,18\}$ has exactly one element divisible by $17$, not two.

$\endgroup$

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