We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
+0  
 
0
131
2
avatar

Hi. I am sort of confused on this question I have in my exponents workbook. My teacher is away and isn't answering the email I sent him, and I am on a tight schedule as of now with my second term coming up, and I need to get this done soon for my online math course. Anyways, if someone could maybe walk me through it that would be great! Here is the question. 

 

A telephone tree is used to send messages. The person at the top calls 2 people. Each person calls 2 more people. Suppose it takes 1 min to call someone. A message is relayed until the bottom row of the tree has 256 people. How long does this take? How do you know?

 

Thank you for reading this, and hopefully you can help me!

Dylan Gassner.

 Jan 30, 2019
 #1
avatar
0

So obviously this is about exponents so, 2^n = 256 and obviously, n is 8, so probably 8 minutes.

 Jan 30, 2019
 #2
avatar+7531 
+2

Consider small cases.

When there are only 2 layers of people (bottom row has 2 people),

1st minute: person on top calls first person

2nd minute: person on top calls second person.

So we need 2 minutes when there are 2 layers.

 

When there are 3 layers of people (bottom row has 4 people).

We number the people like 

1

2 3

4 5 6 7.

1st minute: 1 -> 2

2nd minute: 2 -> 4 and 1 -> 3

3rd minute: 2 -> 5 and 3 -> 6

4th minute: 3 -> 7

 

We need 4 minutes when there are 3 layers.

 

We can make a reliable guess, that if there are n layers, then it takes 2n-1 minutes. (and it's probably true!)

 

When there are 4 layers of people:

We number the people:

                1

         2             3

    4      5      6      7

8    9  10 11 12 13 14 15

1st minute: 1 -> 2

2nd minute: 2 -> 4 and 1 -> 3

3rd minute: 4 -> 8 and 2 -> 5 and 3 -> 6

4th minute: 3 -> 7 and 4 -> 9 and 5 -> 10 and 6 -> 12

5th minute: 5 -> 11 and 6 -> 13 and 7 -> 14

6th minute: 7 -> 15

 

Oh no, it wasn't true :(

We can guess that is 2(n-1) minutes instead.

 

When there are 5 layers of people:

I am lazy to number them.

1st minute: 1 -> 2

2nd minute: 2 -> 4 and 1 -> 3

3rd minute: 4 -> 8 and 2 -> 5 and 3 -> 6

4th minute: 3 -> 7 and 4 -> 9 and 5 -> 10 and 6 -> 12 and 8 -> 16

5th minute: 8 -> 17 and 9 -> 18 and 10 -> 20 and 5 -> 11 and 12 -> 24 and 6 -> 13 and 7 -> 14

6th minute: 9 -> 19 and 10 -> 21 and 11 -> 22 and 12 -> 25 and 13 -> 26 and 14 -> 28 and 7 -> 15

7th minute: 11 -> 23 and13 -> 27 and 14 -> 29 and 15 -> 30

8th minute: 15 -> 31

Now that's 8 minutes. The claim is probably correct. Why?

 

Notice how many calls are being made in each minute:

3 layers: 1, 2, 2, 1

4 layers: 1, 2, 3, 4, 3, 1

5 layers: 1, 2, 3, 5, 7, 4, 1

If we add 1, 2 to the left of the sequence, add 1 to the right of the sequence, then include the sum of each pair of consecutive elements of the previous row, then we get another row.

Example: 4th row: 1, 2, 3, 4, 3, 1

Array of sum of pair of consecutive elements: 3, 5, 7, 7, 4

Add 1,2 to the left: 1,2,3,5,7,7,4

Add 1 to the right: 1,2,3,5,7,7,4,1

We get the 5th row.

 

We do this to the n-th row, then we get the (n+1)-th row.

 

The number of elements of each row is the answer.

Notice how the number of elements of each row change:

Let Sn be the number of elements on the n-th row.

Array of sum of pair of consecutive elements has Sn-1 elements.

Adding 2 numbers to the left gives Sn+1 elements.

Adding 1 number to the right gives Sn+2 elements.

 

So there are Sn+2 elements on the (n+1)-th row.

 

That means, each row has 2 more elements than the previous row.

Or mathematically, we just developed a recursive formula: \(S_{n+1} = S_n + 2\).

 

Now, we found the answer to these questions:

How many calls are being made each minute, with varying number of rows of the tree?

How many minutes does it take for the message to relay through the tree, with varying number of rows of the tree?

 

Now we just find out how many rows are there in the tree if 256 people are at the bottom.

Let n be the number of rows.

2n-1 = 256

n = 9.

(Finally, some use of exponents cheeky)

 

So there are 9 rows. We just need to find S9, which is 2(9-1) = 16.

 

Therefore, it takes 16 minutes for the message to relay through the entire tree.

 

P.S.: This problem is tough! I thought it would be easy, then I realised there may be more than 1 call in each minute. So I really tried hard to develop the formulae and explain those to you. Please DO NOT just skip through the process, and try your best to understand it(because my English is bad haha).

It took me so much effort!

 Feb 7, 2019

8 Online Users

avatar