8
$\begingroup$

There is a group of people, some of whom are friends with one another (all friendships are mutual). Then one day, one of them gets sick. The sickness obeys the following rules:

  • On day 1, one person is sick with the virus, and nobody has immunity.

  • Illness lasts exactly one day.

  • Next day the recovered patient has immunity for a day.

  • If a person is sick, all of his friends who are not sick that day go to visit him in bed. They get sick next day, unless they were immune when they visited him.

Prove that the pandemics will end in a finite amount of time.

(No, this disease is not COVID. Call it mathitis)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\begingroup$

Suppose person 1 is sick on day 1. We can show that after recovering they won't fall sick again.
For person 1 to be sick again, they need to be not immune when any of their friends are sick. But all of their friends fall sick the very next day while person 1 is immune.
Using the same argument, we can show that the friends of person 1 won't fall sick again after recovering.
As every person falls sick atmost once so the process must be finitely long.

Considering a graph where friendships are undirected edges, then:
On day 1 only person 1 falls sick.
On day 2 all the people at a shortest distance of 1 from person 1 fall sick.
On day n all the people at a shortest distance of n-1 from person 1 fall sick.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I’m not sure I follow your reasoning. One of your friends may be friends with someone else that you’re not friends with. On day 2 when your friend is sick they’ll be visited by that other person. This may go around in a circle until one of your friends becomes sick from a person you don’t know, when you go visit your friend you will become sick again. $\endgroup$
    – Amorydai
    Jan 7 at 18:52
  • 2
    $\begingroup$ @Amorydai Cycles are accounted for because if there is a back-edge then the shortest distance to the source is much less and they will be infected much before. The entire graph is traversed in a breadth first search manner. $\endgroup$
    – Manish Kundu
    Jan 7 at 19:15
  • 3
    $\begingroup$ Consider grouping all the friends based on the distance from source and then it will be easier to observe how the process works. $\endgroup$
    – Manish Kundu
    Jan 7 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.