Solving equations when variables are constrained to be integers.

Factual Questions
1

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. :slight_smile: But if you are at all suspicious, make up your own system of equations to solve.)

2

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

These are known as Diophantine equations.

4

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

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

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

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. :slight_smile:

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

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

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

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

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

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 [sup]1[/sup]

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.

[sup]1[/sup]I’m using an equality symbol to denote congruence because the symbol font doesn’t show up properly on my browser. Sorry.

13

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

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

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(n[sup]3[/sup]). Rescaling these to integer basis vectors is O(n). Finding a base point for the lattice I think can be done in O(n[sup]2[/sup]).

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

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=3k-19+4i
c=39 - 9i -2k
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.