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?

Solution 1:

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$.

Solution 2:

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).