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, 2020 at 9:57
  • $\begingroup$ This is nearly the same problem :math.stackexchange.com/questions/3724627/… $\endgroup$ Jul 30, 2020 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, 2020 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, 2020 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, 2020 at 10:01

2 Answers 2

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, 2020 at 8:15
  • $\begingroup$ @Subbota You can thank additionally ECL by accepting the answer. $\endgroup$ Aug 10, 2020 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .