Thursday, April 24, 2008

very simple linear algebra puzzle

Since I intend to study operations research in my free time, I need to revisit a lot of the linear algebra material I had a better command of a while ago. That is essential to understanding the simplex and related algorithms. In Jim Hefferon's Linear Algebra, there is a really cute puzzle close to the beginning. It's so easy it's almost not worth mentioning, but I still had fun with it for a few minutes. Here it is:
Three truck drivers went into a roadside cafe. One truck driver purchased four sandwiches, a cup of coffee, and ten doughnuts for $8.45. Another driver purchased three sandwiches, a cup of coffee, and seven doughnuts for $6.30. What did the third truck driver pay for a sandwich, a cup of coffee, and a doughnut?
My solution was a bit different from the book's. The first two purchases can be represented as the linear equations and , respectively. They can be reduced to the linear combination . (I never thought of donuts as parameters. I guess I'm in for more surprises when I study topology.)

Anyway, with that knowledge, you can substitute into the equation with the unknown right-hand value (i.e., the cost of the third purchase) and so arrive at . The terms cancel out and so you are left with a constant: two dollars for the third trucker's purchase. Not a bad deal at all, to be honest. Notice that, even with the added constant, there is still a free variable in this system. As such, the menu items can assume infinitely many combinations of prices s.t. they are non-negative and very economical.

3 comments:

Hel. said...

Yeah, it's 4:58 am here now. I have just solved the puzzle. lol
Somehow, we began the same way and finished the same way. But I don't get how you got to that same final equation the way you did. You used combination. I would never think of using combination in such a situation. It probably makes it more complicated.

Epic Fail Guy said...

What steps did you take?

Using a linear combination really makes a lot of sense in this case. Because the first two equations are known, there will be one free variable, the price of a donut, and all the other prices can be put in terms of that one, which reduces the number of unknown prices to only one.

The book's solution is nearly the same. In the answer file, it's under One.III.2.24. When the matrix is in canonical form, The last row reads 0s + 0c + 0d = p - 2.00, so the price is $2.00 (USD).

Hel. said...

Oh!
Now I that I see the solution, it does make me remember about that way of solving from school last year.
But yeah, I didn't do that. I just did:
4x + y + 10z= 8,45 (.3)
3x + y + 7z = 6,30 (.-1) (.4)

4x + y + 10z= 8,45
-3x - y - 7z = -6,30
----------------------
x + 3z = 2,15 (I - first equation)

12x + 3y + 30z = 25,35
-12x - 4y - 28z= 25,20
-----------------------
-y + 2z = 0,15 (II)

Now from I and II, we have:
x = 2,15 - 3z
y = 2z - 0,15

So, x + y + z =
=2,15 - 3z + 2z - 0,15 + z

=2