beanz Magazine

Pigeons on the Stairs

Pank Seelen on Flickr

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.

Also In The October 2013 Issue

An Interview with Troy Hunt

Troy Hunt is a software architect and Microsoft Most Valued Professional (MVP) focusing on security concepts and process improvement in a Fortune 50 company. He's based in Australia.

1Password, LastPass, RoboForm

If you use a password you created that is less than eight characters, your password is vulnerable to hacking. Here are three ways to create and use secure passwords online.

How to Write Secure Code

Coding securely doesn't have to kill the joy of programming. In fact, learning how to code securely provides insights into languages and computing.

How to Code HTML Email

How to code an HTML email like the ones you open every day turns out to be an offbeat software coding challenge.

What is an SSL Certificate?

How to tell if a web page is secure is one of the most basic yet least obvious ways to protect your data online.

Where to Find Command Line Interface Software

One key computing skill is the ability to use command line interface (CLI) software to enter commands to control a computer. Here are some options.

Lua

Lua is a comparatively simple programming language used in a wide range of places, from digital TVs to video games to phone applications. It's also designed to be simple to use and lightweight.

Arrays

Here is how three programming languages handle a common problem: how do you organize and keep track of useful data?

Linux Command List for Command Line Interfaces

Some of the most common commands you'll need for a command line interface (CLI), in a Linux command list.

Computer science education cannot make anybody an expert programmer any more than studying brushes and pigment can make somebody an expert painter.

News Wire Stories for October 2013

Must read stories about computer science, software programming, and technology for September 2013.

Learn More Links for October 2013

Links from the bottom of all the October 2013 articles, collected in one place for you to print, share, or bookmark.