Problems

There are \(n\) balls labelled 1 to \(n\). If there are \(m\) boxes labelled 1 to \(m\) containing the \(n\) balls, a legal position is one in which the box containing the ball \(i\) has number at most the number on the box containing the ball \(i+1\), for every \(i\).

There are two types of legal moves: 1. Add a new empty box labelled \(m+1\) and pick a box from box 1 to \(m+1\), say the box \(j\). Move the balls in each box with (box) number at least \(j\) up by one box. 2. Pick a box \(j\), shift the balls in the boxes with (box) number strictly greater than \(j\) down by one box. Then remove the now empty box \(m\).

Prove it is possible to go from an initial position with \(n\) boxes with the ball \(i\) in the box \(i\) to any legal position with \(m\) boxes within \(n+m\) legal moves.

Given a natural number \(n\), find a formula for the number of \(k\) less than \(n\) such that \(k\) is coprime to \(n\). Prove that the formula works.

Today we will draw lots of pictures.

The subject is Topology. It is often called “rubber-sheet geometry" because while it is the study of shapes, topologists typically do not pay too much attention to rigid notions like angle and lengths. We have much more flexibility in topology. Some common words describing the operations here might include “gluing", “stretching", “twisting" and “inflating".

Although we will not define continuity, it is a more or less intuitive idea. Topological operations should be continuous. If you have a line segment, no amount of stretching, twisting or bending can make it into two disconnected segments.

Let \(A=\{1,2,3\}\) and \(B=\{2,4\}\) be two sets containing natural numbers. Find the sets: \(A\cup B\), \(A\cap B\), \(A-B\), \(B-A\).

Let \(A=\{1,2,3,4,5\}\) and \(B=\{2,4,5,7\}\) be two sets containing natural numbers. Find the sets: \(A\cup B\), \(A\cap B\), \(A-B\), \(B-A\).

Given three sets \(A,B,C\). Prove that if we take a union \(A\cup B\) and intersect it with the set \(C\), we will get the same set as if we took a union of \(A\cap C\) and \(B\cap C\). Essentially, prove that \((A\cup B)\cap C = (A\cap C)\cup (B\cap C)\).

\(A,B\) and \(C\) are three sets. Prove that if we take an intersection \(A\cap B\) and unite it with the set \(C\), we will get the same set as if we took an intersection of two unions \(A\cup C\) and \(B\cup C\). Essentially, prove that \((A\cap B)\cup C = (A\cup C)\cap (B\cup C)\). Draw a Venn diagram for the set \((A\cap B)\cup C\).

Let \(A,B\) and \(C\) be three sets. Prove that if we take an intersection \(A\cap B\) and intersect it with the set \(C\), we will get the same set as if we took an intersection of \(A\) with \(B\cap C\). Essentially, prove that it does not matter where to put the brackets in \((A\cap B)\cap C = A\cap (B\cap C)\). Draw a Venn diagram for the set \(A\cap B\cap C\).
Prove the same for the union \((A\cup B)\cup C = A\cup (B\cup C) = A\cup B\cup C\).

For three sets \(A,B,C\) prove that \(A - (B\cup C) = (A-B)\cap (A-C)\). Draw a Venn diagram for this set.

For three sets \(A,B,C\) prove that \(A - (B\cap C) = (A-B)\cup (A-C)\). Draw a Venn diagram for this set.