How many subsets of (1; 2; 3; ... 14) have 15 as the sum of their largest and smallest elements in the subset?
There are seven possibilities for lowest and highest elements: 1 & 14; 2 & 13; ... ; and 7 & 8.
The number of subsets in each of these categories is just 2 raised to the power of the number of possible elements between the end values, to the total is 2^12 + 2^10 + ... + 2^0.
The binary representation of this is 1010101010101.
The evaluation can be done most easily by recognizing that this is also 1111111 in base 4, which is just 1/3 of 3333333, which in turn is 4^7-1.
So the answer is (4^7 - 1) / 3 = 5461.
|
|
Posted by Charlie
on 2010-05-16 12:45:42 |
solution (spoiler)
