Ответ:

Рассмотрим сумму числа рукопожатий, сделанных всеми депутатами. По условию каждое слагаемое нечётно.

Каждое рукопожатие учитывается дважды: по одному разу для каждого из двух пожавших руки. Поэтому сумма равна удвоенному общему числу рукопожатий и, следовательно, чётна.

Сумма нечётных чисел чётна только тогда, когда нечётных слагаемых чётное число. Значит, депутатов чётное число.

Доказано.