# Tree pruning 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.

• In order to have 10000 people send the letter, you need 6094 people in level 7 to send (along with the 3906 who have sent from higher levels,) practically the opposite of your conclusion. This yields the numbers given in the answers. Commented Apr 20, 2013 at 19:11
• @Kundor "Practically the opposite?" :) Commented Apr 21, 2013 at 12:17
• I meant in that you took $19530-10000$, rather than $10000-3906$. Yeah, I'm not really sure why I thought that was some kind of opposite. Commented Apr 21, 2013 at 12:21

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.