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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.