Straight Dope Message Board > Main Solving equations when variables are constrained to be integers.
 Register FAQ Calendar Mark Forums Read

#1
08-13-2002, 05:45 PM
 Podkayne Guest Join Date: Aug 1999
Solving equations when variables are constrained to be integers.

One frequently encounters puzzles that involve equations that would be trivial (or underdetermined) except that the variables are constrained to be integers.

Just to take a dry and boring example: I need to amass \$167 in twenties, tens, fives, and singles, using a total of exactly 30 bills. How many of each bill will I need?

So we have the equations:

20a + 10b + 5c + d=167
a+b+c+d=30

Is there a rigorous way to apply the constraint that a,b,c, and d must be integers, or must one resort ot guesswork?
I've seen lots of puzzles like this, and it seems like there ought to be a good way to tackle it, but I've never seen one.

(No, this is not homework. But if you are at all suspicious, make up your own system of equations to solve.)
#2
08-13-2002, 05:53 PM
 audiobottle Guest Join Date: Oct 2001
Just divide the number by the largest bill denomination and then drop the remainder. Then subtract the number you get from the total and divide the resulting answer by the next highest denomination. So for your question:
167 / 20 = 8 (so 8 \$20)
167- 160 = 7
7 / 10 = 0 (so 0 \$10)
7 - 0 = 7
7 / 5 = 1 (so 1 \$5)
7 - 5 = 2
2 / 1 = 2 (so 2 \$1)

so 8 \$20, 1 \$5, and 2 \$1. Of course, this isn't the only answer to the question, but it gives you the least number of bills needed.
I'm not sure if this is what you're looking for, but hey, I thought I'd just get things started.

Audiobottle
#3
08-13-2002, 05:56 PM
 DarrenS Guest Join Date: Mar 2000
These are known as Diophantine equations.
#4
08-13-2002, 06:07 PM
 audiobottle Guest Join Date: Oct 2001
Wait... sorry. I totally missed the point of this post.
I take back everything I said, and I will now go think about this in the corner where I belong.

Audiobottle
#5
08-14-2002, 12:13 AM
 Omphaloskeptic Guest Join Date: Oct 2001
As DarrenS says, these are Diophantine equations, for which no general solution algorithm exists. (Fermat's Last Theorem contains an example of a difficult Diophantine equation.). But your example, at least, is a system of linear Diophantine equations, which is not as hard as the general case. (In fact it's a solution of linear Diophantine equations together with the constraint that the variables be nonnegative.)

I started to type up a detailed solution, but it was getting long. Instead, here's a short, and somewhat incoherent, version of a solution algorithm (note, it is more complicated than the playing-around solution for any likely puzzle-type problem, but I think it works for the general case).

First, solve the solution without the integer constraint. In this case, the solution is a plane in four dimensions. Find rational basis vectors for this plane (this can always be done because the original equations had integer coefficients).

Next, add the integer constraint. This reduces the solution space to a lattice in the plane. The basis vectors are the basis vectors found above, rescaled to be integer vectors. Then, to find a base point on the lattice, solve the underdetermined system to give one equation (in more than one variable). Finding a single solution to this equation is pretty easy to do inductively.

Finally, add the constraint of nonnegativity. This constrains all of the solutions (in the plane found above) to lie in a convex region in the plane. Find the minimum and maximum value achieved for one variable (say, a) in this region, and try each possibility in this range for a. This gives a lower-dimensional set of equations, and we can solve these by the same method.
#6
08-14-2002, 03:26 AM
 Achernar Guest Join Date: Aug 1999
Okay, so the general solution is iffy. That's what makes it a puzzle, after all. But you can still be mathematical about your "playing around" solution. Here's an algorithm of sorts, that I imagine would work in some similar situations. It's not a good or reliable algorithm, though, so I know it's not what the OP's looking for.

First off, I notice that d mod 5 = 2, so let me define f such that d = 5f + 2. This is where the constraint of integers comes in handy. You can then substitute, divide, and combine equations to get:

b = 5 + 4f - 3a

This equation should be small enough to wrap your mind around. But you still have to guess, say, a and f. (a, f) = (3, 3) gives you the solution (a, b, c, d) = (3, 8, 2, 17). (a, f) = (0, 0) gives (0, 5, 23, 2). I think as long as you pick numbers such that f is reasonably small, and b is positive, it's easy to find a solution.
#7
08-14-2002, 09:24 AM
 Podkayne Guest Join Date: Aug 1999
Thanks for the effort, audiobottle. You provided a perfectly adequate solution for the problem I posed--if I were are mathematician, I would never have been so sloppy, and would have said explicitly that I wanted all possible solutions in the problem itself.

Thank you for the keyword, Darren and Omphaloskeptic . . . Omphalos, (love your userid . . . hee hee . . . . belly button), I might just work through it as you describe, for the fun of it. (How can you tell when Pod is supposed to be working on her thesis? When she's spending an inordinate amount of time working silly math puzzles!)

The approach I was fiddling with last night was basically what Achernar suggested, but I was trying to just blindly turn the crank on an algorithm instead of thinking about it intelligently.

Here's how I was doing it, in case anyone's interested:

20 a + 10 b + 5 c + d =167
5 ( 4 a + 2 b + c) = 167 - d
4 a + 2 b + c = (167 -d ) / 5
4 a + 2b + c = (165 + 2 -d ) / 5
4 a + 2b + c = 33 + (2 -d ) / 5

So 2 - d = 5 i, where i is an integer (may be positive or negative). This is Achernar's constraint.

4 a + 2 b + c = 33 + i
2 ( 2a + b) = 33 + i - c
2 a + b= (32 + 1 +i - c) / 2
2 a + b = 16+ (1 + i - c) / 2

So 1 + i - c = 2 j .

2 a = 16 + j - b
a = 8 + (j - b) / 2

j - b = 2 k

And so forth . . . Then I substituted into a + b + c + d = 30 to get an equation in terms of i, j, and k, and that's when I was tired and had to go to bed.

Anyway, thank you everyone!
#8
08-14-2002, 09:36 AM
 Podkayne Guest Join Date: Aug 1999
Just noticed that my method makes a lot more sense if you notice that to satisfy 2 - d = 5 i for positive integer d, i must be a negative, and it works a lot better to rewrite it as 4 a + 2 b + c =33 -i, where 2 - d = - 5 i.
#9
08-14-2002, 09:50 AM
 Achernar Guest Join Date: Aug 1999
Yeah, you know, I'm rather interested in Omphaloskeptic's method too. Do you mind if we do it here? I think I did most of the brute work, but I get stuck at the end:

First, solve the solution without the integer constraint.

Let's let a and b be free variables, and c and d be the parameters:

c = -19/4 a - 9/4 b + 137/4
d = 15/4 a + 5/4 b - 17/4

I don't know what the equation of a plane in 4-space looks like. I guess that's it...?

Find rational basis vectors for this plane

The simplest ones would be what you get if you increment a and b, I think:

<1, 0, -19/4, 15/4>
<0, 1, -9/4, 5/4>

Next, add the integer constraint. This reduces the solution space to a lattice in the plane. The basis vectors are the basis vectors found above, rescaled to be integer vectors.

<4, 0, -19, 15>
<0, 4, -9, 5>

Then, to find a base point on the lattice, solve the underdetermined system to give one equation (in more than one variable). Finding a single solution to this equation is pretty easy to do inductively.

19a + 9b + 4c = 137

I'm not much good at Algebra, but this doesn't look too easy. A small amount of playing gets me (a, b, c) = (3, 0, 20), so our base point will be (3, 0, 20, 7)? I know that's a solution, but suppose we didn't want to stop there. If I add the second basis vector I get (3, 4, 11, 12), another solution. I guess I'm not clear on what happens at this point.
#10
08-14-2002, 10:37 AM
 SmackFu Guest Join Date: Sep 2000
Martin Gardner did a SciAm article on this that I thought was quite good, collected in his book Wheels, Life and Other Mathematical Amusements. It was years ago and I don't remember the details, but I recall it all made sense at the time.
#11
08-14-2002, 10:38 AM
 Podkayne Guest Join Date: Aug 1999
Hmmm, I guess I didn't read Achernar's post very carefully, because they way I pictured solving it was immediately eliminating d, leaving the three-dimensional plane 19 a + 9 b+ 4 c + 137. Then use audiobottle's solution as a starting point. Then you can use the base vector whoosis (I know I've done that at some point in math class . . . ) to step from that solution to all the other solutions, avoiding those that are not in the part of the planet where a and b and c are > 0.
#12
08-14-2002, 10:44 AM
 Orbifold Guest Join Date: Oct 2000
Another general technique for linear eqns in integer variables

Quote:
 Originally posted by Achenar 19a + 9b + 4c = 137 I'm not much good at Algebra, but this doesn't look too easy.
Modular arithmetic is a good way to tackle equations like this. For example, if I reduce the above equation modulo 19 I get:

9b + 4c = 4 mod 19 1

I chose 19 because it was a prime and appeared prominently on the left-hand side, and because gcd(19,9)=1. If the equation is in lowest terms and has an integer solution at all, then there will be some prime which divides one coeffecient but not another; choose that prime. Now notice that 2*9=-1 mod 19, so I can multiply everything by 2 and simplify to get:

8c - 8 = b mod 19

or in other words,

b = 8c - 8 + 19k for some integer k.

Substitute back into the original equation to get

19a + 72c - 72 + 171k + 4c = 137

Simplifying and dividing by 19, we get:

a + 4c + 9k = 11

So the general integer solution to the original equation is as follows:

a = 11 - 4c - 9k
b = 8c + 19k - 8
c = c

Where c and k are any integers. If you want positive integer solutions, you have to pick c and k such that c > 0, 8c + 19k > 8, and 4c + 9k < 11. Achenar's first solution corresponds to c=20, k=-8.

1I'm using an equality symbol to denote congruence because the symbol font doesn't show up properly on my browser. Sorry.
#13
08-14-2002, 11:49 AM
 ultrafilter Guest Join Date: May 2001
Not that it matters, but audiobottle's algorithm won't work for arbitrary sets of denominations. Put in a \$12 bill and try to get the minimal number of bills for \$15 using that method, and you'll see it fails.
#14
08-14-2002, 11:55 AM
 ftg Guest Join Date: Feb 2001
Just following up Omphaloskeptic's post:

Finding a optimal solution to a set of bounded linear equations is linear programming. Solvable in poly time. The integer version is NP-Complete. I therefore wonder if Omphaloskeptic's method might be exponential time in general.

In general, finding if a real-valued solution exists for an (possibly quantified) equation is easier than determining if an integer one exists. The opposite of what one might naively think.
#15
08-14-2002, 03:09 PM
 Omphaloskeptic Guest Join Date: Oct 2001
Quote:
 Originally posted by ftg Just following up Omphaloskeptic's post: Finding a optimal solution to a set of bounded linear equations is linear programming. Solvable in poly time. The integer version is NP-Complete. I therefore wonder if Omphaloskeptic's method might be exponential time in general.
I wondered about this a little. Last night I thought it was polynomial-time, but now I think you might be right. The original problem is not an optimization, as integer programming is, which might make it easier. (The goal is just to find a solution, not the best solution.)

The time complexity: Finding rational basis vectors for the plane can be done with a matrix inversion in O(n3). Rescaling these to integer basis vectors is O(n). Finding a base point for the lattice I think can be done in O(n2).

What's left, finding a lattice point in a bounded, convex region, is like integer programming but without the optimization requirement. Finding the minimum and maximum values of a given coordinate is just linear programming, so it's polynomial-time. There may be a lot of integers between the minimum and maximum, though, so stepping through them is not necessarily polynomial-time.

There might be a way around this. I'll have to think about it some more.
#16
08-14-2002, 03:41 PM
 Podkayne Guest Join Date: Aug 1999
I just noticed that audiobottle's solution also uses only 11 bills.

Anyway, I've come up with a solution that's good enough for a physicist. : )

Take the equations I found above, but with i, j, and k defined to be positive (I leave working out all the signs as an exercise for the reader):

d= 2 + 5 i
c = 1 - i + 2 j
b = 2 k - j
a = 8 - k

Plug these in to the equation a + b + c + d = 30 to get

4 i + j + k = 19

From this, we can derive an extra constraint from the requirement that i, j , and k be positive integers, using the same method as above:

i = (19 - j - k ) / 4
i = (16 + 3 - j - k) /4
i = 4 + (3 - j - k ) / 4

Since (3 - j - k) mod 4 must be zero, this gives us i <= 4. Notice also that the equation a = 8 - k gives us k <= 8.

Now, substitute j = 19 - 4 i - k in the equations above:

a = 8 - k
b = 3 k + 4 i -19
c = 39 - 9 i - 2 k
d = 2 + 5 i

Now we have just two variables: i & k , and we know the possible ranges for these, so I just wrote a little computer program to step through the values for i and k, and reject anything that yeilds a negative number for a, b, c, or d. (This is IDL, but the code is quite simple).

for i=0,4 do begin
for k=0,8 do begin
a=8-k
b=3*k-19+4*i
c=39 - 9*i -2*k
d=2+5*i
if ((a ge 0) and (b ge 0) and (c ge 0) and (d ge 0)) then print, a," Twenties, ", b, " Tens, ", c, " Fives, ",d, " Ones "
endfor
endfor

Here are the results:

1 Twenties, 2 Tens, 25 Fives, 2 Ones
0 Twenties, 5 Tens, 23 Fives, 2 Ones
3 Twenties, 0 Tens, 20 Fives, 7 Ones
2 Twenties, 3 Tens, 18 Fives, 7 Ones
1 Twenties, 6 Tens, 16 Fives, 7 Ones
0 Twenties, 9 Tens, 14 Fives, 7 Ones
4 Twenties, 1 Tens, 13 Fives, 12 Ones
3 Twenties, 4 Tens, 11 Fives, 12 Ones
2 Twenties, 7 Tens, 9 Fives, 12 Ones
1 Twenties, 10 Tens, 7 Fives, 12 Ones
0 Twenties, 13 Tens, 5 Fives, 12 Ones
5 Twenties, 2 Tens, 6 Fives, 17 Ones
4 Twenties, 5 Tens, 4 Fives, 17 Ones
3 Twenties, 8 Tens, 2 Fives, 17 Ones
2 Twenties, 11 Tens, 0 Fives, 17 Ones
7 Twenties, 0 Tens, 1 Fives, 22 Ones

Let me know if I've missed any.

 Bookmarks

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Main     About This Message Board     Comments on Cecil's Columns/Staff Reports     Straight Dope Chicago     General Questions     Great Debates     Elections     Cafe Society     The Game Room     In My Humble Opinion (IMHO)     Mundane Pointless Stuff I Must Share (MPSIMS)     Marketplace     The BBQ Pit Side Conversations     The Barn House

All times are GMT -5. The time now is 07:56 PM.