In a Senate of n Senators, itemized lists of all possible k member subcommittees were prepared.

Prove that for any k ≥ 3 the number of possible distinct subcommittees is even and the Senators are evenly divided between subcommittees with either an odd or even number of participants.

Why the constraint that k is at least 3?

Ady:

I have reread the problem, and I am more confused than ever. If you mean to ask only about subcommittees with k members (instead of all the k possible subcomittees), then the question does not make sense. If k is odd, then all the subcommittees under consideration have an odd number of members. If k is even, then all the subcommittees under consideration have an even number of members. For no k are Senators divided between odd-sized and even-sized subcommittees.

Clearly, what we have here is a failure to communicate