Problem of the Week Problem D and Solution Ring Ring

Problem

The POTW school wants to create a phone tree system to be used in the event of an emergency school closure. Using a phone tree system, the principal phones at most three other employees, each of whom phones at most three other employees, and so on, until all of the employees have been contacted.

If the POTW school has $$100$$ employees (including the principal) and uses a phone tree system where each employee phones $$0$$, $$1$$, $$2$$, or $$3$$ other employees, determine the maximum number of employees who do not need to make any phone calls in their phone tree system.

Solution

It is important to note that in order to minimize the number of callers, we need to maximize the number of calls made by those who do make calls.

Once the principal makes the initial three phone calls, four people (the principal and three others) have the information. There are $$100-4=96$$ people left to contact.

The next three people make three calls each, for a total of $$9$$ calls. Now $$13$$ people have the information and $$87$$ people still need to be contacted.

The next $$9$$ people make $$3$$ calls each, for a total of $$27$$ calls. Now $$40$$ people have the information and $$60$$ people still need to be contacted.

From here, we will present two approaches for figuring out how many people are needed to contact the remaining $$60$$ people.

• Approach 1: If the next $$27$$ people make $$3$$ calls each for a total of $$81$$ calls, this is $$81-60=21$$ calls too many. This means $$21\div 3=7$$ of the $$27$$ people do not need to make any calls. Thus, only $$27-7=20$$ more people need to make calls.

• Approach 2: In order to reach the final $$60$$ people, only $$60\div 3=20$$ more people need to make calls because each person phones $$3$$ people.

The total number of people required to make calls is therefore $$1+3+9+20=33$$.

Therefore, $$100-33=67$$ is the maximum number of employees who do not need to make any phone calls in the phone tree system.

A system like this is actually still very efficient at getting information to a large number of people. Close to one third of the employees need to make only $$3$$ calls each, while about two-thirds of the employees do not need to make any calls.