Problems
Suppose that \(p\) is a prime number. How many numbers are there less than \(p^2\) that are relatively prime to \(p^2\)?
How many cuboids are contained in an \(n\times n\times n\) cube? For example, we’ve got \(n^3\) cuboids of size \(1\times1\times1\), and obviously just \(1\) of size \(n\times n\times n\) (which is the whole cube itself). But we also have to count how many there of size \(1\times1\times2\), \(1\times2\times3\), and several more.
In the \(6\times7\) large rectangle shown below, how many rectangles are there in total formed by grid lines?
Simplify \(F_0-F_1+F_2-F_3+...-F_{2n-1}+F_{2n}\), where \(n\) is a positive integer.
Show that \(\text{Nim}(x,y,z)\) is a losing position if and only if \(x \oplus y \oplus z = 0\). Remember that \(x \oplus y\) denotes the nim-sum of \(x\) and \(y\).
Show that \(\text{Nim}(x_1,\dots,x_k)\) is an losing position if and only if \(x_1 \oplus \dots \oplus x_k = 0\). \(x \oplus y\) denotes the nim-sum of \(x\) and \(y\).
There is a secret gathering of a group of \(n\) aliens in a very dark room. You cannot see anyone in the room, but you hear the following questions.
“Is at least one of us a Goop?"
“Is the number of Goops amongst us an even number?"
“Is the number of Goops amongst us a multiple of 3?"
\(\dots\)
“Is the number of Goops amongst us a multiple of \(n\)?"
What are all the possible values of \(n\) such that this gathering can happen? Note that each of the \(n\) aliens have asked exactly one question.
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 of the Fibonacci numbers \(F_0+F_1+F_2+...+F_n\)?