When I was about seven or eight years old, my grandfather gave me a math problem that took me many hours to solve.
The problem is this:
A movie theater made a total of 1 dollar (100 cents). The men cost 5 cents each, the women cost 2 cents each, and the children cost 1 cent for every 10 that were there. There were a total of 100 people in the movie theater. How many men were there? Women? Children?
Read the problem carefully. There is only one solution to this problem. Now if you want to try and solve it, go ahead, before continuing on with the rest of this blog post.
This problem has intrigued me ever since my grandfather challenged me many years ago. More specifically, I was curious to know if there is an algorithm that can solve this problem without trying every possible combination, or using some other brute force method. Regardless, I wrote a naive algorithm that solves it in O(n^3) time, which can be found here, written in Python. I then went to Reddit.com with my algorithm and question to see if anybody knows the answer.
There was, in fact, one person on Reddit who seems to know quite a bit about these problems. The member stated that this is a type of problem known as a Diophantine problem. His remarks:
In this case, your three independent lines of logic are:
1) 5*m + 2*w + 1*(c/10) = 100
2) m + w + c = 100
3) m, w, c are positive integers
This is a particular type of problem called a Diophantine problem because it requires the variables to be discrete integers. In school, you’re taught to solve for a three-variable system you need three algebraic equations… but this is not exactly true. What you really need are three independent lines of logic. It just happens that an linearly-independent algebraic equation is the easiest “line of logic” to be described mathematically.
That last line was pretty shocking. I’ve gone through life this whole time believing that if you have three unknowns, you need three algebraic equations to solve for each of the variables. The individual continues:
Check out section 5 of this paper. It has the solution to a problem very similar to yours (the only difference being that the women cost three cents instead of two).
I read the paper (only 10 pages), and it indeed describes, with much simplicity, how to solve these types of problems. I encourage you to check out section five. It is very interesting.
Now if we apply what we’ve learned to our problem above, we can solve it in O(n) time. Another Redditor took that advice and outlined the solution.
5m + 2w + .1c = 100
m + w + c = 100
Basically, since there is n-1 linear equations and n unknowns, that means there is one degree of freedom. That means that if we can find just one of the unknowns then we should be able to find the rest. I’m going to eliminate variables to find the line defining the search space.
Choosing to eliminate women, we have
5*m + 2*w+.1c=100
- 2(m+w+c=100)
____________________
3m-1.9c=-100
This line represents the ‘search space’ that we are trying to look for. Any solution on this line where c and m are both integers is our solution. Rearranging this line, we get
3m=1.9c-100
m=(1.9c-100.0)/3.0
Then, all you have to do is iterate over the possible range of the unknown variable c and find one that fits the contraint (e.g., provides a positive integer solution). Here’s my python solution.
for c in range(0,100, 10):
m=(1.9*c-100.0)/3.0
if(m.is_integer() && m > 0):
print m
this code printed out “11.0″. The next step is to plug in m=11.0 into our two equations, to get
55+2w+.1c=100
2w+.1c=45
and
11+w+c=100
w+c=89
Then, we are left with two linear equations in two unknowns, which is trivial to solve using 9th grade algebra. Our final solution is m=11,w=19,c=70
I hope you learned a little about Diophantine problems today and that it is possible to solve for three unknowns when you have three pieces of logic, but two equations.
A big thanks to the users of Reddit.com for their great help.