[Algebra · Practice Lab ⑨] 15 Ultra-Challenging Combinations Killers & 1:1 Diagnostic Twins (Equal-Size Partitions, Collinear Grid Traps, Anchored Functions & Modulo-3 Sets)

 

Algebra · Practice Lab ⑨ [Combinatorics Mastery]

15 Ultra-Challenging Combinations Killers & 1:1 Diagnostic Twins

Equal-Size Partitions & Distribution, Collinear Grid Geometric Counting, Anchored Functions & Modulo Residue Subsets

🎯 3 Multi-Layered Deduction Protocols for Combinations Killers
  • Decouple Anonymous Partitioning ($\mathbf{\div p!}$) from Named Allocation ($\mathbf{\times k!}$): When equal group sizes occur $p$ times, clear their permutation order first by dividing by $p!$. Reintroduce order only when allocating bundles to named targets.
  • Execute Collinear Geometry via "All-minus-Invalid with Restoration": For line counts, evaluate ${}_n\text{C}_2$, subtract all collinear combinations ${}_k\text{C}_2$, and append $\mathbf{+1}$ for each unique underlying line. For triangles, subtract all ${}_k\text{C}_3$ with zero restoration.
  • Partition Constrained Functions & Multiples via Boundary Slicing and Residue Classes: Handle conditions like $f(a)=b$ by partitioning inputs into independent left and right subsets. For sum-of-multiples problems, group elements into modulo residue classes ($3k, 3k+1, 3k+2$) before combining.

PART 1. Selection & Group Partitioning/Distribution (01~05)

[Challenge Problem 01] Selection with Pre-Assigned Inclusions & Exclusions
A 5-person committee is selected from 7 boys and 5 girls. Boy $A$ must be chosen, girl $B$ is excluded, and the committee must contain at least one boy and at least one girl. Find the number of valid committees.
💡 Yul's Pro-Tip: Boy $A$ is guaranteed a seat, and girl $B$ is excluded. The remaining pool has 6 boys and 4 girls (10 candidates) to fill $5 - 1 = 4$ seats. Since boy $A$ satisfies the "at least one boy" rule, the only invalid case is selecting zero girls (all 4 remaining seats filled by boys): ${}_{10}\text{C}_4 - {}_6\text{C}_4$.
View Solution & Answer (Click to Expand)
1. Candidates: 10 remaining (6 boys, 4 girls). Select 4 seats: ${}_{10}\text{C}_4 = 210$.
2. Disallowed Outcome: 4 boys chosen from 6: ${}_6\text{C}_4 = 15$.
3. Valid Selections: $210 - 15 = 195$.
Answer: 195
👯 [1:1 Diagnostic Twin 01]

From 6 boys and 6 girls, choose 4 representatives such that boy $A$ is included, boy $B$ is excluded, and at least one girl is included.

Check Twin Answer
Available candidates: 4 boys, 6 girls (10 total). Seats needed: 3.
Total selections: ${}_{10}\text{C}_3 = 120$. All-boy selections: ${}_4\text{C}_3 = 4$.
Valid selections: $120 - 4 = 116$.
Answer: 116
[Challenge Problem 02] Equal-Size Partitioning and Named Vehicle Assignment
In how many ways can 9 distinct students be partitioned into three groups of 3 and assigned to three distinct shuttle vans $A, B$, and $C$?
💡 Yul's Pro-Tip: All three groups are identical in size (3, 3, 3).
1. Partition into unlabelled groups: ${}_9\text{C}_3 \times {}_6\text{C}_3 \times {}_3\text{C}_3 \times \dfrac{1}{3!} = 280$.
2. Distribute to vans $A, B, C$: $280 \times 3! = 1680$. (The $3!$ factors cancel out).
View Solution & Answer (Click to Expand)
1. Anonymous Partitioning: $84 \times 20 \times 1 \times \dfrac{1}{6} = 280$.
2. Assigning to Vans: $280 \times 3! = 1680$.
Answer: 1680
👯 [1:1 Diagnostic Twin 02]

Partition 8 students into three unlabelled groups containing 2, 2, and 4 students.

Check Twin Answer
Two groups have size 2: ${}_8\text{C}_2 \times {}_6\text{C}_2 \times {}_4\text{C}_4 \times \dfrac{1}{2!} = 28 \times 15 \times 1 \times \dfrac{1}{2} = 210$.
Answer: 210
[Challenge Problem 03] Partitioning with Separation Constraints on Specific Elements
Seven students are partitioned into three groups of sizes 2, 2, and 3. How many partitions place students $A$ and $B$ into different groups?
💡 Yul's Pro-Tip: Use complementary counting: $\text{Total Partitions} - \text{Partitions Where } A \text{ and } B \text{ Share a Group}$.
Total: ${}_7\text{C}_2 \times {}_5\text{C}_2 \times {}_3\text{C}_3 \times \dfrac{1}{2!} = 105$.
Together in a size-2 group: ${}_5\text{C}_2 \times {}_3\text{C}_3 = 10$. Together in the size-3 group: ${}_5\text{C}_1 \times ({}_4\text{C}_2 \times \dfrac{1}{2!}) = 15$.
View Solution & Answer (Click to Expand)
1. Total Partitions: $21 \times 10 \times 1 \times \dfrac{1}{2} = 105$.
2. $A$ and $B$ Together: $10 + 15 = 25$.
3. $A$ and $B$ Separated: $105 - 25 = 80$.
Answer: 80
👯 [1:1 Diagnostic Twin 03]

Six students are partitioned into two groups of 3. In how many partitions do students $A$ and $B$ belong to different groups?

Check Twin Answer
Fix $A$ in Group 1 and $B$ in Group 2. Choose 2 of the remaining 4 students to join $A$: ${}_4\text{C}_2 = 6$.
Answer: 6
[Challenge Problem 04] Tournament Bracket Construction via Hierarchical Partitions
Eight soccer teams enter a single-elimination tournament. In how many structurally distinct ways can an 8-team bracket be filled?
💡 Yul's Pro-Tip: Tournament brackets are top-down set partitions:
1. Partition 8 into $(4, 4)$: ${}_8\text{C}_4 \times \dfrac{1}{2!} = 35$.
2. Partition each 4 into $(2, 2)$: ${}_4\text{C}_2 \times \dfrac{1}{2!} = 3$ for each branch.
Total: $35 \times 3 \times 3 = \mathbf{315}$.
View Solution & Answer (Click to Expand)
1. Semifinal halves: ${}_8\text{C}_4 \times \dfrac{1}{2!} = 35$.
2. Quarterfinal pairs per half: $3 \times 3 = 9$.
3. Total distinct brackets: $35 \times 9 = 315$.
Answer: 315
👯 [1:1 Diagnostic Twin 04]

Construct a 6-team bracket split into two halves of 3, where each 3-team group features 1 first-round bye.

Check Twin Answer
Halves: ${}_6\text{C}_3 \times \dfrac{1}{2!} = 10$. Bye selections: ${}_3\text{C}_1 \times {}_3\text{C}_1 = 9$. Total: $10 \times 9 = 90$.
Answer: 90
[Challenge Problem 05] Integer Partitions with Bounded Allocation Limits
Seven distinct books are distributed among students $A, B$, and $C$. Each student receives at least 1 book and at most 4 books. Find the total number of distribution ways.
💡 Yul's Pro-Tip: The allowed integer partitions of 7 into 3 parts bounded between 1 and 4 are $(4, 2, 1)$, $(3, 3, 1)$, and $(3, 2, 2)$. Partition each combination, then multiply by $3!$.
View Solution & Answer (Click to Expand)
1. $(4, 2, 1)$: ${}_7\text{C}_4 \times {}_3\text{C}_2 \times 3! = 35 \times 3 \times 6 = 630$.
2. $(3, 3, 1)$: ${}_7\text{C}_3 \times {}_4\text{C}_3 \times \dfrac{1}{2!} \times 3! = 35 \times 4 \times 3 = 420$.
3. $(3, 2, 2)$: ${}_7\text{C}_3 \times {}_4\text{C}_2 \times \dfrac{1}{2!} \times 3! = 35 \times 6 \times 3 = 630$.
Total: $630 + 420 + 630 = 1680$.
Answer: 1680
👯 [1:1 Diagnostic Twin 05]

Distribute 6 distinct books among 3 students such that everyone receives at least one book.

Check Twin Answer
Partitions: $(4, 1, 1) \implies 90$; $(3, 2, 1) \implies 360$; $(2, 2, 2) \implies 90$. Total: $540$.
Answer: 540

PART 2. Planar & Spatial Geometric Configurations (06~10)

[Challenge Problem 06] Triangles Formed by a 4x3 Grid of 12 Points
Twelve points form a rectangular $4 \times 3$ grid. How many distinct triangles have vertices selected from these 12 points?
💡 Yul's Pro-Tip: Total combinations: ${}_{12}\text{C}_3 = 220$. Subtract all collinear lines of 3 or more points:
- 3 horizontal rows of 4 points: $3 \times {}_4\text{C}_3 = 12$
- 4 vertical columns of 3 points: $4 \times {}_3\text{C}_3 = 4$
- 4 diagonal lines with slope $\pm 1$ of 3 points: $4 \times {}_3\text{C}_3 = 4$
Total invalid: $12 + 4 + 4 = 20$.
View Solution & Answer (Click to Expand)
1. All 3-point combinations: ${}_{12}\text{C}_3 = 220$.
2. Collinear combinations: $12 + 4 + 4 = 20$.
3. Valid triangles: $220 - 20 = 200$.
Answer: 200
👯 [1:1 Diagnostic Twin 06]

Find the number of triangles formed by a $3 \times 3$ grid of 9 points.

Check Twin Answer
${}_9\text{C}_3 = 84$. Collinear lines: 3 horizontal, 3 vertical, 2 diagonal (8 total).
Triangles: $84 - 8 = 76$.
Answer: 76
[Challenge Problem 07] Right and Obtuse Triangles from Regular 12-Gon Vertices
From the 12 equally spaced vertices of a regular 12-gon inscribed in a circle, find (1) the number of right triangles, and (2) the number of obtuse triangles that can be drawn.
💡 Yul's Pro-Tip: Thales's theorem rules right triangles: the hypotenuse must be a diameter (6 diameters $\times$ 10 other vertices $= \mathbf{60}$). An obtuse triangle has all three vertices confined to a semicircle: $12 \times {}_5\text{C}_2 = \mathbf{120}$.
View Solution & Answer (Click to Expand)
1. Right Triangles: 6 diameters $\times 10 = 60$.
2. Obtuse Triangles: 12 base vertices $\times {}_5\text{C}_2 = 120$.
Answer: (1) 60 / (2) 120
👯 [1:1 Diagnostic Twin 07]

Find the number of right triangles formed by 8 equally spaced points on a circle.

Check Twin Answer
4 diameters $\times 6 = 24$.
Answer: 24
[Challenge Problem 08] Maximum Interior Diagonal Intersections of a Convex Octagon
In a convex octagon where no three diagonals intersect at a common interior point, find the total number of interior diagonal intersection points.
💡 Yul's Pro-Tip: Every set of 4 convex vertices uniquely determines two intersecting diagonals. Thus, interior intersections have a 1:1 bijection with 4-vertex subsets: **${}_n\text{C}_4$**.
View Solution & Answer (Click to Expand)
${}_8\text{C}_4 = \dfrac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 70$.
Answer: 70
👯 [1:1 Diagnostic Twin 08]

Find the number of interior diagonal intersections in a convex heptagon (7 vertices).

Check Twin Answer
${}_7\text{C}_4 = {}_7\text{C}_3 = 35$.
Answer: 35
[Challenge Problem 09] Distinct Planes Determined by the 8 Vertices of a Cube
Find the total number of distinct planes that pass through at least three vertices of a cube.
💡 Yul's Pro-Tip: Count planes by category:
- 6 square face planes (4 vertices each)
- 6 diagonal rectangle cross-sections (4 vertices each)
- 8 corner equilateral triangle planes (3 vertices each)
Total: $6 + 6 + 8 = \mathbf{20}$.
View Solution & Answer (Click to Expand)
1. 4-vertex planes: 6 faces + 6 internal diagonals = 12 planes.
2. 3-vertex planes: 8 corner cuts = 8 planes.
3. Total distinct planes: $12 + 8 = 20$.
Answer: 20
👯 [1:1 Diagnostic Twin 09]

How many rectangles (including squares) have vertices selected from the 8 vertices of a cube?

Check Twin Answer
6 square faces + 6 diagonal cross-sectional rectangles = 12.
Answer: 12
[Challenge Problem 10] Non-Square Rectangles in a Parallel Grid
In a grid formed by 5 horizontal and 6 vertical equidistant lines ($4 \times 5$ square cells), find the number of non-square rectangles.
💡 Yul's Pro-Tip: $\text{Non-Square Rectangles} = \text{Total Rectangles} - \text{Squares}$.
Total: ${}_5\text{C}_2 \times {}_6\text{C}_2 = 150$.
Squares: $4 \times 5 + 3 \times 4 + 2 \times 3 + 1 \times 2 = 20 + 12 + 6 + 2 = 40$.
View Solution & Answer (Click to Expand)
Total: $10 \times 15 = 150$. Squares: 40.
Non-square: $150 - 40 = 110$.
Answer: 110
👯 [1:1 Diagnostic Twin 10]

Find the number of non-square rectangles in a grid of 4 horizontal and 5 vertical lines ($3 \times 4$ cells).

Check Twin Answer
Total: ${}_4\text{C}_2 \times {}_5\text{C}_2 = 60$. Squares: $12 + 6 + 2 = 20$. Non-square: $60 - 20 = 40$.
Answer: 40

PART 3. Constrained Functions & Modulo Residue Subsets (11~15)

[Challenge Problem 11] Counting Functions with Exactly Two Elements in the Range
For $X = \{1, 2, 3, 4, 5\}$ and $Y = \{1, 2, 3, 4\}$, find the number of functions $f : X \to Y$ whose range contains exactly two elements.
💡 Yul's Pro-Tip: Select 2 target elements from codomain $Y$ (${}_4\text{C}_2 = 6$). Map the 5 inputs to these 2 targets ($2^5 = 32$), subtracting the 2 constant functions where all inputs hit a single element: $6 \times (32 - 2) = \mathbf{180}$.
View Solution & Answer (Click to Expand)
1. Choose 2 range elements: ${}_4\text{C}_2 = 6$.
2. Surjective assignments: $2^5 - 2 = 30$.
3. Total: $6 \times 30 = 180$.
Answer: 180
👯 [1:1 Diagnostic Twin 11]

For $X = \{1, 2, 3, 4\}$ and $Y = \{a, b, c\}$, find the number of functions whose range contains exactly 2 elements.

Check Twin Answer
Choose 2: ${}_3\text{C}_2 = 3$. Surjective count: $2^4 - 2 = 14$. Total: $3 \times 14 = 42$.
Answer: 42
[Challenge Problem 12] Self-Inverting Bijections (Involutions: $f(f(x)) = x$)
For $X = \{1, 2, 3, 4, 5, 6\}$, find the number of bijections $f : X \to X$ such that $f(f(x)) = x$ for all $x \in X$.
💡 Yul's Pro-Tip: The condition $f(f(x)) = x$ requires every element to be either a fixed point ($f(a)=a$) or paired in a 2-cycle ($f(a)=b, f(b)=a$). Partition by the number of 2-cycles: 0, 1, 2, or 3.
View Solution & Answer (Click to Expand)
- Zero 2-cycles (Identity): 1
- One 2-cycle: ${}_6\text{C}_2 = 15$
- Two 2-cycles: ${}_6\text{C}_4 \times ({}_4\text{C}_2 \times \dfrac{1}{2!}) = 15 \times 3 = 45$
- Three 2-cycles: ${}_6\text{C}_2 \times {}_4\text{C}_2 \times \dfrac{1}{3!} = 15$
Total: $1 + 15 + 45 + 15 = 76$.
Answer: 76
👯 [1:1 Diagnostic Twin 12]

Find the number of involutions $f:X \to X$ on $X = \{1, 2, 3, 4\}$.

Check Twin Answer
0 pairs: 1. 1 pair: ${}_4\text{C}_2 = 6$. 2 pairs: 3. Total: $1 + 6 + 3 = 10$.
Answer: 10
[Challenge Problem 13] 3-Element Subsets with a Sum Divisible by 3
From $S = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$, how many 3-element subsets have an element sum that is divisible by 3?
💡 Yul's Pro-Tip: Classify elements by their residue modulo 3:
$R_0 = \{3, 6, 9\}$ (3 items); $R_1 = \{1, 4, 7, 10\}$ (4 items); $R_2 = \{2, 5, 8\}$ (3 items).
A sum of 3 numbers is a multiple of 3 if and only if: (1) all three are from the same residue class, or (2) exactly one is chosen from each class.
View Solution & Answer (Click to Expand)
1. From same residue class: ${}_3\text{C}_3 + {}_4\text{C}_3 + {}_3\text{C}_3 = 1 + 4 + 1 = 6$.
2. One from each class: ${}_3\text{C}_1 \times {}_4\text{C}_1 \times {}_3\text{C}_1 = 3 \times 4 \times 3 = 36$.
3. Total: $6 + 36 = 42$.
Answer: 42
👯 [1:1 Diagnostic Twin 13]

From $\{1, 2, \dots, 9\}$, how many 3-element subsets have a sum divisible by 3?

Check Twin Answer
Each residue set has 3 elements. Same set: $3 \times {}_3\text{C}_3 = 3$. One each: $3 \times 3 \times 3 = 27$. Total: $3 + 27 = 30$.
Answer: 30
[Challenge Problem 14] 4-Card Subsets Yielding an Even Product
Four cards are drawn simultaneously from a set of 12 cards numbered 1 through 12. In how many selections is the product of the four numbers even?
💡 Yul's Pro-Tip: "Product is even" means at least one card is even. Subtract the all-odd case: ${}_{12}\text{C}_4 - {}_6\text{C}_4 = 495 - 15 = \mathbf{480}$.
View Solution & Answer (Click to Expand)
1. Total combinations: ${}_{12}\text{C}_4 = 495$.
2. All-odd combinations: ${}_6\text{C}_4 = 15$.
3. Even product selections: $495 - 15 = 480$.
Answer: 480
👯 [1:1 Diagnostic Twin 14]

From integers 1 through 10, choose 3 numbers such that their product is even.

Check Twin Answer
Total: ${}_{10}\text{C}_3 = 120$. All-odd: ${}_5\text{C}_3 = 10$. Even product: $120 - 10 = 110$.
Answer: 110
[Challenge Problem 15] Grand Finale: Increasing Functions with a Fixed Range Gap
For $X = \{1, 2, 3, 4, 5, 6\}$ and $Y = \{1, 2, 3, 4, 5, 6, 7\}$, find the number of strictly increasing functions $f : X \to Y$ ($x_1 < x_2 \implies f(x_1) < f(x_2)$) such that $f(4) - f(2) = 3$.
💡 Yul's Pro-Tip: The difference condition gives four potential pairs for $(f(2), f(4))$: $(1, 4), (2, 5), (3, 6), (4, 7)$. Because $f(1) < f(2)$ and $f(4) < f(5) < f(6)$, check whether adequate codomain values remain on both sides. Notice that only $(2, 5)$ satisfies both boundary conditions.
View Solution & Answer (Click to Expand)
1. Pair $(1, 4)$: Needs $f(1) < 1$, impossible (0 ways).
2. Pair $(2, 5)$:
- $f(1) \in \{1\}$ (1 choice)
- $f(3) \in \{3, 4\}$ (${}_2\text{C}_1 = 2$ choices)
- $\{f(5), f(6)\} \subset \{6, 7\}$ (${}_2\text{C}_2 = 1$ choice)
Subtotal: $1 \times 2 \times 1 = 2$.
3. Pair $(3, 6)$: Needs $\{f(5), f(6)\} \subset \{7\}$, impossible.
4. Pair $(4, 7)$: Needs $\{f(5), f(6)\} > 7$, impossible.
Total valid functions: 2.
Answer: 2
👯 [1:1 Diagnostic Twin 15]

For $X = \{1, 2, 3, 4, 5\}$ and $Y = \{1, 2, \dots, 7\}$, find the number of strictly increasing functions such that $f(4) - f(2) = 4$.

Check Twin Answer
Possible pair: $(f(2), f(4)) = (2, 6)$.
$f(1) \in \{1\}$ (1 choice); $f(3) \in \{3, 4, 5\}$ (3 choices); $f(5) \in \{7\}$ (1 choice).
Total: $1 \times 3 \times 1 = 3$.
Answer: 3
🌿 Yul's Masterclass Perspective
"Dominating combination killers requires precise logical casework: knowing when to divide by $p!$, when to restore a shared collinear line, and how to slice constraints into independent subproblems."

With the completion of all 15 challenge patterns and their diagnostic twins, you have established a complete toolkit for high school combinatorics.

Comments