Problems

Age
Difficulty
Found: 2307

Today we will learn a really useful strategy for solving a certain kind of problems. This strategy is called the invariance principle, and after working through this sheet you’ll be able to recognise easily when we need to use an invariant to solve a problem. This strategy is applicable to kinds of problems where some task is repeatedly performed, and we wish to see if it is possible to transform our “initial state" into some given “final state". The key is to ask yourself:

What stays the same?

The topic of this problem sheet will be polynomials. Before we dive into the examples, let’s recap a few key concepts.

A polynomial in \(x\) is an expression formed by adding or subtracting monomials, which are terms of the form \(a x^n\), where \(a\) is a number called a coefficient, and \(n\) is a whole number (non-negative integer). Here, \(x\) is a variable that may represent a number. The degree of a polynomial \(f\), written as \(\deg(f)\) is the highest power of \(x\) appearing in the polynomial. For example: \(\deg(x^3+x^2+x)=3\).

We can perform several familiar operations on polynomials, which you may have seen before:

  • Addition and subtraction: We add or subtract polynomials by looking at each power of \(x\) and adding or subtracting the corresponding coefficients. For example, if \[f(x) = x^4 + 3x - 1 \quad \text{and} \quad g(x) = x^3 + 2x + 5,\] then \(f(x) - g(x) = x^4 - x^3 + x - 6\).

  • Multiplication: We use the distributive property, which means that every term in the first polynomial is multiplied by every term in the second polynomial. For example, if \[f(x) = x^2 + x + 1 \quad \text{and} \quad g(x) = x - 1,\] then \(f(x) g(x) = (x^2 + x + 1)(x - 1) = x^3 + x^2 + x - x^2 - x - 1 = x^3 - 1.\)

Let’s now present the examples. They have some very important techniques, so read them carefully before attempting the problems.

Today we will solve some problems using algebraic tricks, mostly related to turning a sum into a product or using an identity involving squares.
The ones particularly useful are: \((a+b)^2 = a^2 +b^2 +2ab\), \((a-b)^2 = a^2 +b^2 -2ab\) and \((a-b) \times (a+b) = a^2 -b^2\). While we are at squares, it is also worth noting that any square of a real number is never a negative number.

Certain geometric objects nicely blend when they happen to be together in a problem. One possible example of such a pair of objects is a circle and an inscribed angle.
We will be using the following statements in the examples and problems:
1. The supplementary angles (angles “hugging" a straight line) add up to \(180^{\circ}\).
2. The sum of all internal angles of a triangle is also \(180^{\circ}\).

image

3. Two triangles are said to be “congruent" if ALL their corresponding sides and angles are equal.
We recommend solving the problems in this sheet in the order of appearance, as some problems use statements from previous problems as a step in the solution. Specifically, the inscribed angle theorem (problem 2) is required to solve every other problem that comes after it.

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.