1
$\begingroup$

This problem is in a chapter on the Greatest Common Divisor: The Euclidean Algorithm. Apparently I managed to arrive at one of the 3 possible solutions.

Problem goes 'man at a casino wins \$1020 in \$20 and 50 \$chips. if he has more \$50 than \$20 chips, how many chips of each denomination could he possibly have?'

To solve the problem I tried:

$$\gcd(20,50) = 10$$

so $20x + 50y = 10$

$$20(3) + 50(-1) = 10$$

so $20(306 - 50k) + 50(-102 + 20k) = 1020$

solved for $k$: must be $5.1\le k \le 6.12$ so one solution is if $k=6$ then $x=6$, $y=18$. (this is one of the solutions). there are two other solutions provided. not sure how to arrive at those. thanks.

$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

Hint $\ $ By linearity, the general solution of $\ 20x + 50y = n\ $ arises by adding to any particular solution the general solution of the associated homogeneous equation $\, 20x + 50 y = 0,\,$ which is $\, (x,y) = (5n,-2n),\,$ by $\,\frac{y}x = \frac{\!\!\!-20}{50} = \frac{\!\!\!-2}5.\,$ So all other solutions arise by repeatedly adding or subtracting $\,(5,-2)\,$ to solution $\,(6,18),\,$ yielding further only $\,(1,20),\,(11,16)\,$ in your range $$\ \ \ \ \color{#0a0}{\ldots,(-4,22)},(1,20),(6,18),(11,16),\color{#c00}{(16,14),\ldots}$$ since further subtraction makes $\,\color{#0a0}{y < 0},\,$ further addition makes $\, \color{#c00}{x > y}$.

$\endgroup$
1
  • $\begingroup$ For a geometric viewpoint see the Key Idea in this post on the Frobenius Coin Problem. $\ \ $ $\endgroup$ Commented May 7 at 22:49
0
$\begingroup$

$50x+20y = 1020 \implies 5x+2y = 102$. Take $\pmod 2 \implies x = 2k$. Then $5k+y = 51$. Take $\pmod 5$ so $y = 5j+1$. Then $k+j = 10$ which parameterizes all solutions. Then just pick the ones based on your restrictions.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.