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); 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.
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 that lays out a step-by-step procedure for solving linear Diophantine equations of the form ax + by = c.
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, 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.
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.
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.
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.
