Problems

Today we will be looking at tilings. We define a plane tiling as a covering of the entire plane, without any gaps or overlaps, using identical geometric shapes that can be rotated and symmetrical to each other. Usually, it is sufficient to cover a small portion of the plane with a particular pattern that can be extended to cover the entire plane.

We will also look at some tilings of finite shapes, normally rectangles. You can imagine this as tiling a floor. With a huge number of \(1\times2\) tiles, we can investigate how to tile a floor in a rectangular room if no tile can overlap the other. It’s easy to tile the floor in a \(6\times8\) room.

We can notice that if the floor in a room of size \(p\times q\) is tiled with \(1\times2\) tiles, then \(pq\) is even (can you explain why?). The reverse is also true; i.e. if \(pq\) is even, then the floor can be tiled with \(1\times2\) tiles in a similar way to the picture above.

However, this tiling can be cut from one side to another by a grid line without splitting any tiles. Such constructions are impractical, and this type of floor can easily become uneven. That’s why in practise irreducible tilings are used.

A tiling of a rectangle by small identical rectangles (tiles) is called irreducible if any straight cut from one side of the big rectangle to another goes across at least one of the tiles.

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 \(m,n\) 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.