Problems

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

In this sheet, we will look at basic counting problems. The fundamental principle is quite simple. If you have two independent choices to make, then the number of options for making both choices is calculated by multiplying the number of options for each choice.

An issue we frequently run into is that of overcounting. This means we count the same thing more than once. In the examples and problems today, you will see various ideas that we can use to correct for overcounting, or for avoiding it.

From the examples above, we see that we often need to pick \(k\) objects from \(n\) objects where the order of the \(k\) objects is ignored. The number of ways to pick them is notated with the special symbol \(\binom{n}{k}\), pronounced “\(n\) choose \(k\)". What’s a formula for \[\binom{n}{k}\]?

You meet an alien, who you learn is thinking of a positive integer \(n\). They ask the following three questions.

“Am I the kind who could ask whether \(n\) is divisible by no primes other than \(2\) or \(3\)?"

“Am I the kind who could ask whether the sum of the divisors of \(n\) (including \(1\) and \(n\) themselves) is at least twice \(n\)?"

“Is \(n\) divisible by 3?"

Is this alien a Crick or a Goop?

Today we will solve some problems about finding areas of geometric figures. You only need to know how to calculate the area of a rectangle, a triangle and a circle to be able to solve every problem in this set. Here is a brief description of the area formula for each shape.

We start with rectangles because they are easy. In the picture below, one way to find the area of the rectangle is to multiple the length of the side \(AB\) by the length of the side \(AD\).

Next we consider the area of a triangle. In general, the area of a triangle is given by \(\frac{1}{2}bh\), where \(b\) is the length of a chosen base and \(h\) is the height (the length of the altitude corresponding to that base). Finding a base and a corresponding altitude is usually straightforward. However, it can be a bit tricky if the altitude lies outside the triangle. See the picture below for one such case. The segment \(AB\) is the base and \(CD\) is the altitude. If the area formula seems hard to believe in this case, please have a look at problem 6.

At last, we come to the area of a circle. If a circle has radius \(r\), its area is \(\pi r^2\). A fully rigorous proof requires calculus! The number \(\pi\) is approximately 3.14159 to five decimal points.