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

Home > Just Math
Missions impossible (Posted on 2014-11-17) Difficulty: 3 of 5
A certain chain store sells chocolate bars in packets of 17 and 9 only. Clearly, you could not get 8 or 25 bars. Find all quantities of bars that you cannot buy.

Generalize for m and n, mutually prime integers, m>n.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution | Comment 1 of 3
Find the GCD of 17 and 9 via Euclidean method:

           x9  + x17
17          0     1 
 9          1     0 
 8         -1     1 
 1          2    -1 
 0        -17     9 
 
The GCD is 1 and it is obtainable by 2*9 - 1*17 

and

9*17 = 17*9 


buy        x9         x17
 N
 
 9          1
10         20         -10   can't be made positive on both sides
11         22         -11   can't be made positive on both sides
12         24         -12   can't be made positive on both sides
13         26         -13   can't be made positive on both sides
14         28         -14   can't be made positive on both sides
15         30         -15   can't be made positive on both sides
16         32         -16   can't be made positive on both sides
17         34         -17   -- Add 2*9 to the x17 and 
                               subtract 2*17 from the x9
17          0           1
18          2           0
19          4          -1   can't be made positive on both sides
20          6          -2   can't be made positive on both sides
21          8          -3   can't be made positive on both sides
22         10          -4   can't be made positive on both sides
23         12          -5   can't be made positive on both sides
24         14          -6   can't be made positive on both sides
25         16          -7   can't be made positive on both sides
26         18          -8   -- Add 1*9 to the x17
                               subtract 1*17 from the x9
26          1           1   
27          3           0

                               
To buy n items, start, theoretically, with 2*n 9-packs and -1*n 17-packs. Adjustment makes this (-n + 9*ceiling(n/9)) 17-packs and 2*n - 17*ceiling(n/9) 9-packs. If this latter is negative, the number is not possible.


Another example

         x9      x31
31                1
 9        1
 4       -3       1
 1        7      -2
 0       -31      9
 
For n bars, 7*n 9-pacs and -2*n 31-packs to start.  Adjustment factor to make number of 31-packs positive is ceiling(2*n/9): add 9 times this to the -2*n 31-packs and subtract 31 times this from the 7*n 9-packs:


9*ceiling(2*n/9) - 2*n   31-packs and
7*n - 31*ceiling(2*n/9)  9-packs

If the latter is negative, the number is impossible.
 

Edited on November 17, 2014, 7:17 pm
  Posted by Charlie on 2014-11-17 19:16:26

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 (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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