2
$\begingroup$

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.

Chain letter calcs

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Commented Apr 20, 2013 at 19:11
  • $\begingroup$ @Kundor "Practically the opposite?" :) $\endgroup$ Commented Apr 21, 2013 at 12:17
  • $\begingroup$ 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. $\endgroup$ Commented Apr 21, 2013 at 12:21

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I've got to learn to type faster... $\endgroup$
    – vadim123
    Commented Apr 19, 2013 at 21:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .