Problems
Today we will solve some logic problems. This time, we are visiting a strange planet. This planet is inhabited by two kinds of aliens, Cricks and Goops. The physical differences between them are not enough for a human being to distinguish them, but they have another remarkable feature. They can only ask questions. Cricks can only ask questions whose answer is yes, while Goops can only ask questions whose answer is no.
In this sheet, we will look at basic counting problems. The fundamental principle is quite simple. If you have two independent choices to make, then the number of options for making both choices is calculated by multiplying the number of options for each choice.
An issue we frequently run into is that of overcounting. This means we count the same thing more than once. In the examples and problems today, you will see various ideas that we can use to correct for overcounting, or for avoiding it.
From the examples above, we see that we often need to pick \(k\) objects from \(n\) objects where the order of the \(k\) objects is ignored. The number of ways to pick them is notated with the special symbol \(\binom{n}{k}\), pronounced “\(n\) choose \(k\)". What’s a formula for \[\binom{n}{k}\]?
Today we will solve some problems about finding areas of geometric figures. You only need to know how to calculate the area of a rectangle, a triangle and a circle to be able to solve every problem in this set. Here is a brief description of the area formula for each shape.
We start with rectangles because they are easy. In the picture below, one way to find the area of the rectangle is to multiple the length of the side \(AB\) by the length of the side \(AD\).
Next we consider the area of a triangle. In general, the area of a triangle is given by \(\frac{1}{2}bh\), where \(b\) is the length of a chosen base and \(h\) is the height (the length of the altitude corresponding to that base). Finding a base and a corresponding altitude is usually straightforward. However, it can be a bit tricky if the altitude lies outside the triangle. See the picture below for one such case. The segment \(AB\) is the base and \(CD\) is the altitude. If the area formula seems hard to believe in this case, please have a look at problem 6.
At last, we come to the area of a circle. If a circle has radius \(r\), its area is \(\pi r^2\). A fully rigorous proof requires calculus! The number \(\pi\) is approximately 3.14159 to five decimal points.
This week we’re looking at Fibonacci numbers, and other sequences of numbers.
We say that the ‘zeroth’ Fibonacci number is \(0\) and the first Fibonacci number is \(1\). Then, from that point, every Fibonacci number is found by adding the two previous Fibonacci numbers. This means that the sequence begins \(0,1,1,2,3,5,8,13,21,34,55,89,144,...\)
The Fibonacci numbers hide lots of patterns which we’ll explore today, for example snail’s spiral.
Prime numbers are like atoms that build every integer number. That is, a prime decomposition of a number is unique and then we can use it to find the number’s factors. Today we will explore this idea a bit more.
We will introduce a couple of new terms. First, a common divisor of two numbers is simply a number that both of these numbers can be divided by. Two numbers which have no common divisors (except from 1) are called relatively prime. We can establish if two numbers are relatively prime by looking at their prime factorizations - if they share no common primes, then they cannot share a common divisor!
Out of all the common divisors two numbers have, one must be the largest. This is an important number and is called the Greatest Common Divisor (GCD). You can find it by looking at the prime factorizations of the two numbers. For every prime number appearing in both factorizations, we take the smaller power. Then we multiply all our choices together. If we divide both numbers by their GCD, the resulting numbers will have no common divisors left and so will be relatively prime.
Similar to the notion of a common divisor is the one of common multiple. It is simply a number that is divisible by both numbers. Among the common multiples, one must be the smallest – this is called the Least Common Multiple (LCM). Again, the LCM can be found by looking at the prime factorizations of the two numbers. For every prime number appearing in any of the two factorizations, we take the larger power. Then we multiply all our choices together.
[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.