Problems

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

Let \(A\), \(B\), \(C\) and \(D\) be four points labelled clockwise on the circumference of a circle. The diagonals \(AC\) and \(BD\) intersect at the centre \(O\) of the circle. What can be deduced about the quadrilateral \(ABCD\)?

Consider the 7 different tetrominoes. Is it possible to cover a \(4\times7\) rectangle with exactly one copy of each of the tetrominoes? If it is possible, provide an example layout. If it is not possible, prove that it’s impossible.

We allow rotation of the tetrominoes, but not reflection. This means that we consider \(S\) and \(Z\) as different, as well as \(L\) and \(J\).

In the following grid, how many different ways are there of getting from the bottom left triangle to the bottom right triangle? You must only go from between triangles that share an edge and you can visit each triangle at most once. (You don’t have to visit all of the triangles.)

Let’s play some games today! We will play a classic game known as nim, which is thought to be one of the oldest games.

Typically people play nim using matchsticks, though stones and coins are popular too. There are a few heaps of matchsticks in nim. Players take turns to remove matchsticks from a heap of their choosing. The player can remove any number of matchsticks they wish from that heap. Whoever has no matchsticks left to take loses.

This following position will be written as \(\text{Nim}(3,3,3)\):

As another example, this is \(\text{Nim}(1,2,3,4)\):

We will omit heaps of size zero, so \(\text{Nim}(3,0,3,0,3)\) is the same as \(\text{Nim}(3,3,3)\).

Nim is important because a large class of games are equivalent to it despite its simple appearance. The interested reader should look up “Sprague-Grundy Theorem".

Let us introduce a few terms that will be helpful for analyzing games. A game \(G\) consists of some positions and a set of rules. A position \(g\) in the game \(G\) is called a winning position if the player starting this turn has a winning strategy. This means as long as the player starting this turn continues to play optimally, the second player has to lose. Conversely, a position \(g\) is a losing position if the player starting this turn has no winning strategy.

Let us define XOR (or addition mod 2). XOR is defined for 0 and 1 only. Here is a table recording the values of XOR:

Now we define the important concept of nim-sum. Given two natural numbers \(x\) and \(y\), we first convert them into binary representations and then compute XOR on individual digits. The resulting number, denoted \(x \oplus y\), is the nim-sum of \(x\) and \(y\). Here is an example.

This is simply saying \(22 \oplus 5 = 19\). Note that \(22=(10110)_2\) and \(5=(00101)_2\).

Verify \((x \oplus y) \oplus z = x \oplus (y \oplus z)\), so we can speak of \(x \oplus y \oplus z\) with no ambiguity.

Show that \(x \oplus y = 0\) if and only if \(x = y\). Remember that \(x \oplus y\) denotes the nim-sum of \(x\) and \(y\).

Show that \(\text{Nim}(x,y,z)\) is a losing position if and only if \(x \oplus y \oplus z = 0\). Remember that \(x \oplus y\) denotes the nim-sum of \(x\) and \(y\).

Is \(\text{Nim}(7,11,15)\) a winning position or a losing position? If it is a winning position, what is the optimal move?

Two fractions sum up to \(1\), but their difference is \(\frac1{10}\). What are they?