Question

A chain letter starts when a person sends a letter to five others. Each person who receives the letter either sends it to five other people who have never received it or does not send it to anyone. Suppose that \({\bf{10,000}}\) people send out the letter before the chain ends and that no one receives more than one letter. How many people receive the letters, and how many do not send it out?

Short answer

\({\bf{50,001}}\)people received the letter.

\({\bf{40,001}}\) did not send out the letter.

Step-by-step solution

Definition

A m-ary tree is a tree where every internal vertex has exactly m children.

Theorem 2: A full m-ary tree with i internal vertices contain \({\bf{n = mi + 1}}\) vertices.

Finding \({\bf{m}},{\bf{i}}\)

Since every person either sends the letter to five other people or does not send the letter, a vertex is either an internal vertex with 5 children or is a no internal vertex. This then implies that the tree forms a full 5-ary tree.

\(m = 5\)

Since \(10,000\) people send out the letter, there are \(10,000\) internal vertices.

\(i = 10,000\)

Using the theorem \(2\)

Using theorem 2, the number of vertices is:

\(n = mi + 1 = 5 \times 10,000 + 1 = 50,000 + 1 = 50,001\)

Thus, there are then \(50,001\) people who received the letter.

\(10,000\) of the \(50,001\) people send out a letter, thus \(50,001 - 10,000 = 40,001\) people did not send out the letter.