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?

  • 7
    $\begingroup$ This is known as the coin-changing problem, and in general the solution need not exist and may not be unique. $\endgroup$ – Yuval Filmus Dec 2 '10 at 6:14
  • 1
    $\begingroup$ 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. $\endgroup$ – AnonymousCoward Dec 2 '10 at 6:14
  • $\begingroup$ here gcd(4,9)=1 so you will have solutions for any area. Whether or not they are positive is another matter. $\endgroup$ – AnonymousCoward Dec 2 '10 at 6:21

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

  • $\begingroup$ 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. $\endgroup$ – Michael Dorgan Dec 2 '10 at 6:35
  • $\begingroup$ Yes. All numbers involved are integers, so the mod makes sense. $\endgroup$ – TCL Dec 2 '10 at 7:02
  • 1
    $\begingroup$ @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. $\endgroup$ – Janus Dec 2 '10 at 7:33
  • 8
    $\begingroup$ Just in case anyone else is as confused as I was for a while: "b/c" here means "because", not "b divided by c"... $\endgroup$ – 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$.


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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.