# Stamps World Problem

• Mar 28th 2011, 06:55 PM
NOX Andrew
Stamps World Problem
George has a collection of old stamps. Some are worth 29 cents, the rest are worth a quarter. Their total value is \$5.02. How many 29 cent stamps does George have?

Let $x$ be the number of 29 cents stamps and let $y$ be the number of 25 cents stamps. Then,

$0.29x + 0.25y = 5.02$

Multiplying by 100 to rid the equation of decimals yields

$29x + 25y = 502$

Solving for x yields

$x = \dfrac{502 - 25y}{29}$

I know $x$ is an integer, so $\dfrac{502 - 25y}{29}$ is also an integer. I also know $502 - 25y$ is divisible by $29$ (else $x$ isn't an integer). How would I use this knowledge to find $x$?
• Mar 28th 2011, 08:15 PM
TKHunny
A little rewriting could be beneficial.

502 - 25y = 29*17 + 9 - 29y + 4y = 29(17 - y) + (9 + 4y)
• Mar 29th 2011, 04:23 AM
HallsofIvy
Since x and y must be integers, this is a "Diophantine" equation. There is a standard way of solving them.
29x+ 25y= 502.

25 divides into 29 once with remainder 4: 29- 25= 4. 4 divides into 25 6 times with remainder 1: 25- 6(4)= 1. Replacing that "4" by "29- 25", 25- 6(29- 25)= 7(25)- 6(29)= 1. Multiplying each side by 502, 3514(25)- 3012(29)= 502. One solution to that equation is x= -3012, y= 3514. Of course, here, each number must be positive so that does not satisfy this problem. However, for any integer, k, x= -3012+ 25k, y= 3514- 29k is also a solution: 29(-3012+ 25k)+ 25(3514- 29k)= 29(-3012)+ 29(25)k+ 25(3514)- 25(29)k and the terms involving k cancel.

25 divides into 3012 120 times so -3012+ 25(121)= 13 is positive. 29 divides into 3514 121 times so 3514- 29(121)= 5 is still positive. That is the only solution to the equation that has both x and y positive and so is the solution to this problem.
• Mar 29th 2011, 08:12 AM
Soroban
Hello, NOX Andrew!

Quote:

$\text{George has a collection of old stamps.}$
$\text{Some are worth 29 cents, the rest are worth a quarter.}$
$\text{Their total value is \5.02.}$
$\text{How many 29 cent stamps does George have?}$

$\text{Let: }\;\begin{Bmatrix}x &=& \text{number of 29-cent stamps} \\
y &=& \text{number of 25-cent stamps} \end{Bmatrix}$

$\text{Then: }\;29x + 25y \:=\: 502$

$\text{Solving for }x\!:\;\;x \:=\: \dfrac{502 - 25y}{29}$ .[1]

$\text{I know }x\text{ is an integer, so }502 - 25y\text{ is a multiple of 29}$

$\text{How would I use this knowledge to find }x\,?$

Here is a very primitive method . . .

We have: . $502 - 25y \:=\:29a\:\text{ for some integer }a.$

Solve for $y\!:\;\;y \;=\;\dfrac{502-29a}{25} \;=\;20 - a + \dfrac{2-4a}{25}$ .[2]

Since $\,y$ is an integer, $2-4a$ must be a multiple of 25.

Then: . $2 - 4a \:=\:25b\;\text{ for some integer }b.$

Solve for $\,a\!:\;\;a \;=\;\dfrac{2-25b}{4} \;=\;-6b + \dfrac{2-b}{4}$ .[3]

Since $\,a$ is an integer, $2-b$ must be a multiple of 4.

This happens when $b = -2$

Substitute into [3]: . $a \;=\;(\text{-}6)(\text{-}2) + \dfrac{2-(\text{-}2)}{4} \quad\Rightarrow\quad a \:=\:13$

Substitute into [2]: . $y \;=\;20-13 + \dfrac{2-4(13)}{25} \qud\Rightarrow\quad y \:=\:5$

Substitute into [1]: . $x \;=\;\dfrac{502-25(5)}{29} \quad\Rightarrow\quad x \:=\:13$

$\text{Therefore, George had: }\;\begin{Bmatrix}\text{thirteen 29-cent stamps} \\ \text{five 25-cent stamps} \end{Bmatrix}$