Skip to content

Fastest possible spread of illness at a dinner

Question

At a banquet of 10001000 guests, one guest is ill and the rest are well. Every minute each guest chats with exactly one other guest, and repeat conversations are allowed. Whenever a well guest chats with an ill guest, the well guest becomes ill and stays ill. What is the shortest possible time, in minutes, before all 10001000 guests are ill?

Short answer

10. Each ill guest can infect at most one new person per minute, so the number ill can at most double each minute: after nn minutes at most 2n2^n are ill. Since 29=512<1000≤1024=2102^9=512<1000\le1024=2^{10}, ten minutes is the minimum, and perfect pairing achieves it.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question