There are 15 slates placed in a line. In how many ways can you mark 5 of these slates so that there are an odd number of slates between any two of the slates you marked?

Level: Senior

Solution 1.

Since the number of slates before the first marked slates is either odd or even, and the number of slates between any two marked slates is odd, so the number of slates after the last marked slate is odd or even, respectively. Therefore the slates can be depicted as either
(i) _*_*_*_*_*_*_*_
or
(ii) *_*_*_*_*_*_*_*,
where _ represents an unmarked slate and * represents either a marked or an unmarked slate. Since there are 5 marked slates, so exactly 5 of the * is a marked slate in each case. It follows that the number of ways to mark the line of slates with the prescribed condition are (i) 7C5 = 21 and (ii) 8C5 = 56, or 21+56 = 77 combined.

Solution 2.

Let the 5 marked slates divide the remaining 10 slates into groups of x, 2a+1, 2b+1, 2c+1, 2d+1, and y slates, where x, y, a, b, c, d are nonnegative integers. We are seeking the number of number of nonnegative integral solutions to the equation
x+y+2a+2b+2c+2d+4 = 10,
(1) 2(a+b+c+d) = 6-(x+y).
Consider the following cases.
(i) If x+y = 0, then a+b+c+d = 3. There is 1 solution (x, y) and 4+4*3+4 = 20 solutions (a, b, c, d). Therefore there are 1*20 = 20 solutions to (1).
(ii) If x+y = 2, then a+b+c+d = 2. There are 3 solutions (x, y) and 4C2+4 = 10 solutions (a, b, c, d). Therefore there are 3*10 = 30 solutions to (1).
(iii) If x+y = 4, then a+b+c+d = 1. There are 5 solutions (x, y) and 4 solutions (a, b, c, d). Therefore there are 5*4 = 20 solutions to (1).
(iv) If x+y = 6, then a+b+c+d = 0. There are 7 solutions (x, y) and 1 solution (a, b, c, d). Therefore there are 7*1 = 7 solutions to (1).
In all, there are 20+30+20+7 = 77 solutions to (1).