This is the question/riddle:

Five people who wear a red hat spread a gossip. In the first hour every one of them tells the gossip to one other person not yet wearing a red hat. The new insiders than immediately put on a red hat. This trend repeats itself with the following rule: Every person tells the gossip to one other person in the first hour he heard the gossip, and to nine other persons in the following hours. Nobody removes his hat, how many persons wear the red hat (heard the gossip) after n-hours? Hint: use generating functions

My question is, how would I turn a question like this into a generating functions? This is my attempt: $(1+x)(1+x)(1+x)(1+x)(1+x)+(1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9) \cdot n$

Five $(1 + x)$ representing the first five persons plus the nine new one's multiplied by $n$.

But I doubt this is correct.

What is the good generating function to solve this question, and how to get it?

  • $\begingroup$ n has to be limited because of population size. What is the largest n can be? $\endgroup$ Jan 27, 2018 at 21:55
  • $\begingroup$ A person hears the gossip. In the first hour he tells 1 person and in the second hour he tells 9 people and each succeding hour tells 9 more people. Is that the correct understanding of the problem? $\endgroup$ Jan 27, 2018 at 22:07
  • $\begingroup$ @WilliamElliot Yes, that's correct $\endgroup$
    – O'Niel
    Jan 28, 2018 at 14:16


You must log in to answer this question.