Let us define the simple, undirected graph $G$ so that the vertices of $G$ are the town's residents and the edges of $G$ are the friendships between the residents. Let $V(G)=\{v_{1}, v_{2}, \ldots, v_{n}\}$ denote the vertices of $G ; a_{i}$ is degree of $v_{i}$ for every $i$. Let $E(G)$ denote the edges of $G$. In this terminology, the problem asks us to describe the length $k$ of the shortest cycle in $G$. Let us count the walks of length 2 in $G$, that is, the ordered triples $(v_{i}, v_{j}, v_{l})$ of vertices with $v_{i} v_{j}, v_{j} v_{l} \in E(G)$ ( $i=l$ being allowed). For a given $j$ the number is obviously $a_{j}^{2}$, therefore the total number is $\sum_{i=1}^{n} a_{i}^{2}=n^{2}-n$. Now we show that there is an injection $f$ from the set of ordered pairs of distinct vertices to the set of these walks. For $v_{i} v_{j} \notin E(G)$, let $f(v_{i}, v_{j})=(v_{i}, v_{l}, v_{j})$ with arbitrary $l$ such that $v_{i} v_{l}, v_{l} v_{j} \in E(G)$. For $v_{i} v_{j} \in E(G)$, let $f(v_{i}, v_{j})=(v_{i}, v_{j}, v_{i}) . f$ is an injection since for $i \neq l,(v_{i}, v_{j}, v_{l})$ can only be the image of $(v_{i}, v_{l})$, and for $i=l$, it can only be the image of $(v_{i}, v_{j})$. Since the number of ordered pairs of distinct vertices is $n^{2}-n, \sum_{i=1}^{n} a_{i}^{2} \geq n^{2}-n$. Equality holds iff $f$ is surjective, that is, iff there is exactly one $l$ with $v_{i} v_{l}, v_{l} v_{j} \in E(G)$ for every $i, j$ with $v_{i} v_{j} \notin E(G)$ and there is no such $l$ for any $i, j$ with $v_{i} v_{j} \in E(G)$. In other words, iff $G$ contains neither $C_{3}$ nor $C_{4}$ (cycles of length 3 or 4 ), that is, $G$ is either a forest (a cycle-free graph) or the length of its shortest cycle is at least 5. It is easy to check that if every two vertices of a forest are connected by a path of length at most 2 , then the forest is a star (one vertex is connected to all others by an edge). But $G$ has $n$ vertices, and none of them has degree $n-1$. Hence $G$ is not forest, so it has cycles. On the other hand, if the length of a cycle $C$ of $G$ is at least 6 then it has two vertices such that both arcs of $C$ connecting them are longer than 2 . Hence there is a path connecting them that is shorter than both arcs. Replacing one of the arcs by this path, we have a closed walk shorter than $C$. Therefore length of the shortest cycle is 5 . Finally, we must note that there is at least one $G$ with the prescribed properties - e.g. the cycle $C_{5}$ itself satisfies the conditions. Thus 5 is the sole possible value of $k$.