, 2008

Consider an arbitrary villager $a$. Let $A$ denote the set of all villagers who know $a$ and let $B$ contain all the rest. There are $3k + 6$ villagers in $A$ and $9k - 7$ villagers in $B$. Let $x$ be a villager from $a$. The villagers who know $a$ as well as $x$ form a subset of $A$. Let $n$ be the number of villagers in $A$ who know $x$. Then $3k + 5 - n$ villagers from $B$ know $x$. Let $y$ be any villager from $B$. Those villagers who know both $a$ and $y$ also form a subset of $A$ and there are $n$ of them.

Now, let us count the number of acquaintances amongst the villagers in $A$ and villagers in $B$. There are $3k + 6$ villagers in $A$ and each of them knows $3k + 5 - n$ villagers from $B$. On the other hand there are $9k - 7$ villagers in $B$ and each knows $n$ villagers from $A$. So,
$$(3k + 6)(3k + 5 - n) = (9k - 7)n.$$
We can see right away that $n$ is divisible by 3, so we can write $n = 3m$. Thus,
$$m = \frac{3k^2 + 11k + 10}{12k - 1}.$$
For $m$ to be a positive integer we must have
$$4m = k + 3 + \frac{9k + 43}{12k - 1}.$$
Hence, $\frac{9k+43}{12k-1}$ is an integer, which implies that $4 \cdot \frac{9k+43}{12k-1} = 3 + \frac{175}{12k-1}$ is an integer as well. So, $12k - 1$ is a divisor of 175 and since $12k - 1 \ge 1$, it can only be equal to 25, 35 or 175. We find only one integer solution, $k = 3$. It is easy to see that in this case we have $n = 6$, which is an integer and we conclude that there are 36 people in the village.