Permutations & Combinations: CAT previous year questions

Solution

Sandwich choices: $5 \times 4 \times 2 = 40$.

Sauces (none, one or two of 6): $1 + 6 + 15 = 22$.

Total $= 40 \times 22 = 880$.

Solution

Count functions from 6 elements onto 3 elements by inclusion–exclusion:

$3^6 - \binom{3}{1}2^6 + \binom{3}{2}1^6 = 729 - 192 + 3 = 540$.

Solution

Each digit appears 6 times in each place, so the sum $= 6 \times 1111 \times (a + b + c + d) = 6666S$.

$6666S = 153310 + n$ with $1 \leq n \leq 9$: $6666 \times 23 = 153318$, so $S = 23$, $n = 8$.

$a + b + c + d + n = 31$.

Solution

Let Q–R have $x$ paths and R–S have $y$ paths.

P to S: $3 \times 4 + 4y + 3xy = 62 \Rightarrow y(4 + 3x) = 50$.

Q to R: $x + 3 \times 4 + 4y = 27 \Rightarrow x + 4y = 15$.

Try $y = 2$: $x = 7$, and $2(4 + 21) = 50$ ✓.

Direct Q–R paths $= 7$.

Solution

1-digit: 9. 2-digit: $9 \times 9 = 81$. 3-digit up to 500: first digit 1–4, so $4 \times 9 \times 8 = 288$ (500 itself repeats 0).

Total $= 9 + 81 + 288 = 378$.

Solution

1-digit: 9. 2-digit: $9 \times 9 = 81$. 3-digit: $9 \times 9 \times 8 = 648$. (1000 repeats 0.)

Total $= 738$.

Solution

Each child gets an even, positive number: $2a_i$ with $a_i \geq 1$ and $\sum a_i = 10$.

Positive solutions $= \binom{9}{3} = 84$.

Solution

4-digit numbers above 2000: first digit 2–5: $4 \times 5 \times 4 \times 3 = 240$.

5-digit: $5 \times 5 \times 4 \times 3 \times 2 = 600$. 6-digit: $5 \times 5! = 600$.

Total $= 1440$.

Solution

Distinct arrangements of 1, 1, 2, 4: $\dfrac{4!}{2!} = 12$.

By symmetry each place has average digit $\dfrac{1 + 1 + 2 + 4}{4} = 2$.

Mean $= 2222$.

Solution

3 and 5 are always in. Add a non-empty subset of $\{1, 2, 4, 6, 7, 8\}$ that does not contain both 7 and 8.

Subsets without both 7 and 8: $2^6 - 2^4 = 48$. Remove the empty set: $47$.

Solution

Balloons: give each child 4 first, then share 3 freely: $\binom{5}{2} = 10$.

Pencils: give each child 1 first, then share 3 freely: $\binom{5}{2} = 10$.

Erasers: share 3 freely: $\binom{5}{2} = 10$.

Total $= 10 \times 10 \times 10 = 1000$.

Solution

All 4-digit numbers from $\{1, 2, 3\}$: $3^4 = 81$.

Remove those without a 2 ($2^4 = 16$) and without a 3 (16), and add back those with neither (1).

$81 - 32 + 1 = 50$.

Solution

Products 3, 4, 5 or 6 with non-zero digits:

3: $\{1, 1, 3\}$ (3 numbers). 4: $\{1, 1, 4\}$ (3), $\{1, 2, 2\}$ (3). 5: $\{1, 1, 5\}$ (3). 6: $\{1, 1, 6\}$ (3), $\{1, 2, 3\}$ (6).

Total $= 21$.

Solution

Count 4-digit numbers with distinct digits containing both 7 and 3.

Other two digits without 0: $\binom{7}{2} \times 4! = 504$. With 0: $7 \times (4! - 3!) = 126$. Total $= 630$.

In exactly half of these, 7 comes before 3: $315$.

Solution

3-digit numbers: 900. With all digits distinct: $9 \times 9 \times 8 = 648$.

At least one repeated digit $= 900 - 648 = 252$.