Problem 1004

Let $A, B$ and $C$ be any three residents of the city.

It is clear that it is possible for all of them to be friends with each other; it is also possible that one of them (say, $A$) is not friends with either $B$ or $C$, while $B$ and $C$ are friends with each other: in this case, for $A, B$, and $C$ to all become friends, it is sufficient for $A$ to "start a new life."

It is also easy to see that two other cases are impossible: when all three residents $A, B$, and $C$ are enemies with each other, and when one resident, for example, the same $A$, is friends with both $B$ and $C$, while they are enemies with each other.

The described structure of the "friendship relation" between any three individuals $A, B$, and $C$ proves that this relation can be described quite simply for the entire city: in the city, there are two groups of residents (two parties $\mathbf{M}$ and $\mathbf{N}$), such that all residents belong to either one or the other party (but never to both at the same time), and every two members of the same party are friends with each other, while residents belonging to different parties are necessarily enemies. Indeed, let us add to our three residents $A, B$, and $C$ of the city of Diversity another resident $D$; in this case, if $A$ and $B$ are friends with each other and $D$ is friends with at least one of them, then he is friends with the other as well - and, therefore, belongs to the party that includes both $A$ and $B$; if, however, $A$ and $B$ are enemies with each other, then $D$ is friends with only one of them (but is necessarily friends with one of them!). This reasoning ensures the possibility of dividing the quartet of residents $A, B, C$, and $D$ into two parties $\mathbf{M}$ and $\mathbf{N}$ (although one of these parties may be "empty": this will be the case if all residents $A, B, C$, and $D$ are friends with each other). Proceeding in the same way and further, i.e., sequentially adding one person to the already considered residents of the city, we will prove the possibility of dividing all $n$ residents of the city into two parties.

Now, proving the statement of the problem is no longer difficult. If all residents of the city are friends with each other, then there is nothing to prove; if, however, neither of the parties $\mathbf{M}$ and $\mathbf{N}$ is "empty," then we will suggest that each day one of the members of party $\mathbf{M}$ "starts a new life," i.e., simply transitions to party $\mathbf{N}$. If party $\mathbf{M}$ has $k$ people, then all residents of the city will be able to become friends in $k$ days.