Buying Dimsums: The Chicken McNugget (Frobenius Number) Puzzle
Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too. Solution: Highlight the part between the * symbols for the answer. * Answer: 11 dimsums. In general for coprime box sizes p and q, the largest unattainable number is the Frobenius number pq - p - q. For 7 and 3: 11 = 7a + 3b has no non-negative solution (a = 0: 11 not divisible by 3; a = 1: 4 left, not a multiple of 3). But 12 = 4x3, 13 = 7 + 2x3, 14 = 2x7, and from then on every number is 12, 13 or 14 plus a multiple of 3 - so every n >= 12 is buyable and 11 is the answer. General proof sketch: since gcd(p, q) = 1, the numbers 0, q, 2q, ..., (p-1)q hit every residue class mod p. The smallest representable number in class r is t_r = k_r q for the unique k_r in 0..p-1 with k_r q = r (mod p)...