Problems

The set of symmetries of an object (e.g. a square) form an object called a group. We can formally define a group \(G\) as follows.

A is a non-empty set \(G\) with a binary operation \(*\) satisfying the following axioms (you can think of them as rules). A binary operation takes two elements of \(G\) and gives another element of \(G\).

1. Closure: For all \(g\) and \(h\) in \(G\), \(g*h\) is also in \(G\).

2. Identity: There is an element \(e\) of \(G\) such that \(e*g=g=g*e\) for all \(g\) in \(G\).

3. Associativity: For all \(g\), \(h\) and \(k\) in \(G\), \((g*h)*k=g*(h*k)\).

4. Inverses: For every \(g\) in \(G\), there exists a \(g^{-1}\) in \(G\) such that \(g*g^{-1}=e\).

Prove that the symmetries of the ‘reduce-reuse-recycle’ symbol form a group.

Let \(X\) be a finite set, and let \(\mathcal{P}X\) be the power set of \(X\) - that is, the set of subsets of \(X\). For subsets \(A\) and \(B\) of \(X\), define \(A*B\) as the symmetric difference of \(A\) and \(B\) - that is, those elements that are in either \(A\) or \(B\), but not both. In formal set theory notation, this is \(A*B=(A\cup B)\backslash(A\cap B)\).

Prove that \((\mathcal{P}X,*)\) forms a group.

You have a row of coins and you can perform these three operations as many times as you like:

1. Remove three adjacent heads

2. Remove two adjacent tails

3. If there’s a tail followed by a heads, then turn the tail over and put a new tail after both heads

You apply these operations until you can’t make any more moves. Show that you will always get the same configuration at the end, no matter the order.

Let \(a\) be a positive integer, and let \(p\) be a prime number. Prove that \(a^p - a\) is a multiple of \(p\).