1. ## 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$\displaystyle x$be the number of 29 cents stamps and let$\displaystyle y$be the number of 25 cents stamps. Then,$\displaystyle 0.29x + 0.25y = 5.02$Multiplying by 100 to rid the equation of decimals yields$\displaystyle 29x + 25y = 502$Solving for x yields$\displaystyle x = \dfrac{502 - 25y}{29}$I know$\displaystyle x$is an integer, so$\displaystyle \dfrac{502 - 25y}{29}$is also an integer. I also know$\displaystyle 502 - 25y$is divisible by$\displaystyle 29$(else$\displaystyle x$isn't an integer). How would I use this knowledge to find$\displaystyle x$? 2. A little rewriting could be beneficial. 502 - 25y = 29*17 + 9 - 29y + 4y = 29(17 - y) + (9 + 4y) 3. 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. 4. Hello, NOX Andrew!$\displaystyle \text{George has a collection of old stamps.}\displaystyle \text{Some are worth 29 cents, the rest are worth a quarter.}\displaystyle \text{Their total value is \$5.02.}$
$\displaystyle \text{How many 29 cent stamps does George have?}$

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

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

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

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

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

Here is a very primitive method . . .

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

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

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

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

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

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

This happens when $\displaystyle b = -2$

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

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

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

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