Problem 1730

Answer: $17$

Consider any participant $x$. He has shaken hands with $137$ other participants, say $y_1, y_2, \dots, y_{137}$ (collectively known as Group Y participants). Also, there are $1234 - 1 - 137 = 1096$ participants who have not shaken hands with $x$; let's call them $z_1, z_2, \dots, z_{1096}$ (collectively known as Group Z participants).

We count the number of times a Group Y participant has shaken hand with a Group Z participant. This can be done in two ways:

* Since no two participants in Group Y can shake hands (otherwise together with $x$ there will be three participants shaking hands with each other), every Group Y participant must have shaken hands with exactly $136$ participants in Group Z. The total number of such handshakes is thus equal to $137 \times 136$.

* On the other hand, every participant in Group Z (say $z$) must shake hands with exactly $k$ participants in Group Y, because $x$ and $z$ have not shaken hands implies there are exactly $k$ participants (who must be in Group Y) who have shaken hands with both $x$ and $z$. It follows that the total number of such handshakes is also equal to $1096k$.

From the above two ways of counting we obtain the equality $1096k = 137 \times 136$, which gives $k = 17$.