## Investigating Practical Ordering of Grids

In Reinforcement Learning there is an environment known as Gridworld. In this environment you have a grid and there is an agent that learns how to find the shortest path from one cell to another. The theme of reinforcement learning is that you do not want to hard-code the rules, but you want the agent to explore until it can find a set of moves that are optimal for the problem at hand. Usually you can alter the grids to make the tasks tough–set ‘traps’, add obstacles, etc. We are considering grids with obstacles, and an interesting question that came up is the following,

Given two grids of size ${N}$, say ${G, \,G'}$ which have respectively ${k,l}$ obstacles where ${k,l\in \mathbb{N},\,k,l\geq 0}$, what are reasonable ways to put an order on the ‘complexity’ of the grids?

In other words, we want to be able to say that, for instance, in ${G}$ the agent will find the optimal path more easily than in ${G'}$ given any two grids ${G,G'}$.…

## 1.5 Equivalence classes (Infinite sets)

Let’s find the equivalence classes of the following finite set S:

Given $S = \{ -1, 1, 2, 3, 4 \},$ we can form the following relation $R = \{ (-1, -1), (1,1), (2,2), (3,3), (4,4), (1,3), (3,1), (2,4), (4,2) \}.$

Note: writing the relation $R$ on set $S$ in the following ways is equivalent:

$-1R-1, 1R1, 2R2, 3R3, 4R4, 1R3, 3R1, 2R4, 4R2$

or

$-1\le -1, 1 \le1, 2 \le2, 3 \le3, 4 \le4, 1 \le 3, 3 \le 1, 2 \le 4, 4 \le 2$

This relation, $R$ has been given the symbol $\le$ but it means “the same sign and parity” in this case. For instance, $(1,3)$ or $1 \le 3$ tells us that one and three are both odd and both have the same sign in set $A$ (both positive).

The equivalence classes for this relation are the following sets:

$\{ -1 \}, \{ 1, 3\} \text{ and } \{2, 4 \}$

We obtained the above equivalence classes by asking ourselves:

• How is the element $-1$ related to any other element in the set $S$ under the definition of $R?$

Since R is defined as “the same sign and same parity,” then we’re really asking ourselves whether $-1$ has the same sign as any other element in $S.$ Since all the other elements are positive, then $-1$ has the equivalence class containing only itself. Another question we would’ve asked ourselves is whether $-1$ is even or odd. …

## The 2018 South African Mathematics Olympiad — Problem 6

The final round of the South African Mathematics Olympiad will be taking place on Thursday, 28 July 2019. I have been writing about some of the problems from the senior paper from 2018. A list of all of the problems can be found here.

Today we will look at the sixth and final problem from the 2018 South African Mathematics Olympiad:

Let $n$ be a positive integer, and let $x_1, x_2, \dots, x_n$ be distinct positive integers with $x_1 = 1$. Construct an $n \times 3$ table where the entries of the $k$-th row are $x_k, 2x_k, 3x_k$ for $k = 1, 2, \dots, n$. Now follow a procedure where, in each step, two identical entries are removed from the table. This continues until there are no more identical entries in the table.

1. Prove that at least three entries remain at the end of the procedure.
2. Prove that there are infinitely many possible choices for $n$ and $x_1, x_2, \dots, x_n$ such that only three entries remain,

There are some heuristics that are often helpful when solving a problem, such as

• Looking at small cases:

This helps us to understand the problem and how the various pieces in the problem relate to each other.

## On the invariant measure in special relativity

I’m writing this for my string theory class. We are basing our lectures on Zwiebach – A First Course in String Theory, and starting off with special relativity. Not everybody in the class has a physics background (pure and applied mathematics students), and so there are likely to be questions which come up which show where I have to fill in some knowledge. We had a question about the invariant measure in special relativity (SR) and why there was a different sign in front of the time term compared with the space terms. I’ll do my best to explain here. Note that I am not explaining it in the precise chronological order of discoveries.

We start the picture off with relativity before SR – that is, Galilean Relativity. This simply states that the laws of motion are the same in all inertial (non-accelerating frames). That may sound straightaway like SR, but there’s a crucial ingredient missing which we will see in a bit.…

## 1.4 Equivalence classes

Let’s recall the definition of an equivalence relation:

A relation R on a set A is termed an equivalence relation if it is simultaneously reflexive, symmetric and transitive.

Let’s look at more examples:

Example One: Let $A = \{2, 11, 17, 20\}$ be a set with the following relation: $R = \{ (2,2) (11,11) (17,17) (20,20) (2,20) (20,2) (11,17) (17,11) \}.$

The relation described by R is termed “the same parity.” Elements x and y are said to have the same parity if they are both odd or both even. In our case, the elements 11 and 17 are both odd – hence have the same parity. Similarly, 20 and 2 have the same parity because they are both even. An element will always have the same parity as itself.

The elements that share the same parity as 11 can be grouped together to form a set: $O = \{ 11, 17 \}.$ This is the set of all odd elements from A.

Similarly, the even elements can be grouped together to form the set: $E = \{ 2, 20\}.$

The new sets, O and E, form the equivalence classes of the relation R on set A.…

## The 2018 South African Mathematics Olympiad — Problem 5

The final round of the South African Mathematics Olympiad will be taking place on Thursday, 28 July 2019. I have been writing about some of the problems from the senior paper from 2018. A list of all of the problems can be found here.

Today we will look at the fifth problem from the 2018 South African Mathematics Olympiad:

Determine all sequences $a_1, a_2, a_3, \ldots$ of nonnegative integers such that $a_1 < a_2 < a_3 < \ldots$, and $a_n$ divides $a_{n - 1} + n$ for all $n \geq 2$.

Since the sequence $a_1, a_2, \ldots$ is strictly increasing, we know that $a_n \geq n - 1$ for all positive integers $n$. (We could prove this rigorously by induction.) This means that $a_{n - 1} + n \leq (a_n - 1) + (a_n + 1) = 2a_n$ for all $n$, and so we know that $a_{n - 1} + n$ is equal to either $a_n$, or to $2a_n$ for all positive integers $n$. Perhaps we should try to figure out exactly when it is equal to $a_n$, and when it is equal to $2a_n$. If we knew, for example, that we always have that $a_{n - 1} + n = a_n$, then we have reduced the problem to solving this recurrence relation.…

## The 2018 South African Mathematics Olympiad — Problem 4

The final round of the South African Mathematics Olympiad will be taking place on Thursday, 28 July 2019. In the week leading up to the contest, I plan to take a look at some of the problems from the senior paper from 2018. A list of all of the posts can be found here.

Today we will look at the fourth problem from the 2018 South African Mathematics Olympiad:

Let $ABC$ be a triangle with circumradius $R$, and let $\ell_A, \ell_B, \ell_C$ be the altitudes through $A, B, C$ respectively. The altitudes meet at $H$. Let $P$ be an arbitrary point in the same plane as $ABC$. The feet of the perpendicular lines through $P$ onto $\ell_A, \ell_B, \ell_C$ are $D, E, F$ respectively. Prove that the areas of $DEF$ and $ABC$ satisfy the following equation:

$\displaystyle \text{area}(DEF) = \frac{{PH}^2}{4R^2} \cdot \text{area}(ABC).$

Once again, we begin by creating a diagram. Again, since I already know how the solution plays out, I’ve drawn in the circle that passes through $P, E, D, H$, and $F$. We do know yet that these points are concylic, however, as it is not given directly in the problem statement.…

## 1.3 Relations: Equivalence relations

We know that a relation is called an Equivalence Relation when it is reflexive, symmetric AND transitive on some set A. Let’s look at some examples.

Example One: Let $a,b \in \mathbb{R}.$ Suppose we have that a is related to b (i.e. a ~ b) if $a - b \in \mathbb{Z}.$ We want to show that our relation ~ is an equivalence relation.

First, let’s unpack what the question requires us to prove: It wants us to show that the relation ~ on set A is an equivalence relation. Hence, we need to show that ~ is reflexive, symmetric and transitive.

The relation ~ (in this case) is defined as follows: IF any two real numbers, a and b, are related THEN we know that a – b is some integer.

It’s important to note that the order in which a relation is important! Always write your equations as they’ve been given in the question to avoid confusion and mistakes

Ok, let’s prove this.…

## 1.2 Relations: Properties

Note: Do not confuse binary operations (+, x, -, …) with relations. Recall the definition for a relation as:

A relation R on a set A is a subset R ⊆ A × A. We often abbreviate the statement (x, y) ∈ R as xRy.

For instance, the binary operation “x” has a numeric value: $3 \times 3 = 9 \text{ and } 40 \times \frac{1}{5} = 8.$ Yet a mathematical relation, for example “<“, has a True/False value: $3 < 3 \text{ and } 40 < \frac{1}{5}$ are both False expressions.

We want to look at some properties of relations. We will look at three properties for relation expressions:

Suppose A is a set with relation R, then

1. Relation R is Reflexive if $\forall x \in A, \text{ } xRx$
2. Relation R is Symmetric if $\forall x,y \in A, \text{ } xRy \rightarrow yRx$
3. Relation R is Transitive if $\forall x,y,z \in A, \text{ } xRy \wedge yRz \rightarrow xRz$

The first property tells us that if every element, x, in set A is related to itself, then the relation R acting on the set A is termed “reflective.”

The second property tells us that if “x is related to y” from set A implies that “y is also related to x,” then R is termed “symmetric.”

Lastly, if “x is related to y” and “y is related to z” implies that “x is also related to z,” then the relation R is termed “transitive.”

Let’s look at the following examples: $A = \{ 1, 2, 3, 4\}$ with relation $\le.$ Then:

$\forall x \in A, \text{ } x \le x$

In other words $\le$ is reflexive since every number in set A is equal to itself (i.e.…