Problems

Let \(n\geq 2\) be a integer. Fix \(2n\) points in space and select any \(n^2+1\) segments between these points. Show that these segments must form at least \(n\) triangles.

Elections are approaching in Problemland! There are three candidates for president: \(A\), \(B\), and \(C\).

An opinion poll reports that \(65\%\) of voters would be satisfied with \(A\), \(57\%\) with \(B\), and \(58\%\) with \(C\). It also says that \(28\%\) would accept \(A\) or \(B\), \(30\%\) \(A\) or \(C\), \(27\%\) \(B\) or \(C\), and that \(12\%\) would be content with all three candidates.

Show that there must have been a mistake in the poll.

You are creating passwords of length \(8\) using only the letters \(A\), \(B\), and \(C\). Each password must use all three letters at least once.

How many such passwords are there?

How many numbers from \(1\) to \(1000\) are divisible by \(2\) or \(3\)?

The inclusion–exclusion principle is a very useful counting tool. It is based on the simple idea of counting too much and then fixing the mistake.

Suppose there are two properties \(A\) and \(B\) that objects may or may not have (for example, a sticker can be shiny or round). Say there are \(a\) objects with property \(A\) and \(b\) objects with property \(B\). We ask: “How many objects have at least one of the two properties?”

If objects can have property \(A\) or property \(B\), but not both, then the answer is simply \(a+b\). However, if objects can have both properties, then \(a+b\) counts those objects twice. In the picture below, objects are shown as red dots, and the numbers show how many times each region is counted.

Let the number of objects with both properties be \(x\). These objects are counted twice, so to fix this we subtract \(x\). The correct total is therefore \(a+b-x\).

Now let us think about what happens with three properties \(A,B,C\). Suppose there are \(a\) objects with property \(A\), \(b\) with property \(B\), and \(c\) with property \(C\). The number \(a+b+c\) again overcounts. A picture helps us see by how much.

Let \(x\) be the number of objects with properties \(A\) and \(B\), \(y\) the number with \(B\) and \(C\), and \(z\) the number with \(A\) and \(C\). As before, we subtract \(x\), \(y\), and \(z\). This gives \(a+b+c-x-y-z\). But now we have gone too far.

Let \(w\) be the number of objects with all three properties. These were removed once too often, so we add \(w\) back. The correct total is \(a+b+c-x-y-z+w\).

We do not have to stop at three properties, but the formulas get longer. The key idea is always the same: notice when you have counted something too many times or too few times, and then correct it. Let us now look at some examples to see this idea in action.

Three kinds of cookies are sold at a store: dark chocolate \((D)\), raspberry with white chocolate \((R)\) and honeycomb \((H)\). Here is a table summarizing the number of people buying cookies this morning.

The column with label \(D,H\), for example, means the the number of people who bought both dark chocolate and honeycomb cookies.

How many people bought cookies this morning?

At the space carnival, visitors can try two special attractions: the Zero-Gravity Room or the Laser Maze. By the end of the day:

• \(100\) visitors have tried at least one of the two attractions,

• \(50\) visitors tried the Laser Maze,

• \(20\) visitors tried both attractions.

How many visitors tried only the Zero-Gravity Room?

We write all \(26\) different letters of the English alphabet in a line, using each letter exactly once.

How many such arrangements do not contain any of the strings fish, rat, or bird?