Slovenija 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.