Tree pruning question...

Question

all. I'm facing the 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 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 letter, and how many do not send it out?"

Can anyone check my solution/ reasoning? I'm assuming it's a full 5-ary tree, pruning from the last level to get 10,000 senders, then calculating the total received.

Answer 1

The structure of the tree need not be the one described. And counting recipients by layers is not the most efficient or reliable way.

We have $10000$ people sending letters, each to $5$ "new" people. On the assumption, unfortunately not entirely safe, that any letter sent is received, there are $50000$ recipients.

Note that $9999$ of the people who send letters are letter recipients. The rest of the recipients do not send letters.

Answer 2

There is no reason to believe that all the people that fail to send the letter onward are contained in the last level. I think your tree is putting more details into the problem than is necessary.

10,000 people sent a total of 50,000 letters. 9,999 letters were received by these 10,000; the remaining 40,001 letters were received by other people.