Problems

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?

How many permutations of 13 cards leaves the third card where it started?

[Needs editing]

Previously, we have explored how to tile the plane using rectangles, but a much more fascinating topic is plane tilings with more intricate shapes such as quadrilaterals, pentagons, and even more unconventional shapes like chickens.

In this exercise sheet, 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.

While living on the uninhabited island, Robinson Crusoe missed terribly having a proper floor in his hut. He wanted his floor to not be some simple hard floor, but a proper tile floor he used to have in his house. He missed his house with the tile floor so much, that finally he decided to make one by himself.

He made a huge number of \(1\times2\) tiles, and studied how he could tile a floor in a rectan- gular room if no tile can overlap the other. It was easy for him to tile the floor in a \(6\times8\) room.

He also noticed that if floor in a room of size \(p\times q\) is tiled with his \(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.

This tiling can be cut from one side to another by a grid line without splitting any tiles. Such constructions are impractical, 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. Robinson decided to use irreducible tilings. Help him to figure out how to tile a rectan- gular floor.

Does there exist an irreducible tiling with \(1\times2\) rectangles of a \(6\times 6\) rectangle?

Irreducibly tile a floor with \(1\times2\) tiles in a room that is a \(6\times8\) rectangle.

Prove that every pair of consecutive Fibonacci numbers are coprime. That is, they share no common factors other than 1.

Calculate the following: \(F_1^2-F_0F_2\), \(F_2^2-F_1F_3\), \(F_3^2-F_2F_4\), \(F_4^2-F_3F_5\) and \(F_5^2-F_4F_6\). What do you notice?

Work out \(F_3^2-F_0F_6\), \(F_4^2-F_1F_7\), \(F_5^2-F_2F_8\) and \(F_6^2-F_3F_9\). What pattern do you spot?

Can every whole number be written as the sum of two Fibonacci numbers? If yes, then prove it. If not, then give an example of a number that can’t be. The two Fibonacci numbers don’t have to be different.

What’s \(\sum_{i=0}^nF_i^2=F_0^2+F_1^2+F_2^2+...+F_{n-1}^2+F_n^2\) in terms of just \(F_n\) and \(F_{n+1}\)?