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?

Let's say that a subcommittee must have at least one senator (obviously), and cannot have all n senators. This can be disputed, but in order for Ady's first assertion to be true, a committee of the whole cannot be a subcommittee.

**TRUE**

Then the total number of subcommittees is 2^k - 2, which is clearly even for all k. This formula is arrived at by forming each subcommittee one at a time, and considering each senator to be either on or off the committee. There are 2^k different sets of choices, after which we exclude the empty and the full subcommittee.

More simply, we can prove it without a formula. For every subcommittee, there is a corresponding subcommittee of senators excluded from the first committee. So there must be an even number of subcommittees.

**FALSE**

The number of senators are not always evenly divided between even and odd committees. Consider n = 3. The subcommittees are then {a},{b},{c},{a,b},{a,c} and {b,c}. Any individual senator is on 2 even-sized committees and 1 odd-sized committee. In total, the even-sized committees have 6 members and the odd-sized committees only 3.

Did Ady mean us to prove that the number of succommittees are evenly split between even and odd? That is clearly the case if n is odd. I will wait clarification before attempting a proof for all n >= 3.

**TRUE**

Whateve the second assertion is, it cannot be true for n = 2, because there are only two subcommitees, {a} and {b}, both odd-sized.

*Edited on ***May 22, 2022, 2:28 pm**