Free CAT library

Indeterminate Systems & Invariant Linear Combinations

Master strategies for underdetermined systems where variables exceed equations (m < n): the method of undetermined multipliers (k1 E1 + k2 E2 = Target), extracting unique variables when remaining coefficients share identical ratios, and computing extreme values under non-negativity constraints.

1. The Story & Mental Model: The Invariant Projection in Shadow Space

Imagine visiting a wholesale spice merchant who refuses to disclose the individual unit prices of premium saffron (ss), cardamom (cc), and vanilla beans (vv). Instead, the merchant sells only pre-packaged commercial combo hampers:

  • Combo Alpha: 2 units saffron + 3 units cardamom + 5 units vanilla = ₹190

  • Combo Beta: 3 units saffron + 5 units cardamom + 8 units vanilla = ₹300

A customer arrives demanding Combo Target: 5 units saffron + 8 units cardamom + 13 units vanilla.

An untrained shopper might complain: "I cannot calculate the total bill because I have 3 unknown prices but only 2 equations—the system is indeterminate!"

Look closer at the quantities. Notice that:

Combo Target=Combo Alpha+Combo Beta\text{Combo Target} = \text{Combo Alpha} + \text{Combo Beta}

(2+3)s+(3+5)c+(5+8)v=5s+8c+13v(2 + 3)s + (3 + 5)c + (5 + 8)v = 5s + 8c + 13v

The total cost of Combo Target is unconditionally and invariantsly:

Cost=₹190+₹300=₹490\text{Cost} = ₹190 + ₹300 = ₹490

Neither the buyer, nor the merchant, nor any supercomputer can determine the individual price of a gram of saffron from this data. The individual prices are free to slide along a one-dimensional continuum of solutions (the null space). Yet, the total cost of this specific bundle is rock-solid, deterministic, and unique.

In linear algebra, an underdetermined system (m<nm < n) possesses degrees of freedom. While the exact coordinates (x,y,z)(x, y, z) cannot be pinpointed, any target vector that lies within the row space of the constraint equations inherits an absolute, invariant value. Solving these problems is the art of projecting your target onto the constraint subspace.


2. The CAT Question Blueprint: How Examiners Camouflage Underdetermined Systems

Examiners deliberately construct problems where the number of unknowns exceeds the number of equations. They want to test whether you blindly apply standard elimination and panic, or recognize invariant combinations:

The Five Primary Indeterminate Exam Archetypes:

  1. The Aggregate Composite Basket: Three items with two equations. You are asked for the cost of a composite basket, such as 1x+1y+1z1x + 1y + 1z or 5x+9y+13z5x + 9y + 13z. Unprepared students pick "Cannot be determined"—falling straight into the setter's trap.

  2. The Unique Variable Extraction: A system with 3 variables and only 2 equations, but the question asks for the exact value of a single variable (say yy). This is solvable if and only if the coefficients of the other two variables (xx and zz) appear in the exact same ratio across both equations, allowing you to eliminate both xx and zz simultaneously in a single subtraction!

  3. The Solvability Decoy (Data Sufficiency): The question asks whether two different target combinations can be evaluated. One combination lies in the row space (solvable), while the second does not (unsolvable).

  4. Non-Negativity Constraint Extremum (x,y,z≥0x, y, z \ge 0): When an expression cannot be determined uniquely, the question asks for its minimum or maximum value, knowing that real-world quantities cannot be negative.

  5. The Multi-Variable Arithmetic Progression (AP) Pattern: Systems where the coefficients of variables form an arithmetic progression. Any target basket whose coefficients also form an AP can be constructed as a linear combination of the two equations.


3. Core Concepts, Formulae & Derivations

A. The Method of Undetermined Multipliers

Let two constraint equations in three variables be:

E1:a1x+b1y+c1z=d1E_1: a_1 x + b_1 y + c_1 z = d_1

E2:a2x+b2y+c2z=d2E_2: a_2 x + b_2 y + c_2 z = d_2

We wish to evaluate the exact numerical value of a target linear expression:

T=αx+βy+γzT = \alpha x + \beta y + \gamma z

We assume TT can be expressed as a linear combination of E1E_1 and E2E_2 using multipliers k1k_1 and k2k_2:

k1E1+k2E2=Tk_1 E_1 + k_2 E_2 = T

Equating coefficients of x,y,zx, y, z on both sides:

k1a1+k2a2=α— (1)k_1 a_1 + k_2 a_2 = \alpha \quad \text{--- (1)}

k1b1+k2b2=β— (2)k_1 b_1 + k_2 b_2 = \beta \quad \text{--- (2)}

k1c1+k2c2=γ— (3)k_1 c_1 + k_2 c_2 = \gamma \quad \text{--- (3)}

The Verification Algorithm:

  1. Solve equations (1) and (2) simultaneously for the unique multipliers k1k_1 and k2k_2:

    k1=αb2−βa2a1b2−a2b1,k2=a1β−b1αa1b2−a2b1k_1 = \frac{\alpha b_2 - \beta a_2}{a_1 b_2 - a_2 b_1}, \quad k_2 = \frac{a_1 \beta - b_1 \alpha}{a_1 b_2 - a_2 b_1}

  2. Substitute (k1,k2)(k_1, k_2) into equation (3) to test consistency:

    • If k1c1+k2c2=γk_1 c_1 + k_2 c_2 = \gamma: The target vector lies in the row space of the constraint matrix. Its value is uniquely determined:

      Target Value=k1d1+k2d2\text{Target Value} = k_1 d_1 + k_2 d_2

    • If k1c1+k2c2≠γk_1 c_1 + k_2 c_2 \ne \gamma: The target vector is linearly independent of the constraints. Its value cannot be determined uniquely from the given data.

B. The Unique Single-Variable Extraction Theorem

Consider two linear equations in three variables:

a1x+b1y+c1z=d1— (1)a_1 x + b_1 y + c_1 z = d_1 \quad \text{--- (1)}

a2x+b2y+c2z=d2— (2)a_2 x + b_2 y + c_2 z = d_2 \quad \text{--- (2)}

Theorem: Variable yy can be determined uniquely if and only if the coefficients of xx and zz are strictly proportional:

a1a2=c1c2=λandb1b2≠λ\frac{a_1}{a_2} = \frac{c_1}{c_2} = \lambda \quad \text{and} \quad \frac{b_1}{b_2} \ne \lambda

Proof:

Multiply equation (2) by λ\lambda:

λa2x+λb2y+λc2z=λd2\lambda a_2 x + \lambda b_2 y + \lambda c_2 z = \lambda d_2

Since λa2=a1\lambda a_2 = a_1 and λc2=c1\lambda c_2 = c_1, this becomes:

a1x+λb2y+c1z=λd2a_1 x + \lambda b_2 y + c_1 z = \lambda d_2

Subtract this from equation (1):

(a1−a1)x+(b1−λb2)y+(c1−c1)z=d1−λd2(a_1 - a_1) x + (b_1 - \lambda b_2) y + (c_1 - c_1) z = d_1 - \lambda d_2

0⋅x+(b1−λb2)y+0⋅z=d1−λd20 \cdot x + (b_1 - \lambda b_2) y + 0 \cdot z = d_1 - \lambda d_2

y=d1−λd2b1−λb2y = \frac{d_1 - \lambda d_2}{b_1 - \lambda b_2}

Notice that both xx and zz are eliminated simultaneously in a single subtraction! Even though the individual values of xx and zz remain completely indeterminate, yy is isolated with absolute precision.

C. The Arithmetic Progression (AP) Coefficient Shortcut

If the coefficients of x,y,zx, y, z in E1E_1 form an AP with common difference Δ1\Delta_1, and in E2E_2 form an AP with common difference Δ2\Delta_2:

  • Any target expression whose coefficients also form an AP can be constructed as a linear combination k1E1+k2E2k_1 E_1 + k_2 E_2.

  • The multipliers k1k_1 and k2k_2 simply match the first term and the common difference:

    Target First Term=k1a1+k2a2\text{Target First Term} = k_1 a_1 + k_2 a_2

    Target Difference=k1Δ1+k2Δ2\text{Target Difference} = k_1 \Delta_1 + k_2 \Delta_2

D. Optimization under Non-Negativity Constraints (x,y,z≥0x, y, z \ge 0)

When a target expression T=αx+βy+γzT = \alpha x + \beta y + \gamma z does NOT satisfy the multiplier consistency condition, its value varies depending on the choice of the free variable.

To find the range [Tmin⁡,Tmax⁡][T_{\min}, T_{\max}] under the physical restriction x≥0,y≥0,z≥0x \ge 0, y \ge 0, z \ge 0:

  1. Set the free variable z=tz = t.

  2. Express xx and yy as linear functions of tt: x(t)=x0+utx(t) = x_0 + u t and y(t)=y0+vty(t) = y_0 + v t.

  3. Apply non-negativity: x(t)≥0,y(t)≥0,t≥0x(t) \ge 0, y(t) \ge 0, t \ge 0. This defines a closed interval of valid parameters t∈[tmin⁡,tmax⁡]t \in [t_{\min}, t_{\max}].

  4. Substitute into T(t)=Mt+CT(t) = M t + C. Since T(t)T(t) is a monotonic linear function, its minimum and maximum values occur precisely at the endpoints tmin⁡t_{\min} and tmax⁡t_{\max}.


4. Common Pitfalls & Speed Shortcuts

Pitfall 1: Blindly Selecting "Cannot Be Determined"

Seeing 3 unknowns and 2 equations leads many students to guess "Data Insufficient" without attempting to find multipliers.

  • The Rule: If the question asks for a specific combination of all variables (or for one variable whose companions share coefficient ratios), ALWAYS test for multipliers k1,k2k_1, k_2 first.

Pitfall 2: The "Arbitrary Zero" Assumption Trap

Some coaching shortcuts advise setting the free variable z=0z = 0 to calculate the target value quickly.

  • The Danger: Setting z=0z = 0 works only if the target combination is already known to be in the row space. If the target expression is not a valid linear combination, setting z=0z = 0 will produce a bogus number that changes if you had set z=1z = 1. Always verify the third coefficient equation k1c1+k2c2=γk_1 c_1 + k_2 c_2 = \gamma before relying on any value!

Pitfall 3: Missing Negative Multipliers

Multipliers k1k_1 and k2k_2 can be negative integers or fractions. Do not restrict yourself to adding equations; subtraction (k1E1−k2E2k_1 E_1 - k_2 E_2) is equally valid.

Formulas

Undetermined Multiplier System

k1a1+k2a2=α,k1b1+k2b2=β,k1c1+k2c2=γk_1 a_1 + k_2 a_2 = \alpha, \quad k_1 b_1 + k_2 b_2 = \beta, \quad k_1 c_1 + k_2 c_2 = \gamma

Target \alpha x + \beta y + \gamma z is solvable if and only if all 3 equations are consistent for (k_1, k_2)
Invariant Target Value Equation

Target Value=k1d1+k2d2\text{Target Value} = k_1 d_1 + k_2 d_2

Calculates composite basket cost directly without finding individual variable prices
Unique Variable Extraction Ratio Criterion

a1a2=c1c2=λ≠b1b2  ⟹  y=d1−λd2b1−λb2\frac{a_1}{a_2} = \frac{c_1}{c_2} = \lambda \ne \frac{b_1}{b_2} \implies y = \frac{d_1 - \lambda d_2}{b_1 - \lambda b_2}

Isolates variable y uniquely from an underdetermined system by eliminating x and z together
Parametric Free-Variable Linear Form

T(t)=Mt+C,t∈[tmin⁡,tmax⁡]T(t) = M t + C, \quad t \in [t_{\min}, t_{\max}]

Optimizes non-invariant linear objectives over the feasible non-negative domain

Traps and tips

  • Never Guess 'Data Insufficient' Reflexively: Test whether the target vector is a linear combination k_1 E_1 + k_2 E_2 before giving up.
  • Test the Third Coefficient: After solving k_1 and k_2 from the first two coefficients, you MUST verify that k_1 c_1 + k_2 c_2 equals the third target coefficient.
  • Look for Proportional Companion Coefficients: If a question asks for a single variable from 2 equations with 3 unknowns, check if the other two variables have identical coefficient ratios.
  • Beware of the Arbitrary Zero Shortcut: Setting z = 0 yields an answer even when the target is NOT uniquely determinable. Always verify solvability first.

Solved examples

Example 3.1: Classical Stationery Basket Pricing via Multipliers

At a university bookstore, two purchasing receipts for pens (pp), erasers (ee), and notebooks (nn) are recorded:

  • Receipt 1: 33 pens, 55 erasers, and 77 notebooks cost ₹104104.

  • Receipt 2: 44 pens, 77 erasers, and 1010 notebooks cost ₹143143.

Find the exact total cost of purchasing a standard student pack consisting of 11 pen, 11 eraser, and 11 notebook (p+e+np + e + n).

Show solution

Step 1: Formulate the system of constraint equations.

E1:3p+5e+7n=104E_1: 3p + 5e + 7n = 104

E2:4p+7e+10n=143E_2: 4p + 7e + 10n = 143

Target Expression: T=1p+1e+1nT = 1p + 1e + 1n.

Notice that we have 33 unknowns and only 22 equations.

Step 2: Set up the undetermined multipliers equation.

Assume there exist scalars k1k_1 and k2k_2 such that:

k1(3p+5e+7n)+k2(4p+7e+10n)=1p+1e+1nk_1(3p + 5e + 7n) + k_2(4p + 7e + 10n) = 1p + 1e + 1n

Equating coefficients for p,e,np, e, n:

3k1+4k2=1— (1)3k_1 + 4k_2 = 1 \quad \text{--- (1)}

5k1+7k2=1— (2)5k_1 + 7k_2 = 1 \quad \text{--- (2)}

7k1+10k2=1— (3)7k_1 + 10k_2 = 1 \quad \text{--- (3)}

Step 3: Solve equations (1) and (2) for k1k_1 and k2k_2.

Multiply equation (1) by 77 and equation (2) by 44:

21k1+28k2=721k_1 + 28k_2 = 7

20k1+28k2=420k_1 + 28k_2 = 4

Subtracting the two equations:

(21k1−20k1)=7−4  ⟹  k1=3(21k_1 - 20k_1) = 7 - 4 \implies k_1 = 3

Substitute k1=3k_1 = 3 into equation (1):

3(3)+4k2=13(3) + 4k_2 = 1

9+4k2=1  ⟹  4k2=−8  ⟹  k2=−29 + 4k_2 = 1 \implies 4k_2 = -8 \implies k_2 = -2

Step 4: Verify consistency against the third coefficient equation (3).

Check equation (3) with k1=3k_1 = 3 and k2=−2k_2 = -2:

7k1+10k2=7(3)+10(−2)=21−20=17k_1 + 10k_2 = 7(3) + 10(-2) = 21 - 20 = 1

Equation (3) is satisfied perfectly! The target expression is valid.

Step 5: Compute the target bundle cost.

Cost=k1d1+k2d2=3(104)+(−2)(143)\text{Cost} = k_1 d_1 + k_2 d_2 = 3(104) + (-2)(143)

Cost=312−286=₹26\text{Cost} = 312 - 286 = ₹26

The cost of 11 pen, 11 eraser, and 11 notebook is exactly ₹2626.

Takeaway: Solve for multipliers k 1 and k 2 using two variable coefficients, then verify consistency on the third coefficient before computing the total cost.

Example 3.2: Finding an Asymmetric Target Basket

Using the same store pricing where:

3p+5e+7n=1043p + 5e + 7n = 104

4p+7e+10n=1434p + 7e + 10n = 143

Determine the exact cost of an advanced bulk kit containing 55 pens, 99 erasers, and 1313 notebooks (5p+9e+13n5p + 9e + 13n).

Show solution

Step 1: Set up the undetermined multipliers for the new target.

Target Expression: 5p+9e+13n5p + 9e + 13n.

k1(3p+5e+7n)+k2(4p+7e+10n)=5p+9e+13nk_1(3p + 5e + 7n) + k_2(4p + 7e + 10n) = 5p + 9e + 13n

Equating coefficients:

3k1+4k2=5— (1)3k_1 + 4k_2 = 5 \quad \text{--- (1)}

5k1+7k2=9— (2)5k_1 + 7k_2 = 9 \quad \text{--- (2)}

7k1+10k2=13— (3)7k_1 + 10k_2 = 13 \quad \text{--- (3)}

Step 2: Solve equations (1) and (2) for k1k_1 and k2k_2.

Multiply equation (1) by 55 and equation (2) by 33:

15k1+20k2=2515k_1 + 20k_2 = 25

15k1+21k2=2715k_1 + 21k_2 = 27

Subtracting the first from the second:

(21k2−20k2)=27−25  ⟹  k2=2(21k_2 - 20k_2) = 27 - 25 \implies k_2 = 2

Substitute k2=2k_2 = 2 into equation (1):

3k1+4(2)=53k_1 + 4(2) = 5

3k1+8=5  ⟹  3k1=−3  ⟹  k1=−13k_1 + 8 = 5 \implies 3k_1 = -3 \implies k_1 = -1

Step 3: Verify the third coefficient.

7k1+10k2=7(−1)+10(2)=−7+20=137k_1 + 10k_2 = 7(-1) + 10(2) = -7 + 20 = 13

Equation (3) holds exactly! Thus, T=2E2−E1T = 2 E_2 - E_1.

Step 4: Compute the total cost.

Cost=k1d1+k2d2=−1(104)+2(143)\text{Cost} = k_1 d_1 + k_2 d_2 = -1(104) + 2(143)

Cost=−104+286=₹182\text{Cost} = -104 + 286 = ₹182

The cost of 55 pens, 99 erasers, and 1313 notebooks is exactly ₹182182.

Takeaway: Target baskets with irregular coefficients can still be evaluated instantly if they satisfy the linear combination Target = k 1 E 1 + k 2 E 2.

Example 3.3: Extracting a Unique Variable When Remaining Coefficients Match in Ratio

An operational analyst receives two production constraints involving three raw materials (x,y,z)(x, y, z):

E1:2x+7y+6z=75E_1: 2x + 7y + 6z = 75

E2:3x+4y+9z=80E_2: 3x + 4y + 9z = 80

Although the system has three unknowns and only two equations, determine whether the exact numerical value of yy can be found. If so, find its value.

Show solution

Step 1: Inspect the ratios of coefficients for xx and zz.

Notice the coefficients of xx and zz across both equations:

  • Coefficient of xx: in E1E_1 it is 22, in E2E_2 it is 33. Ratio: a1a2=23\frac{a_1}{a_2} = \frac{2}{3}.

  • Coefficient of zz: in E1E_1 it is 66, in E2E_2 it is 99. Ratio: c1c2=69=23\frac{c_1}{c_2} = \frac{6}{9} = \frac{2}{3}.

Because a1a2=c1c2=23\frac{a_1}{a_2} = \frac{c_1}{c_2} = \frac{2}{3}, the variables xx and zz can be eliminated simultaneously in one single subtraction!

Step 2: Eliminate both xx and zz.

Multiply equation E1E_1 by 33 and equation E2E_2 by 22 to equalize the coefficients of both xx and zz to 66 and 1818 respectively:

3E1:3(2x+7y+6z)=3(75)  ⟹  6x+21y+18z=225— (3)3 E_1: 3(2x + 7y + 6z) = 3(75) \implies 6x + 21y + 18z = 225 \quad \text{--- (3)}

2E2:2(3x+4y+9z)=2(80)  ⟹  6x+8y+18z=160— (4)2 E_2: 2(3x + 4y + 9z) = 2(80) \implies 6x + 8y + 18z = 160 \quad \text{--- (4)}

Step 3: Subtract equation (4) from equation (3).

(6x−6x)+(21y−8y)+(18z−18z)=225−160(6x - 6x) + (21y - 8y) + (18z - 18z) = 225 - 160

0⋅x+13y+0⋅z=650\cdot x + 13y + 0\cdot z = 65

13y=6513y = 65

y=6513=5y = \frac{65}{13} = 5

Conclusion:

Even though xx and zz remain completely unknown and have infinitely many pairs of solutions, variable yy has the unique, deterministic value of 55.

Takeaway: If the coefficients of two variables are proportional between two equations, both variables vanish upon subtraction, revealing the unique value of the third variable.

Example 3.4: Solvability Test: Solvable vs Data Insufficient

Given the two cost equations for three catalog items A,B,CA, B, C:

E1:2A+3B+4C=45E_1: 2A + 3B + 4C = 45

E2:3A+5B+7C=74E_2: 3A + 5B + 7C = 74

Determine whether the total cost can be evaluated uniquely for:

(a) Basket 1: 4A+7B+10C4A + 7B + 10C

(b) Basket 2: 5A+7B+8C5A + 7B + 8C

Show solution

Step 1: Test Basket 1 (4A+7B+10C4A + 7B + 10C).

Set k1E1+k2E2=4A+7B+10Ck_1 E_1 + k_2 E_2 = 4A + 7B + 10C:

2k1+3k2=4— (1)2k_1 + 3k_2 = 4 \quad \text{--- (1)}

3k1+5k2=7— (2)3k_1 + 5k_2 = 7 \quad \text{--- (2)}

4k1+7k2=10— (3)4k_1 + 7k_2 = 10 \quad \text{--- (3)}

Solve (1) and (2):

Multiply (1) by 33: 6k1+9k2=126k_1 + 9k_2 = 12.

Multiply (2) by 22: 6k1+10k2=146k_1 + 10k_2 = 14.

Subtracting: k2=14−12=2k_2 = 14 - 12 = 2.

From (1): 2k1+3(2)=4  ⟹  2k1=−2  ⟹  k1=−12k_1 + 3(2) = 4 \implies 2k_1 = -2 \implies k_1 = -1.

Check equation (3):

4(−1)+7(2)=−4+14=104(-1) + 7(2) = -4 + 14 = 10

Equation (3) holds! Basket 1 can be determined uniquely.

Cost=−1(45)+2(74)=−45+148=₹103\text{Cost} = -1(45) + 2(74) = -45 + 148 = ₹103

Step 2: Test Basket 2 (5A+7B+8C5A + 7B + 8C).

Set k1E1+k2E2=5A+7B+8Ck_1 E_1 + k_2 E_2 = 5A + 7B + 8C:

2k1+3k2=5— (4)2k_1 + 3k_2 = 5 \quad \text{--- (4)}

3k1+5k2=7— (5)3k_1 + 5k_2 = 7 \quad \text{--- (5)}

4k1+7k2=8— (6)4k_1 + 7k_2 = 8 \quad \text{--- (6)}

Solve (4) and (5):

Multiply (4) by 33: 6k1+9k2=156k_1 + 9k_2 = 15.

Multiply (5) by 22: 6k1+10k2=146k_1 + 10k_2 = 14.

Subtracting: k2=14−15=−1k_2 = 14 - 15 = -1.

From (4): 2k1+3(−1)=5  ⟹  2k1=8  ⟹  k1=42k_1 + 3(-1) = 5 \implies 2k_1 = 8 \implies k_1 = 4.

Check equation (6):

4(4)+7(−1)=16−7=9≠84(4) + 7(-1) = 16 - 7 = 9 \ne 8

Equation (6) fails because 9≠89 \ne 8! Basket 2 cannot be determined uniquely (its cost varies depending on the choice of individual item prices).

Conclusion: Basket 1 is uniquely ₹103103; Basket 2 is Data Insufficient.

Takeaway: A target combination is uniquely solvable if and only if the third coefficient equation is strictly consistent with the multipliers derived from the first two.

Example 3.5: Range of Target Cost under Non-Negativity Constraints

A logistics planner considers non-negative shipping volumes x,y,z≥0x, y, z \ge 0 satisfying the simultaneous linear constraints:

x+2y+3z=30x + 2y + 3z = 30

2x+3y+z=402x + 3y + z = 40

Find the minimum and maximum possible values of the total shipping volume S=x+y+zS = x + y + z.

Show solution

Step 1: Express variables in terms of free variable z=tz = t.

Multiply the first equation by 22 and subtract the second:

2(x+2y+3z)−(2x+3y+z)=2(30)−402(x + 2y + 3z) - (2x + 3y + z) = 2(30) - 40

(2x−2x)+(4y−3y)+(6z−z)=60−40(2x - 2x) + (4y - 3y) + (6z - z) = 60 - 40

y+5z=20  ⟹  y=20−5ty + 5z = 20 \implies y = 20 - 5t

Substitute y=20−5ty = 20 - 5t and z=tz = t into the first equation to express xx:

x+2(20−5t)+3t=30x + 2(20 - 5t) + 3t = 30

x+40−10t+3t=30x + 40 - 10t + 3t = 30

x=30−40+7t=7t−10x = 30 - 40 + 7t = 7t - 10

Step 2: Apply the non-negativity restrictions (x≥0,y≥0,z≥0x \ge 0, y \ge 0, z \ge 0).

  1. For x≥0x \ge 0:

    7t−10≥0  ⟹  t≥107≈1.4287t - 10 \ge 0 \implies t \ge \frac{10}{7} \approx 1.428

  2. For y≥0y \ge 0:

    20−5t≥0  ⟹  5t≤20  ⟹  t≤420 - 5t \ge 0 \implies 5t \le 20 \implies t \le 4

  3. For z≥0z \ge 0:

    t≥0t \ge 0

Combining these constraints, the permissible domain for parameter tt is:

107≤t≤4\frac{10}{7} \le t \le 4

Step 3: Formulate the objective function S(t)=x+y+zS(t) = x + y + z.

S(t)=(7t−10)+(20−5t)+tS(t) = (7t - 10) + (20 - 5t) + t

S(t)=(7−5+1)t+(−10+20)=3t+10S(t) = (7 - 5 + 1)t + (-10 + 20) = 3t + 10

Since S(t)=3t+10S(t) = 3t + 10 is a strictly increasing linear function of tt, its minimum occurs at the lower bound of tt and its maximum occurs at the upper bound.

Step 4: Compute extreme values.

  • Minimum Value (t=10/7t = 10/7):

    Smin⁡=3(107)+10=307+707=1007≈14.29S_{\min} = 3\left(\frac{10}{7}\right) + 10 = \frac{30}{7} + \frac{70}{7} = \frac{100}{7} \approx 14.29

  • Maximum Value (t=4t = 4):

    Smax⁡=3(4)+10=12+10=22S_{\max} = 3(4) + 10 = 12 + 10 = 22

The total shipping volume x+y+zx + y + z ranges from a minimum of 1007\frac{100}{7} to a maximum of 2222.

Takeaway: When an objective function cannot be uniquely determined, parameterize with free variable t and evaluate the function at the non-negativity domain endpoints.

Example 3.6: 4-Variable Manufacturing Mix with AP Coefficients

A chemical synthesis facility produces four industrial reagents with unit costs w,x,y,zw, x, y, z. Two production runs report the following total costs:

Run 1: 2w+3x+4y+5z=180\text{Run 1: } 2w + 3x + 4y + 5z = 180

Run 2: 3w+5x+7y+9z=290\text{Run 2: } 3w + 5x + 7y + 9z = 290

Find the exact cost of manufacturing a customized blend containing 4w+7x+10y+13z4w + 7x + 10y + 13z.

Show solution

Step 1: Observe coefficient structures across variables.

Notice the progression of coefficients across variables w,x,y,zw, x, y, z:

  • In Run 1, the coefficients are 2,3,4,52, 3, 4, 5, which form an AP with first term a1=2a_1 = 2 and common difference d1=1d_1 = 1.

  • In Run 2, the coefficients are 3,5,7,93, 5, 7, 9, which form an AP with first term a2=3a_2 = 3 and common difference d2=2d_2 = 2.

  • In the Target, the coefficients are 4,7,10,134, 7, 10, 13, which form an AP with first term aT=4a_T = 4 and common difference dT=3d_T = 3.

Step 2: Find multipliers k1k_1 and k2k_2 from the AP parameters.

To match the first term and common difference:

k1(2)+k2(3)=4— (First Term Equation)k_1(2) + k_2(3) = 4 \quad \text{--- (First Term Equation)}

k1(1)+k2(2)=3— (Common Difference Equation)k_1(1) + k_2(2) = 3 \quad \text{--- (Common Difference Equation)}

Multiply the second equation by 22:

2k1+4k2=62k_1 + 4k_2 = 6

Subtract the first equation (2k1+3k2=42k_1 + 3k_2 = 4):

(4k2−3k2)=6−4  ⟹  k2=2(4k_2 - 3k_2) = 6 - 4 \implies k_2 = 2

Substitute k2=2k_2 = 2 into k1+2k2=3k_1 + 2k_2 = 3:

k1+2(2)=3  ⟹  k1=3−4=−1k_1 + 2(2) = 3 \implies k_1 = 3 - 4 = -1

Step 3: Verify all 4 coefficients simultaneously.

Linear combination: 2E2−E12 E_2 - E_1.

  • For ww: 2(3)−2=6−2=42(3) - 2 = 6 - 2 = 4 (Matches)

  • For xx: 2(5)−3=10−3=72(5) - 3 = 10 - 3 = 7 (Matches)

  • For yy: 2(7)−4=14−4=102(7) - 4 = 14 - 4 = 10 (Matches)

  • For zz: 2(9)−5=18−5=132(9) - 5 = 18 - 5 = 13 (Matches)

All 4 variable coefficients match simultaneously!

Step 4: Calculate the target cost.

Cost=2(290)−1(180)=580−180=₹400\text{Cost} = 2(290) - 1(180) = 580 - 180 = ₹400

The customized blend costs exactly ₹400400.

Takeaway: When equation coefficients form arithmetic progressions, align the first term and common difference to solve any AP target basket across arbitrarily many variables.

Practice questions

Question 1 · CAT Level

The cost of 33 pens, 55 notebooks, and 77 pencils is ₹115115, while the cost of 55 pens, 88 notebooks, and 1111 pencils is ₹180180. What is the cost of 11 pen, 22 notebooks, and 33 pencils?

  1. A

    ₹45₹45

  2. B

    ₹50₹50

  3. C

    ₹55₹55

  4. D

    ₹60₹60

Show answer and explanation

Answer: (B) ₹50

Let equations be E1:3p+5n+7c=115E_1: 3p + 5n + 7c = 115 and E2:5p+8n+11c=180E_2: 5p + 8n + 11c = 180.

We seek the value of T=1p+2n+3cT = 1p + 2n + 3c.

Notice the linear combination: 2E1−E2=2(3p+5n+7c)−(5p+8n+11c)2E_1 - E_2 = 2(3p + 5n + 7c) - (5p + 8n + 11c).

=(6p−5p)+(10n−8n)+(14c−11c)=1p+2n+3c=T=(6p - 5p) + (10n - 8n) + (14c - 11c) = 1p + 2n + 3c = T.

Therefore, T=2(115)−180=230−180=₹50T = 2(115) - 180 = 230 - 180 = ₹50.

Question 2 · CAT Level

If 2x+3y+4z=292x + 3y + 4z = 29 and 3x+5y+7z=463x + 5y + 7z = 46, what is the unique value of 5x+7y+9z5x + 7y + 9z?

  1. A

    6565

  2. B

    7070

  3. C

    7575

  4. D

    8080

Show answer and explanation

Answer: (B) 70

Set up k1(2x+3y+4z)+k2(3x+5y+7z)=5x+7y+9zk_1(2x + 3y + 4z) + k_2(3x + 5y + 7z) = 5x + 7y + 9z.

Matching coefficients: 2k1+3k2=52k_1 + 3k_2 = 5 and 3k1+5k2=73k_1 + 5k_2 = 7.

Multiplying by 33 and 22: 6k1+9k2=156k_1 + 9k_2 = 15 and 6k1+10k2=14  ⟹  k2=−1,k1=46k_1 + 10k_2 = 14 \implies k_2 = -1, k_1 = 4.

Verify zz coefficient: 4(4)+7(−1)=16−7=94(4) + 7(-1) = 16 - 7 = 9 (Consistent!).

Value =4(29)+(−1)(46)=116−46=70= 4(29) + (-1)(46) = 116 - 46 = 70.

Question 3 · CAT Level

In the system 3a+4b+2c=443a + 4b + 2c = 44 and 6a+8b+7c=976a + 8b + 7c = 97, what is the unique value of cc?

  1. A

    22

  2. B

    33

  3. C

    44

  4. D

    55

Show answer and explanation

Answer: (B) 3

Observe that the coefficients of aa and bb are directly proportional: 63=84=2\frac{6}{3} = \frac{8}{4} = 2.

Multiply the first equation by 22: 6a+8b+4c=886a + 8b + 4c = 88.

Subtract this from the second equation: (6a+8b+7c)−(6a+8b+4c)=97−88(6a + 8b + 7c) - (6a + 8b + 4c) = 97 - 88.

3c=9  ⟹  c=33c = 9 \implies c = 3.

Thus, cc can be uniquely determined without knowing aa or bb.

Question 4 · CAT Level

Let x,y,zx, y, z be positive integers satisfying x+2y+3z=30x + 2y + 3z = 30 and 2x+y+z=182x + y + z = 18. What is the maximum possible value of zz?

  1. A

    44

  2. B

    55

  3. C

    66

  4. D

    77

Show answer and explanation

Answer: (C) 6

Multiply the second equation by 22: 4x+2y+2z=364x + 2y + 2z = 36.

Subtract the first equation: (4x+2y+2z)−(x+2y+3z)=36−30  ⟹  3x−z=6  ⟹  z=3x−6(4x + 2y + 2z) - (x + 2y + 3z) = 36 - 30 \implies 3x - z = 6 \implies z = 3x - 6.

Substitute z=3x−6z = 3x - 6 into the second equation: 2x+y+(3x−6)=18  ⟹  y=24−5x2x + y + (3x - 6) = 18 \implies y = 24 - 5x.

Since yy is a positive integer, y≥1  ⟹  24−5x≥1  ⟹  5x≤23  ⟹  x≤4y \ge 1 \implies 24 - 5x \ge 1 \implies 5x \le 23 \implies x \le 4.

To maximize zz, choose the maximum integer x=4x = 4: z=3(4)−6=12−6=6z = 3(4) - 6 = 12 - 6 = 6 (with y=4y = 4).

Question 5 · CAT Level

Given 2x+5y+3z=402x + 5y + 3z = 40 and 3x+8y+5z=653x + 8y + 5z = 65, what is the value of 4x+11y+7z4x + 11y + 7z?

  1. A

    8080

  2. B

    8585

  3. C

    9090

  4. D

    9595

Show answer and explanation

Answer: (C) 90

We express the target as a linear combination k1(2x+5y+3z)+k2(3x+8y+5z)k_1(2x + 5y + 3z) + k_2(3x + 8y + 5z).

Matching coefficients: 2k1+3k2=42k_1 + 3k_2 = 4 and 5k1+8k2=115k_1 + 8k_2 = 11.

Multiply first by 55 and second by 22: 10k1+15k2=2010k_1 + 15k_2 = 20 and 10k1+16k2=22  ⟹  k2=2,k1=−110k_1 + 16k_2 = 22 \implies k_2 = 2, k_1 = -1.

Check zz coefficient: 3(−1)+5(2)=−3+10=73(-1) + 5(2) = -3 + 10 = 7 (Consistent!).

Target value =−1(40)+2(65)=−40+130=90= -1(40) + 2(65) = -40 + 130 = 90.

Try real CAT questions

Study this concept with interactive practice in PrepSoc.

Open the concept library