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, Ex-Helion 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 7-box and the rest 3-boxes, provided the total is >= 7.
It takes 2 7-boxes to make a total that's 3n+2, and any number of 3-boxes 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 7-3 = 4, which is smaller than 11, so 11 is the specific solution.)
Generalizing, assume p < q. (p-1)q is the smallest number possible with its modulus mod p that you can make. No amount of subtracting p-boxes can change that modulus; it must come entirely from q-boxes -- and because p and q are relatively prime the first p-1 multiples of q must all have distinct moduli mod p. The biggest failure for this modulus, then, is (p-1)q - p = pq - (p+q) [ or (p-1)(q-1) - 1 if you prefer]
|
Posted by Paul
on 2017-10-16 10:40:41 |