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