QUESTION:
There are $22$ people in a party. Calvin, one of the participants of the party, shakes hands with $18$ friends forgetting about the other three, goes to the washroom to wash his hands, and returns to the party. Then he again shakes hands with $18$ friends, goes to the washroom, and returns to the party. He repeats this same pattern over and over.
Calvin sits down with some punch immediately after a final round of $18$ handshakes in which Calvin shakes hands with one final friend who he's randomly managed to neglect all the rest of the evening. Sipping his punch, Calvin realizes that the numbers of handshakes with each of the $21$ friends are all different. What is the minimum number of times he must return to the party, assuming that he always shakes hands with $18$ friends after every return?
Now, my answer to this question was incorrect and the correct answer given is as follows, I've bolded the questions I have about this answer. In general though, if anybody has any insights for grasping this answer that would be great:
If Calvin returns to the party $k$ times, he will have shaken hands $k+1$ times. Thus he will have done $16(k+1)$ handshakes in total.
Why $16$ in the expression $16(k+1)$? Would this not be $18$?
Let $X_1$ be the friend who was forgotten the least number of times. Similarly, let $X_2$ be the friend who has forgotten the second least number of times, ... , $X_{20}$ the friend forgotten second most number of times, and finally $X_{21}$ the friend forgotten the most number of times which is $k$ times.
Now, let $x_1,x_2,...,x_{20}$ be the number of times forgotten corresponding to $X_1,X_2,...,X_{20}$, respectively. Then the following holds:
Where does the 3 in the expression $3(k+1)$ come from? $$3(k+1)=x_1+x_2+x_3+\cdots+x_{20}+k\ge 0+1+2+\cdots+19+k$$
which reduces to $2k\ge 187$.
Therefore, Calvin must have returned to the party at least $94$ times.
Yes, it should be $18(k+1)$.
In each round of handshaking, Calvin omitted $3$ people. Thus, in $k+1$ rounds of handshaking he omitted $3(k+1)$ possible handshakes, $3$ in each round. We know that $x_1$ of those missing handshakes were with $X_1$, $x_2$ of them were with $X_2$, and so on, so that altogether there were $x_1+x_2+\ldots+x_{21}=x_1+x_2+\ldots+x_{20}+k$ missing handshakes. Thus, the two quantities must be equal:
$$3(k+1)=x_1+x_2+\ldots+x_{20}+k\;.$$