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.
Source: Alok Goyal (Stellaris VP, ExHelion VC) puzzle blog
A person can buy any multiple of 3 dimsums by buying just the smaller boxes.
Since 7 = 1 mod 3, a person can buy any number 3n+1 of dimsums by getting 1 7box and the rest 3boxes, provided the total is >= 7.
It takes 2 7boxes to make a total that's 3n+2, and any number of 3boxes after that, so the smallest 3n+2 solution is 14.
That means the biggest 3n+2 failure is 14  3 = 11. (The biggest 3n+1 failure is 73 = 4, which is smaller than 11, so 11 is the specific solution.)
Generalizing, assume p < q. (p1)q is the smallest number possible with its modulus mod p that you can make. No amount of subtracting pboxes can change that modulus; it must come entirely from qboxes  and because p and q are relatively prime the first p1 multiples of q must all have distinct moduli mod p. The biggest failure for this modulus, then, is (p1)q  p = pq  (p+q) [ or (p1)(q1)  1 if you prefer]

Posted by Paul
on 20171016 10:40:41 