I am stuck with the solution to the following problem (it is also known as the Rational Approximation Theorem) at the Art of Problem Solving wiki, which states:
Show that for any irrational $x \in \mathbb{R}$ and positive integer $n$, there exists a rational number $\frac{p}{q}$ with $1 \leq q \leq n$ such that $|x - \frac{p}{q}| < \frac{1}{nq}$.
They give the following solution with Pigeonhole Principle:
Multiplying both sides by $q$, we have
$|xq-p| < \frac{1}{n}$.
Now, we wish to find a $q$ between $1$ and $n$ such that $xq$ is within $\frac{1}{n}$ of some integer. Let $\{a\}$ denote the fractional part of $a$. Now, we sort the pigeons $\{x\},\{2x\}, ... , \{nx\}$ into the holes $(0, 1/n), (1/n, 2/n), ... , ((n - 1)/n, 1).$ If any pigeon falls into the first hole, we are done. Therefore assume otherwise; then some two pigeons $\{ix\}, \{jx\} \in (k/n, (k+1)/n)$ for $1 \leq k < n$. Assume, without loss of generality, that $j-i > 0$. Then we have that $\{(j-i)x\}$ must fall into the first or last hole, contradiction.
I got everything except the last line of the proof: Then we have that $\{(j-i)x\}$ must fall into the first or last hole, contradiction. How does it follow? And isn't the proof incomplete if $\{(j-i)x\}$ falls into the last hole?
Note that since $\{ ix \}$, $\{ jx \}\in (k/n, (k+1)/n)$ then their difference is at most $(k+1)/n - k/n = 1/n$. Hence the fractional parts of $\{ ix \}$ and $\{ jx \}$ differ by at most $1/n$. So subtracting $ix$ from $jx$ we obtain a number that is within $1/n$ of an integer, hence $\{ (j-i)x \}$ is in the first or last hole.
If it is in the first hole then you can see how the problem is solved. If it is in the last hole then (setting $j-i = q$) we have $qx = p - y$ for some integer $p$ and $0< y < 1/n$. So $qx - p = -y$ and taking absolute values $ |qx - p| < |-y| = y < 1/n$.