dabaobao wrote:
In how many ways can 10 different paintings be distributed between two collectors – Dave and Mona – if both collectors should get an even number of paintings? (All paintings should be given away.)
A) 128
B) 256
C) 420
D) 512
E) 1024
Official Solution
Credit: Veritas Prep
Paintings can be distributed in the following ways:
0, 10 – One person gets 0 paintings and the other gets 10
2, 8 – One person gets 2 paintings and the other gets 8
4, 6 – One person gets 4 paintings and the other gets 6
You will need to calculate each one of these ways and then add them. Note that the ‘Total – Opposite’ method does not work here because finding the number of ways in which each person gets odd number of paintings is equally daunting.
Case 1: 0, 10
One person gets 0 paintings and the other gets 10. This can be done in 2 ways – either Dave gets all the paintings or Mona gets them.
Case 2: 2, 8
One person gets 2 paintings and the other gets 8. Select 2 paintings out of 10 for Dave in 10C2 = 45 ways. Mona could also get the 2 selected paintings so total number of ways = 45*2 = 90 ways
Case 3: 4, 6
One person gets 4 paintings and the other gets 6. Select 4 paintings out of 10 for Dave in 10C4 = 210 ways. Mona could also get the 4 selected paintings so total number of ways = 210*2 = 420
Total number of ways such that each person gets even number of paintings = 2 + 90 + 420 = 512 ways
But 512 is 2^9 – in form, suspiciously close to 2^10 we used in question 2 above. Is there some logic which leads to the answer 2^(n-1)? There is!
You have 10 different paintings. Each painting can be given to one of the 2 people in 2 ways. You do that with 9 paintings in 2*2*2… = 2^9 ways. When you distribute 9 paintings, one person will have odd number of paintings and one will have even number of paintings (0 + 9 or 1 + 8 or 2 + 7 or 3 + 6 or 4 + 5).
The tenth painting needs to be given to the person who has the odd number of paintings so you give the tenth painting in only one way. This accounts for all cases in which both get even number of paintings.
Total ways = 2^9 * 1 = 512
ANSWER: D