# My Daughter's 4th grade math question got me thinking

Given a number of 3in squares and 2in squares, how many of each are needed to get a total area of 35 in^2?

Through quick trial and error (the method they wanted I believe) you find that you need 3 3in squares and 2 2in squares, but I got to thinking on how to solve this exactly.

You have 2 unknowns and the following info:

4x + 9y = 35

x >= 0, y >= 0, x and y are both integers.

It also follows then that x <= 8 and y <= 3

I'm not sure how to use the inequalities or the integer only info to form a direct 2nd equation in order to solve the system of equations. How would you do this without trial and error?

• This is known as the coin-changing problem, and in general the solution need not exist and may not be unique. – Yuval Filmus Dec 2 '10 at 6:14
• This is a linear diophantine equation $ax+by=c$. There are infinitely many solutions for x and y which you can find using the extended euclidean algorithm en.wikipedia.org/wiki/… You are interested in positive solutions. Solutions only exist if gcd(a,b) |c. – AnonymousCoward Dec 2 '10 at 6:14
• here gcd(4,9)=1 so you will have solutions for any area. Whether or not they are positive is another matter. – AnonymousCoward Dec 2 '10 at 6:21

## 2 Answers

A quick way to see the answer is to convert both sides of the equation mod 4. So the left hand side is y (mod 4) (because 4=0, 9=1 mod 4), and the right hand side is 3 (mod 4). So y=3 mod 4. Since $y\le 3$ as you observed, the only solution (if there is any ) is $y=3$. Then you check that $4x+27=35$ and hence $x=2$.

• You are allowed to mod as an operator? I thought that mod was only half of a divide operation and couldn't be seperated. Neat. I'll login under my Stack Overflow account tomorrow and give you credit for this nice answer. – Michael Dorgan Dec 2 '10 at 6:35
• Yes. All numbers involved are integers, so the mod makes sense. – TCL Dec 2 '10 at 7:02
• @Michael: I agree with you that it is not immediately obvious why using modulo like this works: To me, learning about modular arithmetic (en.wikipedia.org/wiki/Modular_arithmetic), as this is called, was what convinced me that group theory is a useful tool. – Janus Dec 2 '10 at 7:33
• Just in case anyone else is as confused as I was for a while: "b/c" here means "because", not "b divided by c"... – Hans Lundmark Dec 2 '10 at 9:14

There is an algorithmic way to solve this which works when you have two types of squares.

if $\displaystyle \text{gcd}(a,b) = 1$, then for any integer $c$ the linear diophantine equation $\displaystyle ax + by = c$ has an infinite number of solution, with integer $\displaystyle x,y$.

In fact if $\displaystyle x_0, y_0$ are such that $\displaystyle a x_0 - b y_0 = 1$, then all the solutions of $\displaystyle ax + by = c$ are given by

$\displaystyle x = -tb + cx_0$, $\displaystyle y = ta - cy_0$, where $\displaystyle t$ is an arbitrary integer.

$\displaystyle x_0 , y_0$ can be found using the Extended Euclidean Algorithm.

Since you also need $\displaystyle x \ge 0$ and $\displaystyle y \ge 0$ you must pick a $\displaystyle t$ such that

$\displaystyle c x_0 \ge tb$ and $ta \ge cy_0$.

If there is no such $\displaystyle t$, then you do not have a solution.

In your case, $\displaystyle a= 9, b= 4$, we need a solution of $\displaystyle ax + by = 35$.

We can easily see that $\displaystyle x_0 = 1, y_0 = 2$ gives us $\displaystyle a x_0 - by_0 = 1$.

Thus we need to find a $\displaystyle t$ such that $35 \ge t\times 4$ and $t\times 9 \ge 35\times 2$.

i.e.

$\displaystyle 35/4 \ge t \ge 35\times 2/9$

i.e.

$\displaystyle 8.75 \ge t \ge 7.77\dots$

Thus $t = 8$.

This gives us $\displaystyle x = cx_0 - tb = 3$, $\displaystyle y = ta- cy_0 = 2$.

(Note: I have swapped your x and y).