All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Dimsums LTD (Posted on 2017-10-16)
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

 See The Solution Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution Comment 1 of 1
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

 Search: Search body:
Forums (0)