Q: How do we pair elements of a set X?

A: Use a function f:X -> X that has order two (that is f(f(x))=x).

Then each subset {x, f(x)} has either one, or two elements, and these subsets give a partition of X.
That is, if {x, f(x)} and {y, f(y)} are not disjoint, then they are identical. [This is where f²=Id is used.]

If {x, f(x)} has two elements (that is, x is not equal to f(x)), we can discard this pair.
So, the only elements of X that are left are those for which f(x)=x.

Thus, we reduce our question about the parity of X to a smaller subset of it,

Y={x in X | f(x)=x}

So, it remains to find a good function.

The set X consists of the nonempty subsets S of {1, 2, ..., n} that have an integer average.

An example of period-2 function is

S -> {1, 2, ..., n} \ S

(that is, associate to S its complement w.r.t. {1, 2, ..., n}).

However, this operation does not map X into itself!
(If S has an integer average, it does not follow that its complement has also an integer average.)