Problems

The numbers \(x,a,b\) are natural. Show that \(\gcd(x^a -1,x^b-1) = x^{\gcd(a,b)}-1\).

Let \(p\) be a prime number bigger than \(3\). Prove that \(p^2-1\) is a multiple of 24.

Is it possible to draw \(K_5\) without intersecting edges on a Möbius band? Recall that \(K_5\) is the complete graph on \(5\) vertices. That is, \(5\) points with an edge between every pair of different points.

In chess, knights can move one square in one direction and two squares in a perpendicular direction. This is often seen as an ‘L’ shape on a regular chessboard. A closed knight’s tour is a path where the knight visits every square on the board exactly once, and can get to the first square from the last square.

This is a closed knight’s tour on a \(6\times6\) chessboard.

Can you draw a closed knight’s tour on a \(3\times3\) torus? That is, a \(3\times3\) square with both pairs of opposite sides identified in the same direction, like the diagram below.

You may remember the game Nim. We will now play a slightly modified version, called Thrim. In Thrim, there are two piles of stones (or any objects of your choosing), one of size \(1\) and the other of size \(5\).
Whoever takes the last stone wins. The players take it in turns to remove stones - they can only remove stones from one pile at a time, and they can remove at most \(3\) stones at a time.
Does the player going first or the player going second have a winning strategy?

A circle is inscribed in a triangle (that is, the circle touches the sides of the triangle on the inside). Let the radius of the circle be \(r\) and the perimeter of the triangle be \(p\). Prove that the area of the triangle is \(\frac{pr}{2}\).

We meet a group of people, all of whom are either knights or liars. Knights always tell the truth and liars always lie. Prove that it’s impossible for someone to say “I’m a liar".

We’re told that Leonhard and Carl are knights or liars (the two of them could be the same or one of each). They have the following conversation.

Leonhard says “If \(49\) is a prime number, then I am a knight."

Carl says “Leonhard is a liar".
Prove that Carl is a liar.

Today we will solve some logic problems. This time, we are visiting a strange planet. This planet is inhabited by two kinds of aliens, Cricks and Goops. The physical differences between them are not enough for a human being to distinguish them, but they have another remarkable feature. They can only ask questions. Cricks can only ask questions whose answer is yes, while Goops can only ask questions whose answer is no.

Let \(p\) be a prime number greater than \(3\). Prove that \(p^2-1\) is divisible by \(12\).