0
$\begingroup$

Change machine contains n quarters, 2n nickels, 4n dimes, n positive integer. Find all values of n so that these coins total k dollars, k positive integer.

My thinking is to reduce coins to prime factors so quarter = $5^2$, nickel = $5$, dime = $2*5$.

$5^2n + 2*5n + 2^3*5n = k$

$\endgroup$
5
$\begingroup$

Consider the problem in cents.

You want $100k$ cents, for $k\geq 1$. Given $n$, the change machine contains $$\underbrace {25n}_{{\text{quarters}}} + \underbrace {5 \cdot 2n}_{{\text{nickels}}} + \underbrace {10 \cdot 4n}_{{\text{dimes}}} = 75n\,\,{\text{cents}}$$ Hence the question is what are the integer solutions to the equation $75n = 100k$ for $k \geq 1$.

Ordinarily you would use the techniques for first-order Diophantine equations, but this one is simple enough to simply observe that $3n = 4k$, hence $n$ must be a positive multiple of $4$.

$\endgroup$
  • $\begingroup$ Thanks. My next thought was to think in terms of cents. $\endgroup$ – miniparser Aug 14 '14 at 14:13
  • $\begingroup$ Care to elaborate on solving it as a Diophantine equation? I think I know the method for doing that. Thanks. $\endgroup$ – miniparser Aug 15 '14 at 19:30
  • $\begingroup$ mathworld.wolfram.com/DiophantineEquation.html $\endgroup$ – COTO Aug 15 '14 at 19:50
0
$\begingroup$

Solve Diophantine equation $3x + -4y=0, y\ge1$

attempt:

$gcd(3,-4) = 1$; $3(-1) + -4(-1) = 1$; $3(-1)(0) + -4(-1)(0) = (1)(0)$;(multiply through by c)

$3(-1)(0) + -4(-1)(0) + (3)(-4)k - (3)(-4)k = (1)(0)$;(+/- $abk$)

$3((-1)(0)+(-4)k) + -4((-1)(0) - (3)k) = (1)(0)$; (factor out $a,b$ from $k$ , etc.)

k must be $\le-1$ for $(-1)(0)-(3)k$ to be $\ge1$ so yes $x$ is positive multiple of 4.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.