There's a problem I ran into that said:
"At a certain casino, blue poker chips are worth 9 dollars and white poker chips are worth 14 dollars. How many chips can Hank buy to spend exactly 206 dollars?"
The answer is 19 chips (12 blue and 7 white). The solution posed was trial-and-error which was frustrating. I was able to use an augmented matrix to solve it, but that took longer than I would've liked.
I noticed 9 and 14 are coprime, though, so according to the Euclidean Algorithm there exist integers X and Y such that 9X+14Y=1 (since gcd(9,14)=1). That said, there should be integers X' and Y' such that 9X'+14Y'=206 (linear independence; spanning set; etc.). The issue here is that 9X+14Y=1 results in X=-3, Y=2. Negative numbers aren't allowed in the question posed above, technically.
Is there any way to use the Extended Euclidean Algorithm to solve this problem such that we have X' and Y' BOTH positive? Or is it not possible using the Algorithm this way?
No comments:
Post a Comment