Solution:

Consider a graph $G$ with $n$ vertices corresponding to the tourists and two vertices connected when they are familiar.

The first condition of the problem means that there is no triangle in $G$.

The second condition of the problem means that there is a cycle of odd length in the graph. Indeed, if all cycles are of even length, then the vertices can be partitioned into two groups such that there is no edge in any of them.

Let $A_{1}, A_{2}, \ldots, A_{k}$ be a cycle with minimal odd length in $G$. Since there is no triangle in $G$, and because of minimality, it follows that every vertex outside this cycle is connected with at most two vertices from the cycle. Hence the number of edges of the form $(X, A_{i}), X \neq A_{j}, j=1,2, \ldots, k$ does not exceed $2(n-k)$. Denote by $d(A_{i})$ the degree of the vertex $A_{i}$ and set $\delta= \min_{1 \leq i \leq k} d(A_{i})$. Obviously $\sum_{i=1}^{k} d(A_{i})=|E^{*}|+2k$, where $E^{*}$ is the set of edges $X A_{i}$. We have that

$$2(n-k) \geq |E^{*}| = \sum_{i=1}^{k} d(A_{i}) - 2k \geq k\delta - 2k$$

Hence $\delta \leq \frac{2n}{k}$ and $k \geq 5$ implies that $\delta \leq \frac{2n}{5}$.