The pigeonhole principle is often called “Dirichlet’s box principle". Dirichlet made good use of this tool to show a fundamental result in Diophantine approximation, now commonly known as the Dirichlet Approximation Theorem. You will now prove it yourself!
Suppose \(\alpha\) is any irrational real number and \(N\geq 1\) is any positive integer. Show that there is an integer \(1\leq q\leq N\) and an integer \(p\) such that \[\left| q \alpha - p \right| < \frac{1}{N}.\]
What’s the sum \(\frac{F_2}{F_1}+\frac{F_4}{F_2}+\frac{F_6}{F_3}+...+\frac{F_{18}}{F_9}+\frac{F_{20}}{F_{10}}\)?
We have a sequence where the first term (\(x_1\)) is equal to \(2\), and each term is \(1\) minus the reciprocal of the previous term (which we can write as \(x_{n+1}=1-\frac{1}{x_n}\)).
What’s \(x_{57}\)?
There is a very, very fast way of computing the greatest common divisor of two positive integers. It was in fact known even to the Greeks two thousand years ago. This procedure is called the Euclidean algorithm, named after Euclid, a famous ancient Greek mathematician.
The algorithm works as follows. Take two positive integers \(a,b\). Let’s say \(a\geq b\).
Calculate the remainder of \(a\) when divided by \(b\). Call it \(r_1\).
Calculate the remainder of \(b\) when divided by \(r_1\). Call it \(r_2\).
Calculate the remainder of \(r_1\) when divided by \(r_2\). Call it \(r_3\).
Continue to divide the remainder from two steps prior by the remainder from the last step, until...
The remainder \(r_n\) is divisible by \(r_{n+1}\). The Euclidean algorithm stops now and \(r_{n+1}\) is \(\gcd(a,b)\).
Show that there is indeed some natural number \(n\) such that \(r_n\) is divisible by \(r_{n+1}\), so that the Euclidean algorithm must stop eventually. Furthermore, show that \(r_{n+1}\) is actually \(\gcd(a,b)\) (otherwise it is all in vain!).
Cut a packet of 4 cards. Is any of the cards in the same place as it was before?
We have a packet of 13 cards from Ace to King. Let Ace be the first card, 2 the second card and so on with King being the thirteenth card. How can you interchange 4 and 7 (and leave all other cards where they are) by only switching adjacent pairs of cards?