Problems

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

How many subsets of \(\{1, 2, . . . , n\}\) are there of even size?

In how many ways can \(\{1, . . . , n\}\) be written as the union of two sets? Here, for example, \(\{1, 2, 3, 4\}\cup\{4, 5\}\) and \(\{4, 5\}\cup\{1, 2, 3, 4\}\) count as the same way of writing \(\{1, 2, 3, 4, 5\}\) as a union.

Prove for any natural number \(n\) that \((n + 1)(n + 2). . .(2n)\) is divisible by \(2^n\).

Between two mirrors \(AB\) and \(AC\), forming a sharp angle two points \(D\) and \(E\) are located. In what direction should one shine a ray of light from the point \(D\) in such a way that it would reflect off both mirrors and hit the point \(E\)?
If a ray of light comes towards a surface under a certain angle, it is reflected with the same angle as on the picture.

Consider a set of natural numbers \(A\), consisting of all numbers divisible by \(6\), let \(B\) be the set of all natural numbers divisible by \(8\), and \(C\) be the set of all natural numbers divisible by \(12\). Describe the sets \(A\cup B\), \(A\cup B\cup C\), \(A\cap B\cap C\), \(A-(B\cap C)\).

Prove that the set of all finite subsets of natural numbers \(\mathbb{N}\) is countable. Then prove that the set of all subsets of natural numbers is not countable.

How many subsets are there of \(\{1,2,...,n\}\) (the integers from \(1\) to \(n\) inclusive) containing no consecutive digits? That is, we do count \(\{1,3,6,8\}\) but do not count \(\{1,3,6,7\}\).
For example, when \(n=3\), we have \(8\) subsets overall but only \(5\) contain no consecutive integers. The \(8\) subsets are \(\varnothing\) (the empty set), \(\{1\}\), \(\{2\}\), \(\{3\}\), \(\{1,3\}\), \(\{1,2\}\), \(\{2,3\}\) and \(\{1,2,3\}\), but we exclude the final three of these.

Most magic tricks rely on some kind of sleight of hand. However, some tricks are powered by maths!

A fruitful way of analyzing card shuffles is by using the idea of “permutations". Permutations are important objects that occur in various parts of maths. Many interesting patterns emerge, and we will only touch the tip of the iceberg today.

Suppose you have a set of ordered objects. A permutation of this set is a reordering of the objects. For example, a permutation of a deck of cards ordered from top to bottom is simply a shuffle of the cards. Note that in general, a permutation can be defined as a relabelling of objects, so an order is not necessary.

Let’s discuss two ways of writing permutations.

The first way is two-line notation. Say you have the cards from top to bottom Ace, two, three. Say Ace is 1. Suppose that after a shuffle \(p\), we have from top to bottom two, three, Ace. The two-line notation keeps the original positions on the first line and the new positions in the second line.

\[p = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 3 & 1 & 2 \\ \end{array} \right).\]

A second way of writing permutations is function notation. In the same situation, we could write \(p(1)=3\), \(p(2)=1\) and \(p(3)=2\).

As a first indication of why permutations give a useful perspective, we note that permutations can be done after another and the result is still a permutation. Let \(q\) be the permutation on the same three cards given by \(q(1)=2\), \(q(2)=3\) and \(q(3)=1\). Consider \(qp\) which is performing \(p\) first and then \(q\). To find out what the effect of this composite permutation is on \(1\), we can visualize it as follows: \[1\mapsto3=p(1)\mapsto q(p(1))=q(3)=1.\]

This shows that the function notation plays very nicely with composing permutations. By the way, if we work out the entire \(qp\) in this fashion, we find that \[qp = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 1 & 2 & 3 \\ \end{array} \right).\]

In other words, \(q\) has “negated" the effect of \(p\)!

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}\).

3. Two triangles are said to be “congruent" if ALL of their corresponding sides and angles are equal.
The following terminology will also be quite helpful. In the picture below, the points \(B\) and \(C\) lie on the circumference of the circle while the vertex \(A\) lies at the centre of the circle. We say that the angle \(\angle BAC\) is a central angle. The angle \(\angle DFE\) is called an inscribed angle because the vertices \(D\), \(F\) and \(E\) all lie on the circumference of the circle.