A Phone Chain

Date: 10/28/98 at 22:29:04
From: Leah
Subject: Phone chain

I'm trying to figure out if there is a formula for this problem.  

There is a phone chain of people on a response team. When the first 
person gets a call, he calls two people, those two call two more, and 
each person calls two more. In all, 55 people need to be called. 
Figuring that each call takes one minute, estimate how long it will 
take to call 55 people. How long to call 100 people? How long to call 
n people?

We have already constructed a table showing how many people it takes 
to call 55 people, and how many people have been called in increments 
of 2 minutes. We have determined that in 2 minutes, 3 people have been 
called, in 4 minutes, 7 people have been called, in 6 minutes, 15 
people have been called, etc. The first person calls 2, they call 4, 
they call 8, they call 16, etc. Is there any kind of formula to use to 
figure out how long it will take to call 100 people, ot any number of 
people? Or is it just as easy to estimate from a chart if it is 
lengthened to cover the number of people who need to be called? 

Thank you very much for your help.

Date: 10/29/98 at 12:58:27
From: Doctor Rick
Subject: Re: Phone chain

Hi, Leah. This is very interesting! I will answer your question first, 
but then I will point out that the problem is a little trickier than 
it looks at first.

It is easy to find a pattern in the numbers if we start with your 
second list, the number of NEW people called every 2 minutes: 2, 4, 8, 
16, .... Each number in the list is twice the number right before it: 
4 = 2 * 2, 8 = 2 * 4, etc. You probably figured this out already: if 
each person calls 2 people, then the number of people called is twice 
as many as the number called two minutes ago. 

These numbers are the POWERS OF 2. The second number is 2 * 2, which 
is 2 squared or 2^2 (that's the way we write:

   2
  2

on the keyboard). The 3rd number is 2 * 2 * 2, which is 2^3, etc.

Now look at the total number of people called: 3, 7, 15, etc. Do you 
notice that each number in the first list is one less than the next 
number in the second list? This is the pattern we see:

  1 + 2             =  3 = 2^2 - 1
  1 + 2 + 2^2       =  7 = 2^3 - 1
  1 + 2 + 2^2 + 2^3 = 15 = 2^4 - 1
  etc.

You can see why this is true if you think about what happens, for 
instance, when you add 2^3 to 2^3 - 1.

Now let's take another look at the problem. I think what the problem 
says is a little different from what you thought, and this little 
difference changes the answer quite a bit.

You were thinking that each person calls 2 people in 2 minutes, and 
then after the 2 minutes, those 2 people each call 2 more people. But 
I don't think that is quite what will happen. The first person calls 
one person FIRST, taking 1 minute. Then while the first person makes a 
second phone call, the first person she called is ALREADY calling 
someone else! (Why wait a minute?) It will look like this:

                                         Calls per minute  Total calls
                                         ----------------  -----------
                          1                     1               1
               +---------------------+
               |                     |
               2                     |          1               2
       +---------------+             |
       |               |             |
       3               |             4          2               4
   +---------+         |        +---------+
   |         |         |        |         |
   5         |         6        7         |     3               7
 +-----+     |    +-------+   +---+       |
 |     |     |    |       |   |   |       |
 8     |     9   10       |  11   |      12     5               12

Person 1 calls person 2 first, then person 4, but in the meantime 
person 2 is already calling person 3. Do you see how it goes?

I have listed how many people are called each MINUTE (not every 2 
minutes). If you want to compare it with what you found, remember to 
take this difference into account.

See if you can figure out how the pattern continues. If you have heard 
of the Fibonacci numbers, you'll get the idea. Then you can keep 
building the list, adding up as you go until the sum of all the numbers 
in the list reaches 55.

Here is a place to look for information on Fibonacci numbers:

  http://mathforum.org/dr.math/faq/faq.golden.ratio.html   

- Doctor Rick, The Math Forum
  http://mathforum.org/dr.math/