Associated Topics || Dr. Math Home || Search Dr. Math

### Steps and Footprints

```
Date: 5/31/96 at 8:37:10
From: Anonymous
Subject: Down the staircase

I've tried to solve this problem by logic and doing a drawing to see
it more clearly.  I haven't had any success.

Four friends race side by side down a dusty staircase.  Peter goes
down two steps at a time, Bruce three steps at a time, Jessica four
steps at a time, and Wiz five steps at a time. If the only steps with
footprints from all four friends are at the top and bottom, how many
steps have just one person's foot prints?
```

```
Date: 5/31/96 at 16:4:34
From: Doctor Darrin
Subject: Re: Down the staircase

Let's call the top step step 0, and number the steps counting
downward. Then Peter will step on all the even-numbered steps, Bruce
will step on all the steps which are numbered with a multiple of
three, Jessica on all the multiples of four, and Wiz on all the steps
that are multiples of 5.

First we will see how many steps there are.  Since all four people
will step on the last step, the number of the last step must be a
multiple of 2, 3, 4, and 5.  3*4*5 = 60 is the smallest such number
(the least common multiple of 2, 3, 4, and 5), so the last step is
number 60.

Now we will count the steps that only Peter steps on.  These will
be given by even numbers which are not multiples of 3, 4, or 5.  We
can write such a number as 2*n with n between 1 and 30, and n
relatively prime to 30 (so that n is not divisible by 2, 3, or 5).
There are 8 numbers below thirty relatively prime to 30, so Peter
steps on eight steps that nobody else steps on.  (We could also just
count which of the even-numbered steps have numbers not divisible by
3, 4, or 5.  They are steps 2, 14, 22, 26, 34, 38, 46, 58, and there
are 8 of them.)

Now let's count the steps that only Bruce steps on.  He steps on
multiples of three which are not multiples of 2, 4, or 5.  The steps
he steps on are given by 3*n where n is between 1 and 20 and n is
relatively prime to 20 (so that n is not divisible by 2, 4, or 5).
There are 8 such numbers, so he steps on 8 steps that nobody else
steps on. (Steps 3, 9, 21, 27, 33, 39, 51, 57).

Every step that Jessica steps on is an even-numbered step that Bruce
also steps on, so Jessica steps on 0 steps that nobody else steps on.

Wiz steps on steps numbered 5*n with n between 1 and 12, and n
relatively prime to 12 (so that n is not divisible by 2, 3, or 4).
There are 4 numbers relatively prime  to twelve below twelve, so Bruce
steps on 4 steps that nobody else steps on.

Thus there are 20 steps that are stepped on by only one person.
Notice that we counted the numbers relatively prime to a certain
number and less than the number several times.  There is a special
name for this - it is called the Euler phi function.  Basically
phi(n) = the number of numbers between 1 and n relatively prime to n.
It is a very important function in number theory (and in solving fun
number problems like this one).

-Doctor Darrin,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
Middle School Logic

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search