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

 Missions impossible (Posted on 2014-11-17)
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 | Comment 1 of 3
Find the GCD of 17 and 9 via Euclidean method:

`           x9  + x1717          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          110         20         -10   can't be made positive on both sides11         22         -11   can't be made positive on both sides12         24         -12   can't be made positive on both sides13         26         -13   can't be made positive on both sides14         28         -14   can't be made positive on both sides15         30         -15   can't be made positive on both sides16         32         -16   can't be made positive on both sides17         34         -17   -- Add 2*9 to the x17 and                                subtract 2*17 from the x917          0           118          2           019          4          -1   can't be made positive on both sides20          6          -2   can't be made positive on both sides21          8          -3   can't be made positive on both sides22         10          -4   can't be made positive on both sides23         12          -5   can't be made positive on both sides24         14          -6   can't be made positive on both sides25         16          -7   can't be made positive on both sides26         18          -8   -- Add 1*9 to the x17                               subtract 1*17 from the x926          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      x3131                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

 Search: Search body:
Forums (0)
Random Problem
Site Statistics
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox: