Problems

DRAFT
We need to ensure that there isn’t overlap with the first areas problem sheet.
We can introduce the areas of a new shape, e.g. a trapezium more formally. Maybe an ellipse?

We’ll look at ways of making big numbers today. Hopefully you know about powers of numbers. Most of the biggest numbers you’ve seen probably involve powers. Powers are typically thought of as ’repeated multiplication’. You could think of this as being similar to how multiplication is ’repeated multiplication’.

We might use powers when decimal representation is far too long to be useful for understanding the size of an object.

But what if powers aren’t helpful enough? Mathematician and computer scientist Donald Knuth introduced Knuth’s up-arrow notation. A single up-arrow means ‘raise to the power of’. So \(2\uparrow5=2^5=2\times2\times2\times2\times2=32\). Recall that the \(5\) means we have five \(2\)s. Two arrows means ‘tetration’. For example \(2\uparrow\uparrow4=2\uparrow(2\uparrow(2\uparrow2))=2^{(2^{(2^2)})}=2^{(2^4)}=2^{16}=65536\). The \(4\) means that we have four \(2\)s. Three arrows means pentation. So \(2\uparrow\uparrow\uparrow3=2\uparrow\uparrow(2\uparrow\uparrow2)\). Here the \(3\) means that there are three \(2\)s. Remember that \(2\uparrow\uparrow2=2\uparrow2=2^2=4\). So \(2\uparrow\uparrow\uparrow3=2\uparrow\uparrow4=65536\).

A million is \(10^6\) and a billion is \(10^9\). A million seconds is about eleven and a half days. A billion seconds is about 31 years. Other famous big numbers are googol, Skewes’ number, Graham’s number, busy beaver and TREE(3). Another classic big number is the number of atoms in the observable universe - about \(10^{80}\). This is less than \(4\uparrow\uparrow3\), \(3\uparrow\uparrow\uparrow3\), or \(2\uparrow\uparrow\uparrow\uparrow3\).

A couple of these problems are Fermi problems, named after physicist Enrico Fermi. This is where you try to estimate a quantity in the real world. We’re not expecting an exact answer (indeed, we don’t know the exact answer), but using some intelligent estimation, you can get a good idea of the answer.

We bet that some of you play chess and are pretty good. Someone may be better than all of the tutors. Unfortunately for that person, and fortunately for the rest of you, that won’t help too much with the problems today. You’ll need to know how the pieces move and that’s it.

There are various themes of knight’s tours, independence and queens’ domination. We also won’t just look at typical \(8\times8\) chessboards, but grids of different sizes, and even ones that aren’t flat.

The evil warlock found a mathematics exercise book and replaced all the decimal numbers with the letters of the alphabet. The elves in his kingdom only know that different letters correspond to different digits \(\{0,1,2,3,4,5,6,7,8,9\}\) and the same letters correspond to the same digits. Help the elves to restore the exercise book to study.

Today we will solve some problems involving counting the same quantity twice (or more times) in different ways, which will let us learn about the components making it up.

Today we will explore some mathematical games involving two players who take turns to move. In many games, one of the players has a winning strategy, which guarantees victory regardless of the opponent’s moves.

Let’s say you are at a stage of the game where you can win in one move and it is also your turn. Then that position is called a winning position. We can now make the following definition for all states of the game.

A losing position is one where all your moves give the other player a winning position. A winning position is one where you can make a move that gives your opponent a losing position.

We can analyse from the end of the game backwards and figure out whether each possible state is a winning position or a losing position. The first player has a winning strategy if the starting position is a winning position. The winning strategy belongs to the second player if the starting position is a losing position.

Mathematical Induction is a method to prove statements that are usually true for all natural numbers. The method consists of two steps.

• The first step, known as the base case, is to prove the given statement for the first natural number.

• The second step, known as the inductive step, is to prove that the true statement for the number \(n\) implies that the statement for \(n+1\) is also true.

To understand how the method of induction works we look at dominoes. Have you ever seen a line of dominoes falling? How does it happen?

To prove that a line of dominoes will all fall when we push the first one, we just have to prove that:

• The first domino falls down (base case)

• The dominoes are close enough that each domino will knock over the next one when it falls (inductive step).

Pascal’s triangle, (known as Khayyam’s triangle in Iran and Yang Hui’s triangle in China) is seen below.

Well, what does it mean? We start with diagonal lines of 1s. Then every other number in the interior is the sum of the two numbers above it. With this simple rule, the triangle shows lots of cool structure.

An equation of the form \(x^2 - dy^2 = 1\) where \(d>0\) is a nonsquare (what if \(d\) is a square?) integer and we seek \(x,y\) in the integers is called Pell’s equation. By changing the sign of \(x\) and \(y\), we may assume they are nonnegative. There is always the solution \((x,y)=(1,0)\) which we call trivial.

Here is a useful way to think about the solutions to Pell’s equations. The difference of squares identity prompts us to consider the solution \((x,y)\) to Pell’s equation as the real number \(x+y\sqrt{d}\). The fact that \((x,y)\) is a solution simply means \((x+y\sqrt{d})(x-y\sqrt{d})=1\).

Here is some common notation you might see if you look at books or on the internet: if we have a number \(u=x+y\sqrt{d}\), we can define its conjugate as the number \(\bar u=x-y\sqrt{d}\). Moreover, the set of numbers of the form \(x+y\sqrt{d}\) where \(x,y\) are whole numbers, is often written as \(\mathbb Z[\sqrt{d}]\) (pronounced “integers adjoint \(\sqrt{d}\)"). Therefore, a number \(u\) that belongs to \(\mathbb Z[\sqrt{d}]\) is a solution to Pell’s equation if \(u\bar u=1\).

As with all Diophantine equations, we would like to to know the following about Pell’s equation.

1. Does Pell’s equation always have nontrivial solutions?

2. When Pell’s equation does have solutions, is the number of solutions finite?

3. How can we describe all solutions to Pell’s equation?

In this sheet, we answer all of the questions above and apply these theoretical results to some other problems.

Just like atoms are the building blocks of molecules, prime numbers are the building blocks of integers, or whole numbers. What do we mean by this?

Well, every molecule is composed of atoms, and each atom is an atom of a particular element, like carbon or nitrogen. Similarly, every positive integer (except \(1\)) can be broken down into prime numbers. We can say this formally as follows:

The Fundamental Theorem of Arithmetic says that any natural number greater than \(1\) can be uniquely expressed as a product of prime numbers in non-decreasing order. For example: \[630=2\times3\times3\times5\times7=2\times3^2\times5\times7.\]

Recall that a number is composite if it is a product of two smaller, natural numbers. For example, \(6 = 2\times3\). Otherwise, and if the number is not equal to \(1\), it is called prime. The number \(1\) is neither prime nor composite.

Modulo operation: We look at division. For example \(41=2\times15+11\) is the division of \(41\) (the dividend) by \(15\) (the divisor) with remainder \(11\), and \(5=0\times7+5\) is the division of \(5\) by \(7\) with the remainder \(5\). More generally, when we divide \(a\) by \(b\), we’re looking for non-negative integers \(c\) and \(d\) (\(d<b\)) such that \(a=c\times b+d\).
In the case of \(45\) divided by \(15\), we get \(3\) with remainder \(0\) - in which case we say “\(15\) divides \(45\)", or “\(45\) is divisible by \(15\)". We can write this as \(15|45\).

We can deduce from the Fundamental Theorem of Arithmetic that if a product of two natural numbers is divisible by a prime number, then one of these numbers is divisible by this prime number. For example, \(7|7007=13\times539\) tells us that \(7\) divides \(13\) or \(539\). Clearly \(7\nmid13\), so we know \(7|539\).