12
$\begingroup$

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
    This is known as the coin-changing problem, and in general the solution need not exist and may not be unique.2010-12-02
  • 1
    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 http://en.wikipedia.org/wiki/Euclidean_algorithm#Linear_Diophantine_equations You are interested in positive solutions. Solutions only exist if gcd(a,b) |c.2010-12-02
  • 0
    here gcd(4,9)=1 so you will have solutions for any area. Whether or not they are positive is another matter.2010-12-02

2 Answers 2

13

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

  • 0
    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.2010-12-02
  • 0
    Yes. All numbers involved are integers, so the mod makes sense.2010-12-02
  • 1
    @Michael: I agree with you that it is not immediately obvious why using modulo like this works: To me, learning about modular arithmetic (http://en.wikipedia.org/wiki/Modular_arithmetic), as this is called, was what convinced me that group theory is a useful tool.2010-12-02
  • 8
    Just in case anyone else is as confused as I was for a while: "b/c" here means "because", not "b divided by c"...2010-12-02
7

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