# Solving equations when variables are constrained to be integers.

**URL:** <https://boards.straightdope.com/t/solving-equations-when-variables-are-constrained-to-be-integers/123752>\
**Category:** Factual Questions\
**Created:** [August 13, 2002, 9:45pm UTC](https://boards.straightdope.com/t/solving-equations-when-variables-are-constrained-to-be-integers/123752 "2002-08-13T21:45:26Z")\
**Posts on this page:** 16\
**Page:** 1

<div class="post-metadata">

**Author:** ![Podkayne](https://avatars.discourse-cdn.com/v4/letter/p/edb3f5/32.png) [@Podkayne](https://boards.straightdope.com/u/Podkayne)\
**Post date:** [August 13, 2002, 9:45pm UTC](https://boards.straightdope.com/t/solving-equations-when-variables-are-constrained-to-be-integers/123752/1 "2002-08-13T21:45:26Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![audiobottle](https://avatars.discourse-cdn.com/v4/letter/a/bc8723/32.png) [@audiobottle](https://boards.straightdope.com/u/audiobottle)\
**Post date:** [August 13, 2002, 9:53pm UTC](https://boards.straightdope.com/t/solving-equations-when-variables-are-constrained-to-be-integers/123752/2 "2002-08-13T21:53:20Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![DarrenS](https://avatars.discourse-cdn.com/v4/letter/d/977dab/32.png) [@DarrenS](https://boards.straightdope.com/u/DarrenS)\
**Post date:** [August 13, 2002, 9:56pm UTC](https://boards.straightdope.com/t/solving-equations-when-variables-are-constrained-to-be-integers/123752/3 "2002-08-13T21:56:27Z")

</div>

These are known as [Diophantine](http://mathworld.wolfram.com/DiophantineEquation.html) equations.

---

<div class="post-metadata">

**Author:** ![audiobottle](https://avatars.discourse-cdn.com/v4/letter/a/bc8723/32.png) [@audiobottle](https://boards.straightdope.com/u/audiobottle)\
**Post date:** [August 13, 2002, 10:07pm UTC](https://boards.straightdope.com/t/solving-equations-when-variables-are-constrained-to-be-integers/123752/4 "2002-08-13T22:07:04Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\
**Post date:** [August 14, 2002, 4:13am UTC](https://boards.straightdope.com/t/solving-equations-when-variables-are-constrained-to-be-integers/123752/5 "2002-08-14T04:13:53Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\
**Post date:** [August 14, 2002, 7:26am UTC](https://boards.straightdope.com/t/solving-equations-when-variables-are-constrained-to-be-integers/123752/6 "2002-08-14T07:26:17Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Podkayne](https://avatars.discourse-cdn.com/v4/letter/p/edb3f5/32.png) [@Podkayne](https://boards.straightdope.com/u/Podkayne)\
**Post date:** [August 14, 2002, 1:24pm UTC](https://boards.straightdope.com/t/solving-equations-when-variables-are-constrained-to-be-integers/123752/7 "2002-08-14T13:24:24Z")

</div>

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!

---

<div class="post-metadata">

**Author:** ![Podkayne](https://avatars.discourse-cdn.com/v4/letter/p/edb3f5/32.png) [@Podkayne](https://boards.straightdope.com/u/Podkayne)\
**Post date:** [August 14, 2002, 1:36pm UTC](https://boards.straightdope.com/t/solving-equations-when-variables-are-constrained-to-be-integers/123752/8 "2002-08-14T13:36:08Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\
**Post date:** [August 14, 2002, 1:50pm UTC](https://boards.straightdope.com/t/solving-equations-when-variables-are-constrained-to-be-integers/123752/9 "2002-08-14T13:50:26Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![SmackFu](https://avatars.discourse-cdn.com/v4/letter/s/53a042/32.png) [@SmackFu](https://boards.straightdope.com/u/SmackFu)\
**Post date:** [August 14, 2002, 2:37pm UTC](https://boards.straightdope.com/t/solving-equations-when-variables-are-constrained-to-be-integers/123752/10 "2002-08-14T14:37:33Z")

</div>

Martin Gardner did a SciAm article on this that I thought was quite good, collected in his book [Wheels, Life and Other Mathematical Amusements](http://www.amazon.com/exec/obidos/ASIN/0716715899/102-3529055-0323316). It was years ago and I don’t remember the details, but I recall it all made sense at the time.

---

<div class="post-metadata">

**Author:** ![Podkayne](https://avatars.discourse-cdn.com/v4/letter/p/edb3f5/32.png) [@Podkayne](https://boards.straightdope.com/u/Podkayne)\
**Post date:** [August 14, 2002, 2:38pm UTC](https://boards.straightdope.com/t/solving-equations-when-variables-are-constrained-to-be-integers/123752/11 "2002-08-14T14:38:00Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Orbifold](https://avatars.discourse-cdn.com/v4/letter/o/779978/32.png) [@Orbifold](https://boards.straightdope.com/u/Orbifold)\
**Post date:** [August 14, 2002, 2:44pm UTC](https://boards.straightdope.com/t/solving-equations-when-variables-are-constrained-to-be-integers/123752/12 "2002-08-14T14:44:49Z")

</div>

> [@](#):
>
> _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 [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.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [August 14, 2002, 3:49pm UTC](https://boards.straightdope.com/t/solving-equations-when-variables-are-constrained-to-be-integers/123752/13 "2002-08-14T15:49:54Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\
**Post date:** [August 14, 2002, 3:55pm UTC](https://boards.straightdope.com/t/solving-equations-when-variables-are-constrained-to-be-integers/123752/14 "2002-08-14T15:55:28Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\
**Post date:** [August 14, 2002, 7:09pm UTC](https://boards.straightdope.com/t/solving-equations-when-variables-are-constrained-to-be-integers/123752/15 "2002-08-14T19:09:15Z")

</div>

> [@](#):
>
> \*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(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.

---

<div class="post-metadata">

**Author:** ![Podkayne](https://avatars.discourse-cdn.com/v4/letter/p/edb3f5/32.png) [@Podkayne](https://boards.straightdope.com/u/Podkayne)\
**Post date:** [August 14, 2002, 7:41pm UTC](https://boards.straightdope.com/t/solving-equations-when-variables-are-constrained-to-be-integers/123752/16 "2002-08-14T19:41:55Z")

</div>

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.