Counting cleverly

Some questions ask "how many?" when there are far too many things to count one by one. How many handshakes at a party of 30 people? How many squares hide in a grid? Clever counting means finding a short way to get the total without missing any and without counting any twice. A second kind of question asks how many you need to be sure of something. For those, the trick is to imagine the unluckiest thing that could happen. Both ideas are used every day by people who write computer programs and plan sports leagues.

Handshakes at a party

There are 5 people at a party. Each one shakes hands once with every other person. How many handshakes are there? Each person shakes hands with the 4 others, so it looks like 5 × 4 = 20. But when Ana shakes hands with Ben, that one handshake is counted twice: once for Ana and once for Ben. So divide by 2.

Sometimes the question goes the other way: you know the handshakes and must find the people. Double the number of handshakes. Then look for two whole numbers next to each other that multiply to give it. The bigger one is the number of people.

Squares in a grid

A big square is cut into a 3 by 3 grid of small squares. How many squares are there in total? Not just 9: the small squares can join to make bigger squares. Count by size.

• 1 by 1 squares: 3 in each row and 3 rows, so 3 × 3 = 9.
• 2 by 2 squares: a 2 by 2 square can start in 2 places across and 2 places down, so 2 × 2 = 4.
• 3 by 3 squares: only the whole grid, so 1.
• Total: 9 + 4 + 1 = 14.

Socks in the dark

A drawer has 8 red socks and 8 blue socks. It is dark, so you cannot see the colors. How many socks must you take to be sure of two of the same color? Think of the unluckiest case, the worst case. With 2 socks, you might get one red and one blue: no pair. But the 3rd sock must be red or blue, so it matches one of them. The answer is 3.

This is called the pigeonhole principle. A pigeonhole is one small box in a wall of boxes. If 13 pigeons fly into 12 holes, at least one hole has two pigeons. In the same way, if 13 people are in a room, at least two of them have their birthday in the same month, because there are only 12 months.

Being sure of something harder

The same worst-case thinking answers harder questions. Ask: what is the longest I could go without getting what I want? Then take one more.

Gloves are a little harder, because a glove is a left one or a right one. A drawer has 5 pairs of black gloves and 5 pairs of white gloves. How many must you take to be sure of a left and a right glove of the same color? In the worst case, the first 10 gloves are all left gloves: 5 black and 5 white. There are no more left gloves, so the 11th is a right glove. Whatever its color, there is a left glove of that color already in your hand. The answer is 11.

The fewest coins

You must pay an exact amount with as few coins as possible. The plain method is to take the biggest coin that fits, again and again, until nothing is left.

This works for the coins most countries use. But with unusual coins it can fail. With coins of 1, 10 and 25 cents, the biggest-first method pays 30 cents as 25 + 1 + 1 + 1 + 1 + 1: 6 coins. Three 10-cent coins make 30 with only 3.

Finding the heavier coin with a balance

You have 9 coins that look the same, but one is a little heavier. A balance scale has two pans and tells you which side is heavier, or that they weigh the same. What is the fewest weighings that always finds the heavy coin? Most people split the coins in half. The better idea is to split them into three groups, because one weighing has three possible results: the left pan is heavier, the right pan is heavier, or they balance.

Each weighing cuts the number of possible coins to a third. So 1 weighing can handle 3 coins, 2 weighings 9 coins, 3 weighings 27 coins, and 4 weighings 81 coins. For a number in between, use the next one up: 8 coins still need 2 weighings (weigh 3 against 3; if they balance, weigh the last 2 against each other), and 10 coins need 3.