Advanced Combinatorics/Inequalities

Permutations, combinations with constraints, circular arrangements, absolute value inequalities, quadratic inequalities, and sign-analysis traps.

Category
GMAT
Level
advanced
Languages
en → en
Cards
32
Markdown
Advanced Combinatorics/Inequalities (.md)

Flashcards (32)

#Front (Term / Question)Back (Definition / Answer)ExampleMultiple-Choice Options
1What is the Handshake / Pair Selection formula among n people?Number of unique pairwise interactions = C(n, 2) = n(n - 1) / 2.
2How do you calculate derangements (no item in its original spot) for 3 and 4 items?• For 3 items: !3 = 2 derangements. • For 4 items: !4 = 9 derangements. Formula: !n = n! * [1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n / n!].
3What is the rule for squaring both sides of an inequality a < b?• If both a and b are positive: a^2 < b^2. • If both a and b are negative: a^2 > b^2 (e.g., -5 < -2 => 25 > 4). • If signs differ: The result depends on absolute magnitudes.
4When does the product of three variables abc > 0?abc > 0 if and only if either: (1) All three are positive; OR (2) Exactly two are negative and one is positive.
5How do you simplify an absolute value inside an absolute value: ||x| - 3| = 5?Split outer absolute value: |x| - 3 = 5 or |x| - 3 = -5 => |x| = 8 or |x| = -2. Since |x| >= 0, |x| = -2 has no solution. |x| = 8 yields x = 8 or x = -8.
6What rule governs multiplying two inequalities together?You can multiply two inequalities (a < b and c < d) to yield ac < bd IF AND ONLY IF all four terms are strictly positive (0 < a < b and 0 < c < d). If negative numbers are involved, sign rules fail.
7What is the maximum number of intersection points of n distinct lines in a plane?Maximum intersections = C(n, 2) = n(n - 1) / 2, occurring when no two lines are parallel and no three lines intersect at the same point.
8How do you solve combination problems where specific items 'Must Be Together'?The 'Tie' (Glue) Method: Treat the group of items that must stay together as a single super-item. Count the arrangements of the super-item with other items, then multiply by the internal permutations of the tied items.
9How do you calculate arrangements of n items when some items are identical (multinomial permutations)?Total arrangements = n! / (p! * q! * r!...), where p, q, r are the frequencies of the identical items. Example: Arrangements of 'PEPPER' (6 letters: 3 P, 2 E, 1 R) = 6! / (3! * 2! * 1!) = 60.
10What is the AM-GM Inequality for non-negative real numbers a and b?(a + b) / 2 >= sqrt(ab). The Arithmetic Mean is always greater than or equal to the Geometric Mean. Equality holds if and only if a = b.
11What does the Triangle Inequality state for real numbers?|x + y| <= |x| + |y|. Equality holds if and only if x and y have the same sign (or at least one is zero, i.e., xy >= 0).
12For non-zero real numbers, what is the sign of x + 1/x?• If x > 0: x + 1/x >= 2 (minimum value 2 at x = 1, from AM-GM). • If x < 0: x + 1/x <= -2 (maximum value -2 at x = -1).
13What is the Stars and Bars theorem for distributing n identical items into k distinct groups?• If groups may receive zero items: C(n + k - 1, k - 1) • If each group must receive at least one item: C(n - 1, k - 1) (for n >= k).
14How do you solve a quadratic inequality like (x - 2)(x + 5) < 0 using critical points?Find the roots (critical points: -5 and 2). Plot them on the number line. The product is negative between the roots: -5 < x < 2. For > 0, the intervals are x < -5 or x > 2.
15What is the geometric interpretation of |x - c| <= d?The distance between x and the center c on the number line is at most d. The interval is [c - d, c + d].
16What is the inequality property of fractions when adding a positive constant k to numerator and denominator?For positive numbers a, b, k: • If a/b < 1 (proper fraction): (a + k)/(b + k) > a/b (it gets closer to 1). • If a/b > 1 (improper fraction): (a + k)/(b + k) < a/b (it gets closer to 1).
17How do you determine the sign of (x - a)^2 * (x - b)^3 * (x - c) > 0?Even powers (x - a)^2 are always non-negative and do not change the sign of the expression (except at x = a where it equals 0). Odd powers (x - b)^3 have the same sign as (x - b). Focus sign testing on the odd-power roots.
18What is Pascal's Identity for combinations?C(n, k) = C(n - 1, k - 1) + C(n - 1, k). Any selection either includes a specific chosen element or excludes it.
19What is the trap when solving rational inequalities like (x - 1)/(x + 3) <= 0?Never cross-multiply by (x + 3)! Instead, find critical points where numerator = 0 (x = 1) and denominator = 0 (x = -3). Test intervals, noting x != -3 (cannot divide by zero). Solution: -3 < x <= 1.
20How do you count the number of odd factors in an integer N?Completely remove all factors of 2 from the prime factorization of N. Calculate the total factors using only the remaining odd prime factors. Example: In 360 = 2^3 * 3^2 * 5^1, odd factors = (2 + 1)(1 + 1) = 6.
21How do you solve combination problems where specific items 'Must NOT Be Together'?Complementary Counting: (Total arrangements without restrictions) - (Arrangements where the items ARE together). Alternatively, place the unrestricted items first and place constrained items in the gaps.
22What is the symmetry property of combinations C(n, k)?C(n, k) = C(n, n - k). Choosing k items to include is mathematically identical to choosing (n - k) items to leave behind.
23What is the difference between Permutation and Combination formulas?• Permutation (Order matters): P(n, k) = n! / (n - k)! • Combination (Order does not matter): C(n, k) = n! / [k! * (n - k)!].
24What are the two algebraic equivalents for absolute value inequalities |x| < a and |x| > a (for a > 0)?• |x| < a is equivalent to -a < x < a (a single bounded interval). • |x| > a is equivalent to x > a OR x < -a (two disjoint unbounded intervals).
25Can you subtract one inequality from another (e.g., given a < b and c < d, is a - c < b - d)?NO! You cannot subtract inequalities oriented in the same direction. To combine them, multiply the second inequality by -1 (reversing its sign to -c > -d, i.e., -d < -c) and then ADD the aligned inequalities: a - d < b - c.
26Can you multiply both sides of an inequality by an unknown variable x?NO, not unless you know the sign of x! If x is positive, the sign stays; if x is negative, the sign flips. If the sign is unknown, you cannot multiply, or you must multiply by x^2 (which is strictly positive for x != 0).
27What is the Pigeonhole Principle in GMAT combinatorics?If n items are put into k containers and n > k, at least one container must contain at least ceil(n/k) items. Worst-case scenario analysis is used to guarantee an outcome.
28What is the formula for circular permutations of n distinct items?Arrangements around a circle = (n - 1)!. One position is fixed to eliminate rotational equivalence. If flipping the circle is identical (like a keychain or bead necklace), divide by 2: (n - 1)! / 2 (for n >= 3).
29How many paths exist on a grid from (0, 0) to (m, n) moving only Right and Up?Total moves = m + n (m Right moves and n Up moves). Number of unique paths = C(m + n, m) = (m + n)! / (m! * n!).
30In combinatorics, what does 'at least 2' mean when selecting from a group?Calculate: Total selections - (Selections with exactly 0) - (Selections with exactly 1).
31What is the Fundamental Counting Principle for independent choices?If an operation can be performed in m ways, and a subsequent operation can be performed in n ways, the two operations can be performed in m * n ways.
32What happens when you multiply or divide an inequality by a negative number?You MUST REVERSE the direction of the inequality sign. If -2x < 6, dividing by -2 yields x > -3.