The Hardest Problem in 7th Grade

The hardest problem in 7th grade

Before we get into the weeds about “what is math” from the perspective of an undergrad, lay person, and (hopefully) PhD I want to talk about one of my favorite challenge problems. This problem is useful as people usually reach for the highest level of math they know to attempt to solve it, but you only need 7th grade math to find a solution. I’ve heard stories of people asking this question in more advanced math classes and students attempting to use calculus to solve it.

Handshake Problem

This problem is from the USSR Olympiad Problem Book and reads as follows:

Every living person has shaken hands with a certain number of other persons. Prove that a count of the number of people who have shaken hands an odd number of times must yield an even number. Before you click to see the solution I’d suggest you give it a try. My hint is to start small.

Solution

Consider the total number of handshakes which have been completed at any moment. This must be an even number, since handshakes were participated in by two people, thus the total number of people is increased by two. The number of handshakes, however, is also the sum of handshakes made by each individual person. Since this sum is an even number, the count of people who have shaken hands an odd number of times must be even (otherwise, odd times odd would give an odd contribution to the total.