In how many ways can 10 different paintings be distributed

[BTGmoderatorDC]

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

OA D

Source: Veritas Prep

[Ian Stewart]

Half the time, the first collector gets less than 5 paintings, so 0, 2 or 4 paintings. We can choose those paintings in 10C0 + 10C2 + 10C4 ways, or

1 + (10)(9)/2! + (10)(9)(8)(7)/4! = 1 + 45 + 210 = 256

ways. The other half of the time, or another 256 times, the first collector gets more than 5 paintings, so doubling the result above, the answer is (2)(256) = 512.

There's a faster way, but it relies on a combinatorial identity you would never need on the GMAT (and this question is not the kind of question you see on the GMAT). The total number of even-sized subsets you can pick from a group is equal to the number of odd-sized subsets you can pick, so we can also count all of the ways to distribute the paintings, and divide by 2. Since we have 2 choices for each of the ten paintings, there are 2^10 ways to distribute them with no restrictions, and 2^10/2 = 2^9 = 512 ways if each collector must get an even number of paintings.