Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The problem is as follows:

On day 1, a person will call two persons; these will, in turn, call other people on day 2; generally, if a person gets called on day n, they will call another set of people on day n + 1.

There are two kinds of people: sociable and unsociable. Sociable people always call 4 people; unsociables always call 2. Also consider that every person calls exactly one sociable person.

The problem then is to find how many people will call on the nth day. I have a solution for this but I think it is kind of artificial. I would like to see more solutions to this.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

Let's denote the numbers of sociable and unsociable callers on day $n$ by $s_n$ and $u_n$, respectively. On day $n$, there will be one sociable caller for every sociable or unsociable caller on day $n-1$, so $s_n=s_{n-1}+u_{n-1}$. There will also be $3$ unsociable callers for every sociable caller on day $n-1$, and one unsociable caller for every unsociable caller on day $n-1$, so $u_n=3s_{n-1}+u_{n-1}$. In matrix form,

$$\pmatrix{s_n\\u_n}=\pmatrix{1&1\\3&1}\pmatrix{s_{n-1}\\u_{n-1}}\;.$$

Now you just have to find the eigensystem of the matrix, decompose the initial state $s_1=0$, $u_1=1$ into its eigenvectors and multiply each eigenvector with the $(n-1)$-th power of the corresponding eigenvalue.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.