Kids Code & Computer Science

Here is a deceptively simple math puzzle at least 1200 years old.

Recreational math problems and puzzles are key to learning how to solve problems. The ability to carefully tease out an answer from a complicated problem, reducing complexity and confusion to the simplest possible units, also is key to learning computer science and programming.

Every issue of this magazine will have at least one puzzle and math problem. Solutions will be offered at the bottom of the page but you have to promise not to to cheat and look up the answer. It's the honor system.

The Problem

This problem comes from one of the oldest collections of mathematical problems, Problems to Sharpen the Young. Some scholars say the author might have been Alcuin, who lived from about 732 to 804 AD. Alcuin lived near the city of York, in England, and became a teacher and then head of the Cathedral School at York which still exists, as St. Peter’s School, York.

Here is the math problem to solve:

A staircase has 100 steps. On the first step stands a pigeon; on the second, two pigeons; on the third, three; on the fourth, four; on the fifth, five; and so on, on every step up to the hundredth where there are 100 pigeons on the hundredth step. How many pigeons are there altogether?

If 100 steps is too hard, answer the problem for 20 stairs, or 10 stairs.

If pigeons gross you out, feel free to substitute kittens, hamsters, or whatever makes you happy.

Answers

Here are answers to the puzzle. Hopefully you tried to solve the problems instead of skipping down this page.

My teenage son also tells me this is an unfair puzzle to unleash on third graders. Perhaps.

Let’s begin by solving this problem for 10 stairs, to see what insights we might get to help solve the problem for 20 stairs and 100 stairs. It’s also easier to use a chalkboard or piece of paper to map out all the possibilities for a simpler version of this puzzle.

Here’s one way to solve for 10 stairs:

1+2+3+4+5+6+7+8+9+10

That’s difficult. And it doesn’t scale for 100 stairs or 20 stairs. So let’s think a different way. What if, instead of counting individual stairs, we counted in pairs? That would reduce our counting in half. And what if you tried different pairs of stairs, for example, counting the 1 pigeon on stair 1 with the 9 pigeons on stair 9? That’s 10 pigeons, an easy number to remember. If you look deeper, you’ll notice this pattern:

1+9 (stair 1 pigeons + stair 9 pigeons)
2+8
3+7
4+6

Of our 10 stairs full of pigeons, four pairs each add up to 10, don’t they? If you add the pigeons on stair 5 and stair 10, your count looks like this:

1+9 (stair 1 pigeons + stair 9 pigeons)
2+8
3+7
4+6
5
10

That can be expressed this way:

(4 x 10) + 5 + 10

That’s much easier to calculate than adding each number individually, isn’t it? It’s 55 pigeons total on the 10 stairs.

Let’s apply this pair solution to 20 stairs:

1+19 (stair 1 pigeons + stair 19 pigeons)
2+18
3+17
4+16
5+15
6+14
7+13
8+12
9+11
10
20

The nine pairs each total 20 with the pigeons on stairs 10 and 20 counted as singles. The calculation is:

(9 x 20) + 10 + 20

That’s also much easier to calculate than adding up all numbers from 1 to 20, isn’t it? For 20 stairs, we have 180 pigeons in pairs of stairs plus 30, or 210 pigeons.

So let’s tackle how many pigeons would be on 100 stairs.

The total number of pigeons on the first stair and 99th stair is 100 (1 pigeon on the first stair + 99 pigeons on the 99th stair). Same for the total number of pigeons on the second stair and the 98th stair. And the third stair and the 97th stair. Every pair of stairs equals 100 pigeons, except the middle stair (50th) and top stair (100th). This partial list gives an idea of how you can count in pairs to calculate the number of pigeons quickly:

1+99 = 100 pigeons
2+98
3+97
4+96
5+95
6+94
7+93
8+92
9+91
10+90
20+80
25+75
30+70
40+60
49+51
50 pigeons on the 50th step
100 pigeons on the 100th step

Thus you have 49 pairs of 100 pigeons for 4900 pigeons, plus 50 pigeons from the 50th step and a final 100 pigeons from the 100th step, for a total of 4900 + 50 + 100 or 5050 pigeons.

Pseudo Code

If we had to calculate the number of pigeons with software code, we could convert this process into the following steps, or pseudo code:

1. Divide the last number, an even number, by 2 to get the middle number.
2. The number of pairs will be the middle number minus one.
3. The middle number and last number will be unpaired.
4. Multiply the number of pairs by the last number, an even number.
5. Add to the multiplication result the middle number and last number.

Let’s perform these tasks with a last even number of 10:

1. Divide the last number by 2 to get the middle number: 5.
2. The number of pairs will be the middle number (5) minus one: 4 pairs.
3. The middle number (5) and last number (10) will be unpaired.
4. Multiply the number of pairs (4) by the last number (10): 40.
5. Add to the multiplication result (40) the middle number (5) and last number (10): 55.

In writing this article, originally I had Step 1 as the second step. When I looked more closely, however, I realized the middle number is used in several steps. Therefore, I defined the middle number first, as Step 1, so it could be used in Steps 2, 3, and 5. This sort of optimization is part of the programming process, the fun part, I might add.

What is the value in defining this math pattern? With programming, you often have to reduce problems told as stories into math calculations. You also have to reduce the stories to their simplest form to make your code as flexible as possible.