Anand packs 304 marbles into bags of 9 or 11 marbles so that no marble is left. He wants to maximize the number of bags with 9 marbles, with at least one bag containing 11 marbles. How many bags does he need?

• A. 33
• B. 32
• C. 31
• D. 30

Answer: (B)

You’re trying to split 304 into bags of 9 and 11 marbles, with at least one bag of 11, and you want as many bags of 9 as possible. So set up the equation 9x + 11y = 304 with x ≥ 0 and y ≥ 1, and maximize x.

Work with the equation modulo 9 to find a feasible y. Since 11 ≡ 2 (mod 9) and 304 ≡ 7 (mod 9), we need 2y ≡ 7 (mod 9). The inverse of 2 modulo 9 is 5, so y ≡ 7·5 ≡ 35 ≡ 8 (mod 9). The smallest positive y that works is 8. Then x = (304 − 11·8)/9 = (304 − 88)/9 = 216/9 = 24. So with y = 8, you have 24 bags of 9 and 8 bags of 11, totaling 24 + 8 = 32 bags.

If y increases by 9, x drops by 11, so the total number of bags goes down (from 32 to 30, then 28, …). Therefore the maximum number of bags occurs at y = 8, giving 32 bags. He needs 32 bags.