Нашел старый советский задачник и на первой же странице встретил такую вот задачку,
"Каждый из людей, когда-либо живших на земле, обменялся с другими определенным числом рукопожатий. Доказать, что число людей, обменявшихся нечетным числом рукопожатий, четно."