Permutations & Combinations Questions and Answers

Answer: C

The possible trajectory is (C).

The ant starts at the bottom-left corner and the target is the top-right corner, which is up and to the right. A step up or a step to the right along a grid line moves it closer to that corner, while a step down or to the left moves it away. So every allowed path is a staircase made only of up and right moves.

Path (C) goes up, right, up, right, so its distance to the target keeps falling. Path (A) ends with a step down, and path (B) also turns down after its last move right, so the distance grows on those steps. Path (D) is a closed loop that returns to P, which must include moves down and left.

Answer: D

There are 80 frabjous numbers.

The odd digits are 1, 3, 5, 7, 9. The first digit can be any of the 5. Each later digit must be odd and differ from the digit just before it, leaving 4 choices:

\[ 5 \times 4 \times 4 = 80 \]

Only adjacent digits must differ, so the first and third may be equal (as in 131). 125 = 5³ ignores the 'no two adjacent equal' rule, and 60 = 5 × 4 × 3 wrongly forbids repeats of non-adjacent digits as well.

Answer: A

F(5) is 8.

The last move onto stair N is either a single step from stair N - 1 or a double step from stair N - 2, so:

\[ F(N) = F(N-1) + F(N-2) \]

With F(1) = 1, F(2) = 2 and F(3) = 3, this gives F(4) = 3 + 2 = 5 and F(5) = 5 + 3 = 8, the Fibonacci numbers.

Listing by the number of double steps confirms it: no double step (1 way), one double step among four moves (4 ways), two double steps among three moves (3 ways), total 8. 5 is F(4), one stair short.

Answer: A

There are 729 such pairs.

Decide, element by element, where each of the six numbers goes when S is a subset of T. Each element has exactly three possibilities: it is in neither set, it is in T but not in S, or it is in both S and T. (It cannot be in S without being in T.) The choices are independent, so

\[ 3^{6} = 729 \]

728 leaves out one pair, such as the pair of two empty sets, which is a valid pair since the empty set is a subset of itself. 665 is \(729 - 64\), which drops the 64 pairs where S equals T; but 'S is a subset of T' includes equality. 664 makes both of those deductions.

Answer: B

The minimum number of steps is 5.

Each step is a chess knight's move (two squares one way, one square at right angles), and no step may end on a shaded square (P1, P4, Q3, R1, S2, S5, T3). One shortest route is

P2 → Q4 → R2 → P3 → R4 → P5

Every move is a legal knight's move and every square it ends on is unshaded.

Fewer steps are impossible. The target P5 can be entered only from R4, because its other knight neighbour, Q3, is shaded. Working outward from P2, the squares reachable in one step are Q4 and R3; in two steps R2, S3, Q1, Q5, S1, T2 and T4; in three steps P3, S4, T1, Q2, R5 and T5. R4 is first reached on the fourth step, so P5 needs a fifth. That rules out 4, and 6 or 7 are not minimal.

Answer: D

The minimum number of colors is 2.

The corners and edges of a cube form a bipartite graph: every edge joins corners whose positions differ in exactly one coordinate. Colour a, d, h and f with one colour and b, c, e and g with the other. Then every edge (a-b, b-d, d-c, c-a on top; e-h, h-g, g-f, f-e at the bottom; and the verticals a-e, b-h, d-g, c-f) joins two different colours.

At least two colours are needed, since any edge has two ends that must differ, so 2 is the minimum. 3, 4 and 8 colours are all possible but not minimal; 8 would give every corner its own colour.

Answer: A

There are 336 such numbers.

The units digit is fixed as 5. The other three places are filled from the remaining 8 digits (1 to 9 without 5), with no repetition:

\[ \begin{aligned} \text{thousands} \times \text{hundreds} \times \text{tens} &= 8 \times 7 \times 6 \\ &= 336 \end{aligned} \]

There is no zero among the digits, so no case of a leading zero needs removing.

504 is \(9 \times 8 \times 7\), which wrongly lets 5 be used again in the first three places. 1400 matches no correct count, and 'None of these' is wrong because 336 is offered.

Answer: A

90 three-digit even numbers can be formed.

With repetition allowed, count the choices for each place. The hundreds digit cannot be 0, so it has 5 choices (1-5). The tens digit can be any of the 6 digits. The units digit must be even, so it has 3 choices (0, 2, 4):

\[ 5 \times 6 \times 3 = 90 \]

216 = 6 × 6 × 6 counts all strings of three digits, including those starting with 0 and odd ones. 150 = 5 × 6 × 5 drops only the leading zero, and 75 does not correspond to a correct count.

Answer: A

The number of ways is \({}^{20}C_{8}\).

Choosing 8 balls from 20 is a selection in which order does not matter: picking ball 1 and then ball 2 gives the same group as picking ball 2 and then ball 1. Selections are counted by combinations:

\[ {}^{20}C_{8} = \frac{20!}{8!\,12!} \]

\({}^{20}P_{8}\) counts ordered arrangements of 8 balls, which overcounts each group by 8! orderings. 20! is the number of ways to arrange all 20 balls in a row, and 8! the number of ways to arrange 8 balls, so neither counts selections of 8 from 20.

Answer: A

There are 461 such numbers.

Write every number with at most five digits as five digits with leading zeros. We need the number of solutions of \(d_{1} + d_{2} + \dots + d_{5} \leq 6\) with each \(d_{i} \geq 0\) (no digit can exceed 6 here, so the limit of 9 never binds). Adding a slack variable makes this an equation in six unknowns summing to 6:

\[ \binom{6 + 5}{5} = \binom{11}{5} = 462 \]

This count includes 00000, which is not a natural number, so the answer is \(462 - 1 = 461\). Option 462 is the trap of forgetting to remove zero.