2
$\begingroup$

I have 50 coins. They add up $10. They are comprised of 10 cent, 20 cent and 50 cent coins. How many combinations are possible?

I tried making equations and etc.

x + 2y + 5z = 100 cents
x + y + z = 50
y + 4z = 50 cents
x = 3z

However I don’t know what to do next. I’m expecting a quartic or some sort of polynomial, because there should be multiple combinations possible. However I don’t know how to go about finding it.

$\endgroup$
6
  • $\begingroup$ Regarding your comment about quartic polynomials, three equations in three variables, where no equation is a linear combination of the other two (i.e linearly independent) will always give you a unique value of $x,y,z$. Having more than three equations will still give you a unique solution, but one or more of the equations will be redundant. Having only one or two equations will give you a solution in terms of a parameter, which is not unique. $\endgroup$
    – Toby Mak
    Jul 30 '20 at 9:57
  • $\begingroup$ This is nearly the same problem :math.stackexchange.com/questions/3724627/… $\endgroup$ Jul 30 '20 at 9:58
  • $\begingroup$ In this question, equation $(3)$ is a linear combination of the other equations, specifically $(1) - (2)$. Equation $(4)$ is not necessarily true. If you want to get more in-depth, the study of linear equations is called linear algebra. $\endgroup$
    – Toby Mak
    Jul 30 '20 at 9:59
  • $\begingroup$ @TobyMak I don't think the OP tried to relate the equations. He made them in desperate attempt to reduce the problems complexity. $\endgroup$ Jul 30 '20 at 10:00
  • $\begingroup$ @AnindyaPrithvi While the questions may look similar, I don't agree that this question is a duplicate. The added condition that $x+y+z$ allows us to find the number of solutions to this equation, which is not mentioned in the duplicate links. In addition, the answer there is way too complex compared to this question. $\endgroup$
    – Toby Mak
    Jul 30 '20 at 10:01
4
$\begingroup$

INTUITIVE APPROACH

First you can notice that $50$ coins of $20$c give you $10$\$. So you have at least one possibility. The other possibilities can be obtained from this one thinking that you have to change some of these $20$c coins in $10$c and $50$c coins. To be clearer you are allowed to change $n$ coins of $20$c, with $p$ coins of $10$c and $q$ coins of $50$c such that $p+q=n$ (the total number of coins is fixed) and the value of the $n$ coins of $20$c must be equal to the one obtained with the new coins. The minimum amount of coins $n$ that you can change is $4$. Indeed $4$ coins of $20$c are equivalent to $3$ coins of $10$c and $1$ coin of $50$p. Actually all the possible change you can make must be multiple of $n=4$. So you have $n=4$, $n=8$, $n=12$ and so on, up to $n=48$ (since $n\leq 50$). This means that you have $12$ possibilities. Adding the initial solution of only $20$c coins you get that there are $13$ possible combinations.

RIGOROUS APPROACH

Let $x$ be the number of $10$c coins, $y$ of $20$c and $z$ of $50$c. You are looking for the non-negative integer solutions of the system $$10x+20y+50z=1000\,;$$ $$x+y+z=50\,.$$

The solutions are in the form $$x=\frac{3}{4}(50-y)\,;\qquad z=\frac{1}{4}(50-y)\,.$$ So you are looking for the number of integer $y$ between $0$ and $50$ such that $50-y = 0\mod 4$. So how many $y\in\{0\dots 50\}$ such that $y\mod 4 = 2$? There are $13$ such $y$, precisely given by $$y = 2+4k$$ with $k=0\dots 12$.

$\endgroup$
2
  • 1
    $\begingroup$ Thank you! Great explanation. $\endgroup$
    – Subbota
    Jul 31 '20 at 8:15
  • $\begingroup$ @Subbota You can thank additionally ECL by accepting the answer. $\endgroup$ Aug 10 '20 at 16:37
1
$\begingroup$

$y+4z=50$ means that $4z\le 50$, so there are $13$ possible values for $z$. That's all you need, because given $z$, we are forced to choose $x=3z$ and $y=50-4z$. It is easy to check then that these values satisfy your first two equations.

$\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.