# Infinitely many solutions. How to find the solutions that are whole number. **URL:** \ **Category:** Factual Questions\ **Created:** [March 2, 2013, 6:47pm UTC](https://boards.straightdope.com/t/infinitely-many-solutions-how-to-find-the-solutions-that-are-whole-number/651841 "2013-03-02T18:47:13Z")\ **Posts on this page:** 10\ **Page:** 1
**Author:** ![chowching](https://avatars.discourse-cdn.com/v4/letter/c/f14d63/32.png) [@chowching](https://boards.straightdope.com/u/chowching)\ **Post date:** [March 2, 2013, 6:47pm UTC](https://boards.straightdope.com/t/infinitely-many-solutions-how-to-find-the-solutions-that-are-whole-number/651841/1 "2013-03-02T18:47:13Z")
Suppose there is a big bus containing 100 passengers. A passenger is distinguished as an adult, a student, or a child. The bus fare for an adult is 500. The bus fare for a student is 100. The bus fare for a child is 25. The total fare of the 100 passengers is 10,000. How many adult, student, and child are there? I can only make two equations and there are three unknowns so there must be infinitely many solutions. I let x = no. of adults , y = no. of students, z = no. of children so x + y + z = 100 and 500x + 100y + 25z =10000 After eliminating one variable and letting z = a I have: z = a x = 3a/16 y = 100 - 19a/16 Is there a way do determine what values of a will give whole number values for x and for y if there is any? I could limit the possible values of z between zero and 100 based on the problem. I could check the values one by one but is there a shorter way how to do this? Thanks. ---
**Author:** ![Andy\_L](https://avatars.discourse-cdn.com/v4/letter/a/c67d28/32.png) [@Andy\_L](https://boards.straightdope.com/u/Andy_L)\ **Post date:** [March 2, 2013, 6:59pm UTC](https://boards.straightdope.com/t/infinitely-many-solutions-how-to-find-the-solutions-that-are-whole-number/651841/2 "2013-03-02T18:59:19Z")
> [@chowching](#): > > Suppose there is a big bus containing 100 passengers. > A passenger is distinguished as an adult, a student, or a child. > The bus fare for an adult is 500. > The bus fare for a student is 100. > The bus fare for a child is 25. > The total fare of the 100 passengers is 10,000. > How many adult, student, and child are there? > > I can only make two equations and there are three unknowns so there must be infinitely many solutions. > I let x = no. of adults , y = no. of students, z = no. of children > so x + y + z = 100 > and 500x + 100y + 25z =10000 > After eliminating one variable and letting z = a I have: > z = a > x = 3a/16 > y = 100 - 19a/16 > > Is there a way do determine what values of a will give whole number values for x and for y if there is any? I could limit the possible values of z between zero and 100 based on the problem. I could check the values one by one but is there a shorter way how to do this? Thanks. This is one of a class of equations called Diophantine equations ([Diophantine equation - Wikipedia](http://en.wikipedia.org/wiki/Diophantine_equation)); I don’t know if there is a general way to solve them, except by trial and error, but the links in the article I cited might help. ---
**Author:** ![Giles](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/giles/32/60_2.png) [@Giles](https://boards.straightdope.com/u/Giles)\ **Post date:** [March 2, 2013, 7:09pm UTC](https://boards.straightdope.com/t/infinitely-many-solutions-how-to-find-the-solutions-that-are-whole-number/651841/3 "2013-03-02T19:09:12Z")
With the given problem, there are multiple solutions: 0 adults, 100 students, 0 children 3 adults, 81 students, 16 children 6 adults, 62 students, 32 children 9 adults, 43 students, 48 children 12 adults, 24 students, 64 children 15 adults, 5 students, 80 children ---
**Author:** ![yearofglad](https://avatars.discourse-cdn.com/v4/letter/y/b782af/32.png) [@yearofglad](https://boards.straightdope.com/u/yearofglad)\ **Post date:** [March 2, 2013, 7:10pm UTC](https://boards.straightdope.com/t/infinitely-many-solutions-how-to-find-the-solutions-that-are-whole-number/651841/4 "2013-03-02T19:10:47Z")
> [@chowching](#): > > Suppose there is a big bus containing 100 passengers. > A passenger is distinguished as an adult, a student, or a child. > The bus fare for an adult is 500. > The bus fare for a student is 100. > The bus fare for a child is 25. > The total fare of the 100 passengers is 10,000. > How many adult, student, and child are there? > > I can only make two equations and there are three unknowns so there must be infinitely many solutions. > I let x = no. of adults , y = no. of students, z = no. of children > so x + y + z = 100 > and 500x + 100y + 25z =10000 > After eliminating one variable and letting z = a I have: > z = a > x = 3a/16 > y = 100 - 19a/16 > > Is there a way do determine what values of a will give whole number values for x and for y if there is any? I could limit the possible values of z between zero and 100 based on the problem. I could check the values one by one but is there a shorter way how to do this? Thanks. Well, since z = a, you have to choose an integer value for a. Since x = 3a/16 and you want x to be an integer, 3a must be a multiple of 16. So you can just look at multiples of 16. ---
**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\ **Post date:** [March 2, 2013, 7:25pm UTC](https://boards.straightdope.com/t/infinitely-many-solutions-how-to-find-the-solutions-that-are-whole-number/651841/5 "2013-03-02T19:25:56Z")
> [@chowching](#): > > After eliminating one variable and letting z = a I have: > z = a > x = 3a/16 > y = 100 - 19a/16 The question has already been pretty well answered by the previous posters. You’ve already done the hard work yourself. From the above, it’s pretty obvious that, if you want x to be a whole number, you have to pick a value for a that’s a multiple of 16, as **yearofglad** noted. Any nonnegative value of a that doesn’t make y negative will yield a different solution, resulting in **Giles** ’s list. And yes, as **Andy L** noted, equations for which you’re only interested in whole number (or integer, or rational) solutions are called **Diophantine equations** , and are one of the topics of number theory. I did find [this WikiHow article](http://www.wikihow.com/Solve-a-Linear-Diophantine-Equation) that lays out a step-by-step procedure for solving linear Diophantine equations of the form ax + by = c. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 2, 2013, 9:46pm UTC](https://boards.straightdope.com/t/infinitely-many-solutions-how-to-find-the-solutions-that-are-whole-number/651841/6 "2013-03-02T21:46:01Z")
I don’t know if it’ll help the OP, but for the sake of completeness, I’ll note that there is an algorithm that will solve a system of linear Diophantine equations in polynomial time (but not strongly polynomial time). It’s detailed in [this paper](http://riot.ieor.berkeley.edu/~dorit/pub/lde.pdf), but it’s not incredibly simple. What’s pretty incredible is that this problem is right on the border of what we can reasonably compute. There is no polynomial time algorithm to solve a single quadratic Diophantine equation unless P = NP, and there is no algorithm at all to solve a system of quadratic Diophantine equations. ---
**Author:** ![chowching](https://avatars.discourse-cdn.com/v4/letter/c/f14d63/32.png) [@chowching](https://boards.straightdope.com/u/chowching)\ **Post date:** [March 3, 2013, 1:25am UTC](https://boards.straightdope.com/t/infinitely-many-solutions-how-to-find-the-solutions-that-are-whole-number/651841/7 "2013-03-03T01:25:09Z")
> [@yearofglad](#): > > Well, since z = a, you have to choose an integer value for a. > > Since x = 3a/16 and you want x to be an integer, 3a must be a multiple of 16. So you can just look at multiples of 16. Hah! Of course. That was rather easy. :smack: Thanks guys. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [March 3, 2013, 1:29am UTC](https://boards.straightdope.com/t/infinitely-many-solutions-how-to-find-the-solutions-that-are-whole-number/651841/8 "2013-03-03T01:29:36Z")
> [@](#): > > …and there is no algorithm at all to solve a system of quadratic Diophantine equations. I assume that you’re requiring that the algorithm be able to determine a lack of solutions if no solution exists? Because otherwise, you can just systematically step through all possible values of the variables until you find a solution. I.e., “Is x=0, y=0 a solution? No? OK, then, is x=0, y=1 a solution? No? OK, then, is x=1, y=0 a solution?”, etc. ---
**Author:** ![chowching](https://avatars.discourse-cdn.com/v4/letter/c/f14d63/32.png) [@chowching](https://boards.straightdope.com/u/chowching)\ **Post date:** [March 3, 2013, 1:30am UTC](https://boards.straightdope.com/t/infinitely-many-solutions-how-to-find-the-solutions-that-are-whole-number/651841/9 "2013-03-03T01:30:34Z")
> [@Andy\_L](#): > > This is one of a class of equations called Diophantine equations ([Diophantine equation - Wikipedia](http://en.wikipedia.org/wiki/Diophantine_equation)); I don’t know if there is a general way to solve them, except by trial and error, but the links in the article I cited might help. > [@Thudlow\_Boink](#): > > The question has already been pretty well answered by the previous posters. You’ve already done the hard work yourself. From the above, it’s pretty obvious that, if you want x to be a whole number, you have to pick a value for a that’s a multiple of 16, as **yearofglad** noted. Any nonnegative value of a that doesn’t make y negative will yield a different solution, resulting in **Giles** ’s list. > > And yes, as **Andy L** noted, equations for which you’re only interested in whole number (or integer, or rational) solutions are called **Diophantine equations** , and are one of the topics of number theory. I did find [this WikiHow article](http://www.wikihow.com/Solve-a-Linear-Diophantine-Equation) that lays out a step-by-step procedure for solving linear Diophantine equations of the form ax + by = c. > [@ultrafilter](#): > > I don’t know if it’ll help the OP, but for the sake of completeness, I’ll note that there is an algorithm that will solve a system of linear Diophantine equations in polynomial time (but not strongly polynomial time). It’s detailed in [this paper](http://riot.ieor.berkeley.edu/~dorit/pub/lde.pdf), but it’s not incredibly simple. > > What’s pretty incredible is that this problem is right on the border of what we can reasonably compute. There is no polynomial time algorithm to solve a single quadratic Diophantine equation unless P = NP, and there is no algorithm at all to solve a system of quadratic Diophantine equations. Thanks for this guys. I’ve heard about Diophantine equations in my number theory class. But I guess I did not try to study it at all. Seems interesting to me now. Thanks again. 🙂 ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 3, 2013, 2:06am UTC](https://boards.straightdope.com/t/infinitely-many-solutions-how-to-find-the-solutions-that-are-whole-number/651841/10 "2013-03-03T02:06:16Z")
> [@Chronos](#): > > I assume that you’re requiring that the algorithm be able to determine a lack of solutions if no solution exists? Because otherwise, you can just systematically step through all possible values of the variables until you find a solution. I.e., “Is x=0, y=0 a solution? No? OK, then, is x=0, y=1 a solution? No? OK, then, is x=1, y=0 a solution?”, etc. Yes. In computability theory, every problem is a yes/no question, and a solution is an algorithm that correctly answers yes or no for every instance of the problem. There are problems for which it’s always possible to recognize the instances where you should say yes–this is one, and the halting problem is another–and there are problems for which it’s always possible to recognize the instances where you should say no. There are other problems where you can’t do either, but those tend to be a little more esoteric.