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

Home > Numbers
Dimsums LTD (Posted on 2017-10-16) Difficulty: 2 of 5
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    
Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution | Comment 1 of 3
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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information