Problems

Among the first \(20\) Fibonacci numbers: \(F_0 = 0,F_1 = 1,F_2 = 1, F_3 = 2, F_4 = 3,..., F_{20} = 6765\) find all numbers whose digit-sum is equal to their index. For example, \(F_1=1\) fits the description, but \(F_{20} = 6765\) does not, since \(6+7+6+5 \neq 20\).

Among the first \(20\) Fibonacci numbers: \(F_0 = 0,F_1 = 1,F_2 = 1, F_3 = 2, F_4 = 3,..., F_{20} = 6765\) check whether the numbers with prime index are prime. The index is another name for a number’s place in the sequence.

Consider Pascal’s triangle: it starts with \(1\), then each entry in the triangle is the sum of the two numbers above it. Prove that the diagonals of Pascal’s triangle add up to Fibonacci numbers.

Prove for any integers \(m,n\ge0\) that \(F_{m+n} = F_{m-1}F_n + F_mF_{n+1}\).
Corollary: if \(k\mid n\), then \(F_k\mid F_n\). This can be proven by induction if we write \(n=sk\) for a natural \(s\), then \[F_{k+(s-1)k} = F_{k-1}F_{(s-1)k} + F_kF_{(s-1)k+1}.\]

Denote by \(\gcd(m,n)\) the greatest common divisor of numbers \(m,n\), namely the largest possible \(d\) which divides both \(n\) and \(m\). Prove for any \(m,n\) that \[\gcd(F_n,F_m) = F_{\gcd(m,n)}.\]

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.

Let us define XOR (or addition mod 2). XOR is defined for 0 and 1 only. Here is a table recording the values of XOR:

Now we define the important concept of nim-sum. Given two natural numbers \(x\) and \(y\), we first convert them into binary representations and then compute XOR on individual digits. The resulting number, denoted \(x \oplus y\), is the nim-sum of \(x\) and \(y\). Here is an example.

This is simply saying \(22 \oplus 5 = 19\). Note that \(22=(10110)_2\) and \(5=(00101)_2\).

Verify \((x \oplus y) \oplus z = x \oplus (y \oplus z)\), so we can speak of \(x \oplus y \oplus z\) with no ambiguity.