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.
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 |
solution
