In the city there was one person infected with a virus. Every day every sick person is visited by all his healthy friends, they become infected with the virus and get sick the next day. And all patients recover the next day and are immune to the virus for exactly one day.
$\cdot$Prove that the epidemic will end sometime
I don't really know how to solve this.
On
Consider the graph with the people as vertices and two vertices are connected by an edge if they are friends. Define the distance between two people to be the length of the shortest path connecting them. We refer to the people who are at a distance $k$ from the initial infected person $k-lavil$. I claim that on the $k$th day, the $k-lavil$ people are the only ones sick. If you know about Breadth first spanning tree, you are done. If not, read on.
We prove this by induction on $k$. The base case is trivial. Suppose on the $(k-1)^{th}$ day, the $(k-1)-lavil $ are the only ones sick. We will prove the proposition for $k$. As every $k-lavil$ person is adjacent to at least one $(k-1)-lavil$ person, all $k-lavil$ persons are sick on the $k^{th}$ day. Note that $(k-1)-lavil$ person is adjacent to somebody, his $lavil$ can either be $(k-2)$, $(k-1)$ or $k$, by the definition of distance. As $(k-2)-lavil$ people were sick on the $(k-2)^{th}$ day, they are immune on the $k-1^{th}$ day and thus are not sick on the $k^{th}$ day. Therefore, our claim is proved. As the number of people are finite(why?), the distance is bounded by the total number of people-1. Therefore, on the $(\text{total number of people})^{th}$ day, no one is sick and we are done.
Consider the friendship graph of the city, with an edge between friends. On day $n$, exactly those people get infected whose shortest path in this graph to the original source has length $n$.
You can prove this by induction. It’s true on day $1$. If it’s true on day $n$, then the people at distance $n$ who were infected on day $n$ are sick on day $n+1$. They can’t infect the people at distance $n-1$ because those are immune. They can’t infect people at a distance less than $n-1$ because an edge to them would form a shorter path. They also can’t infect people at a distance greater than $n+1$ because an edge to them would form a shorter path. So the only ones they can infect are the people at distance $n+1$, and those are indeed all infected because they necessarily have friends at distance $n$.
Note that none of this required coding. All it required was to draw a small example of a friendship network and play around with it and notice how the virus keeps spreading further away from the source. I write “play around” because that’s the most important part of learning. Reading this answer may give you some ideas how problems can be solved, but deeper insight usually comes from playing around with the problems yourself and getting a feel for what happens.