Combinatorics and Counting Questions and Answers

Answer: A

The expression has 12 terms. In the binomial expansion of \((a+b)^{n}\) there are \(n+1\) terms, because the power of \(a\) runs from \(n\) down to 0, which gives \(n+1\) different values. Here \(a = x^{2}\), \(b = \frac{2}{x}\) and \(n = 11\), so \[ \text{number of terms} = 11 + 1 = 12 \] The number 11 is the power and not the count of terms, while 22 and 24 come from doubling the power or the count, which does not follow from the binomial theorem.

Answer: A

There are 512 such matrices.

Fill the top-left 3 × 3 block freely: \(2^{9} = 512\) ways. The last entry of each of the first three rows is then forced, to make that row's count of 1s even, and likewise the last entry of each of the first three columns.

The bottom-right corner is forced twice, once by the last row and once by the last column, but both conditions give the same value, because each equals the parity of the 1s in the 3 × 3 block. So every free choice extends to exactly one valid matrix, and the count is \(2^{(4-1)^{2}} = 512\).

1025, 1023 and 255 are not powers of 2, but the count must be a power of 2, since these matrices form a vector space over GF(2).

Answer: C

The answer is 2C(n, 2) + \(n^{2}\).

\[ \begin{aligned} C(2n, 2) &= \frac{2n(2n-1)}{2} = 2n^{2} - n \\ 2C(n, 2) + n^{2} &= n(n-1) + n^{2} = 2n^{2} - n \end{aligned} \]

A combinatorial reading gives the same thing: split 2n objects into two groups of n. A pair is either inside the first group, inside the second (2C(n, 2) ways together) or has one object from each group (\(n \times n = n^{2}\) ways).

The others do not match: 2C(2n, 1) = 4n, nC(n, 1) + 2n = \(n^{2} + 2n\), and C(n, 2) + \(2n^{2}\) = \(2.5n^{2} - 0.5n\). Trying n = 2 confirms it: C(4, 2) = 6 and 2C(2, 2) + 4 = 6.

Answer: C

The cart holds 21 units.

The person takes 1 unit of the first item, 2 of the second, and so on up to r units of the rth, so the total for n items is the sum of the first n natural numbers:

\[ \begin{aligned} 1 + 2 + \dots + n &= \frac{n(n+1)}{2} \\ &= \frac{6 \times 7}{2} = 21 \end{aligned} \]

6 counts only the items, not the units. 42 is \(n(n+1)\), forgetting to halve, and 14 matches no step of the sum.

Answer: C

At least \(n + 1\) people must be chosen.

Think of the \(n\) couples as \(n\) pigeonholes. With \(n + 1\) people chosen, two of them must belong to the same couple, by the pigeonhole principle, so a married couple is guaranteed.

With only \(n\) people this can fail: choose all \(n\) wives (or one person from each couple) and no couple appears. So \(n\), and certainly \(n - 1\), are not enough, and \(n + 2\) is more than necessary.

Answer: C

There are 26 such integers.

Count the numbers up to 100 divisible by 2, 3 or 5 using inclusion-exclusion:

\[ \begin{aligned} &50 + 33 + 20 \\ &- (16 + 10 + 6) + 3 = 74 \end{aligned} \]

(multiples of 2, 3, 5; then of 6, 10, 15; then of 30). So \(100 - 74 = 26\) numbers are divisible by none of them.

Check by Euler-type reasoning: in each block of 30 there are \(30(1/2)(2/3)(4/5) = 8\) such numbers, giving 24 up to 90, plus 91 and 97 between 91 and 100, a total of 26.