12
$\begingroup$

I was recently in an interview and got asked an interesting problem which I want to know the answer to.

Suppose we're in a party with $n$ people. At minute $t=0$, there is $1$ person who has a contagious disease that is transferable by shaking hands. Every minute, every person in the party shakes hands with someone they haven't shook hands with yet randomly (i.e. if there are $k$ people he/she hasn't shaken hands with, then probability of shaking hands with any of them is $\frac{1}{k}$). Let $S(t)$ be the random variables of the number of people who have disease at minute $t$. What is $S(t), \mathbb{E}(S)$?

A followup question was if you could choose who shakes hands with who, how can you maximize $t^*$, the minute where everyone is infected.

In the interview, it was $n=1000$, and I did some approximations manually and reached $664$ for the first problem until minute $t=10$. Couldn't really answer the followup question that well. I am not even sure if this is a known probability distribution or not. Would appreciate an answer, thanks!

$\endgroup$
  • 1
    $\begingroup$ Just a curiosity! For which subject was this interview taken? $\endgroup$ – Archis Welankar Oct 24 '18 at 3:59
  • 1
    $\begingroup$ the requirement that two people never shake hands in two different rounds, makes this a rather subtle problem IMHO. basically every round the hand-shakes have to form a matching consisting of $n/2$ edges, and the $n-1$ matchings (corresponding to the $n-1$ rounds) have to be completely disjoint (i.e. partition of the complete graph). it is not clear to me -- and in fact i would think it's not possible -- to guarantee that if at time $t$ person X has $k$ people he/she hasn't shaken hands with then prob of shaking hands with any of them is $1/k$. $\endgroup$ – antkam Oct 24 '18 at 18:22
  • 1
    $\begingroup$ e.g. just before the 2nd-to-last round, we cannot be left with a scenario where 3 people have not shaken with each other but have shaken with everyone else, because in this scenario no matching can be found for the 2nd-to-last round. and to AVOID being in this scenario, the previous round(s) probabilities cannot be i.i.d. but must instead somehow contrive to avoid this scenario... OTOH if we allow two people to shake again in subsequent rounds, the problem can be approximated much easier. $\endgroup$ – antkam Oct 24 '18 at 18:26
  • 2
    $\begingroup$ @antkam I see what you mean. If $n=6$ and we have the people $(A,B,C,D,E,F)$ who at the first round shake hands with $(B,A,D,C,F,E)$ and in the second round shake hands with $(C,D,A,B,?,?)$, we have a problem finding people for $E$ and $F$ to shake hands with. So the premise that people randomly shake hands among those whose hand they have not yet shaken, is not possible. $\endgroup$ – Jens Oct 29 '18 at 18:25
  • 1
    $\begingroup$ Yes, it is not even clear how you sample a shaking schedule uniformly, which makes it quite a problem. $\endgroup$ – pepster Oct 30 '18 at 1:08
5
+150
$\begingroup$

Here is a strategy for the follow up question, I don't know if it is the optimal strategy. Following the strategy, for $n=d_1d_2$ with $d_1$ even, after $(d_1-1)(d_2-1)=n-d_1-d_2+1$ rounds of hand shaking, there are still $d_1$ uninfected people. Moreover, if $d_2$ is also even, say $d_2=2k$, then after $n-k-d_1$ rounds of hand shaking there are still $d_1$ healthy people.

For this consider first a slight variation of the original problem: Every person can shake hands with himself (only once since repetition is not allowed). Then, if there are $d_2$ people, at the round number $k$ the $j$th person shakes hand with the person $f_k(j)$, where $$ f_k(j)=\left\{\begin{array}{cc} k+1-j & if\ j\le k \\ d_2+k+1-j & if\ j>k . \end{array}\right. $$ If the first infected person is person number one, then after $k$ rounds there are $k$ infected people (note that in the first round the infected person shakes hands with himself). In particular, after $d_2-1$ rounds there is still one disease free person: person number $d_2$. Note also that if $d_2$ is even then at each even round ($k=2k_1$) no one shakes his own hand.

Now assume again that shaking hand with oneself is not allowed and assume $n=d_1 d_2$ with $d_1$ even. Form $d_2$ groups with $d_1$ persons in each group, and with the first infected person in the first group. Now we consider $d_2-1$ (group) rounds, where in the $k$th round the group number $j$ meets group number $f_k(j)$. A meeting of two groups means $d_1$ individual rounds of hand shaking, but if a group meets itself, there are only $d_1-1$ rounds (a group can meet with itself, but not an individual). In particular, this means that if $f_k(j)=j$ for some $j$, then in that round there are only $d_1-1$ rounds of hand shaking even for the meetings of two different groups, so their meeting is not "complete".

Now after $d_2-1$ group rounds, there is still one group (the group number $d_2$) that hasn't met an infected group. Since each group round consists of at least $d_1-1$ rounds of hand shaking, we obtain that after $(d_1-1)(d_2-1)$ rounds of hand shaking there are still $d_1$ healthy people.

Moreover, if $d_2=2k$, there are $k$ rounds of length $d_1-1$ (with at least one group meeting itself) and $k-1$ group rounds of length $d_1$ (with no group meeting itself). So after $$ k(d_1-1)+d_1(k-1)=n-k-d_1 $$ rounds there are still $d_1$ people healthy, as desired.

Note that for a group meeting itself it is known that there is a hand shaking schedule such that every possible pair has shaken hands after $d_1-1$ rounds.

Note also that when two different groups meet in a group round of length $d_1-1$, one of the possible hand shakes for each person will not be performed, so we don't know if the given schedule can be completed to a complete schedule of $n-1$ rounds with every possible hand shake.

$\bf Example$: Take $n=16$. Then $d_1=d_2=4$ and we form the groups $\{1,2,3,4\}$, $\{5,6,7,8\}$, $\{9,10,11,12\}$ and $\{13,14,15,16\}$.

In the first group round there are three rounds of hand shaking: In $\{1,2,3,4\}$ everyone shakes hands inside the group, the same for $\{9,10,11,12\}$. The persons in $\{5,6,7,8\}$ shake hands with (nearly) all people in $\{13,14,15,16\}$ (3 out of 4 possible rounds). So, after 3 rounds of hand shaking (one group round), one group is infected (4 people).

In the second group round (four individual rounds) the persons in $\{1,2,3,4\}$ shake hands with all people in $\{5,6,7,8\}$ and the persons in $\{9,10,11,12\}$ shake hands with all people in $\{13,14,15,16\}$. So, after 7 rounds of hand shaking (two group rounds), two groups are infected (8 people).

In the third group round there are three rounds of hand shaking: In $\{5,6,7,8\}$ everyone shakes hands inside the group, the same for $\{13,14,15,16\}$. The persons in $\{1,2,3,4\}$ shake hands with (nearly) all people in $\{9,10,11,12\}$ (3 out of 4 possible rounds). So, after $10=n-d_1-\frac{d_2}{2}$ rounds of hand shaking (three group rounds), three groups are infected (12 people) and $4=d_1$ people are still healthy: $\{13,14,15,16\}$.

$\bf Note:$

It is important to understand the function $f_k$. Here are the values for $d_2=4$ and for $d_2=7$.enter image description here

$\endgroup$
  • $\begingroup$ Finally understood your system. Only after re-reading your last paragraph did it become clear to me that in group rounds where at least one group meets itself, handshaking stops for all group meetings, including different group meetings, after $d_1-1$ handskaking rounds. You might want to mention that earlier in your description. Nice job, though! $\endgroup$ – Jens Nov 2 '18 at 23:07
  • $\begingroup$ Thank you for your comments @Jens. I have added the required example and some details. $\endgroup$ – san Nov 3 '18 at 2:29
3
$\begingroup$

Some thoughts on the main question.

At best, the question is vague and at worst, it is impossible. An immediate interpretation of the question is that at every minute, everyone randomly selects a person to shake hands with, that they have not yet shaken hands with. But this would mean very few (if any) would actually pair up. What do we do the rest? Or when a person has been selected by more than one person?

An alternative interpretation (stretching a bit) is that at every minute, a list of all allowed handshake scenarios is made and that this list has equally many instances of person $p_i$ shaking hands with not-formerly-shaken person $p_j$ as it has of person $p_i$ shaking the hands of any other not-formerly-shaken person $p_k$. A random selection of one of these instances would then fulfill the setup that "if there are $k$ people he/she hasn't shaken hands with, then probability of shaking hands with any of them is $\frac{1}{k}$".

But handshake scenarios do not in general fulfill the bolded part above. The only instances I found where this is true is with $n=2$ or $n=4$. For $n=6$, for example, we have the following list of scenarios at $t=0$:

enter image description here

We see that any of the $15$ scenarios gives an equal probability for everyone of shaking hands with anyone not-formerly-shaken. Let's randomly select a scenario (green) and then exclude those scenarios which are no longer possible (blue):

enter image description here

We see that the remaining scenarios still fulfill the bolded part above. I.e. the remaining choices are equally distributed for everyone. So far, so good. Let's then select another scenario:

enter image description here

We now see that the remaining scenarios are not evenly distributed. In all scenarios, one person is twice as likely to be selected as the others.

The above is also true for $n=8$, which breaks down at the first round. I suspect it is true for all $n \gt 4$, though I can't prove it.

In short, the main question was very vague and probably the best response would have been to ask a lot of clarifying questions.

$\endgroup$
  • $\begingroup$ Thank you! I wish I can Accept both answers, they're both amazing, thank you for so much insights! $\endgroup$ – AspiringMat Nov 3 '18 at 18:23
  • $\begingroup$ @AspiringMat You're welcome. I would also have chosen the answer from san. :-) $\endgroup$ – Jens Nov 3 '18 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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