1
$\begingroup$

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.

1 Answers 1

5

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.