Problems

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.

A library keeps track of its books by a code with two (not necessarily different) letters taken from A to Z, followed by a three digit number from 000 to 999. What is the maximum number of books one can keep in the library and still tell them apart by looking at their codes?

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\)". Following a similar line of reasoning as the examples, we can write down a general formula:

\[\binom{n}{k} = \frac{n\times (n-1) \times \dots (n-k+1)}{k\times (k-1) \times \dots 1} = \frac{n!}{k!(n-k)!}.\]

\(n!\) is a shorthand for \(n\times (n-1)\times \dots \times 1\), pronounced “\(n\) factorial". This is another useful expression and allows us to write down many formulas succinctly.

Which of the following numbers are divisible by \(11\) and which are not? \[121,\, 143,\, 286, 235, \, 473,\, 798, \, 693,\, 576, \,748\] Can you write down and prove a divisibility rule which helps to determine if a three digit number is divisible by \(11\)?

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?

There is a secret gathering of a group of \(n\) aliens in a very dark room. You cannot see anyone in the room, but you hear the following questions.

1. “Is at least one of us a Goop?"

2. “Is the number of Goops amongst us an even number?"

3. “Is the number of Goops amongst us a multiple of 3?"

4. \(\dots\)

5. “Is the number of Goops amongst us a multiple of \(n\)?"

What are all the possible values of \(n\) such that this gathering can happen? Note that each of the \(n\) aliens have asked exactly one question.

You meet a group of \(n\) aliens. The first alien asks “is at least one of us a Goop?", the second alien asks “are at least two of us Goops?", the third asks “are at least three of us Goops?" and so on until the final one says “are at least \(n\) of us Goops?".

How many Goops are there?

Suppose you only knew the formula of a triangle for right-angled triangles. That is, if a base with length \(b\) and a height \(h\) of a triangle meet at a right angle, you know that the area of the triangle is \(\frac{1}{2}bh\). Can you prove the usual area formula for a general triangle?

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.

There is a pair of parallel lines. The point \(A\) and \(B\) lie on one of the lines. The point \(C\) and \(D\) lies on the other line. We can form triangles \(\triangle ABC\) and \(\triangle ABD\). Prove that the areas of triangles \(\triangle ABC\) and \(\triangle ABD\) are equal.