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
True and Fal;se (possible spoiler)
