The Price of Beer - Linear Algebra Problem

[FactChecker]

I might just as well propose that the bitter was bad and the proprietor ended up paying those who drank it $3.86 per pint.
In any case, "exact" means exact, not "nearly correct".

 

[Ibix]

I makes a problem with twice as many variables as equations.

Yeah, but @pbuk's approach is to restrict the price of a half to half the price of a pint or half plus a half penny. There's also the problem of interpreting things like 5/2 - there are three ways of making that total. That reduces it to solving and checking a relatively small number of linear problems, even if you don't make further insights into the pricing before you start.

 

[FactChecker]

Suit yourself. IMO, this is a much better exercise if it is used to illustrate what can happen in an ill-conditioned problem than to illustrate that it is ok to call a problem "linear algebra" and fudge the "linear" part.

 

[pbuk]

Suit yourself. IMO, this is a much better exercise if it is used to illustrate what can happen in an ill-conditioned problem than to illustrate that it is ok to call a problem "linear algebra" and fudge the "linear" part.

Yes, but that is something that you should take up with the OP: I suggest looking at the original problem in its original context (which is a Computational Maths course, not linear algebra):

it is the bonus question in Part 1 of worksheet 3 from http://www.staff.city.ac.uk/o.s.kerr/CompMaths/.

.. and perhaps also noting from the course notes linked on the same page:

There are two principal types of error that occur when solving the equations.
• Errors in the data. By which is meant that some of the coefficients may only be quoted to say two decimal places, this immediately gives a possible error ±0.005. This type of error is a problem when the solution to the equations are sensitive to small changes in the coefficients - this will always be a problem and is referred to
as ill conditioning. Although this problem is not that common we must always be on our guard to identify when it may occur...

Yeah, but @pbuk's approach is to restrict the price of a half to half the price of a pint or half plus a half penny. There's also the problem of interpreting things like 5/2 - there are three ways of making that total. That reduces it to solving and checking a relatively small number of linear problems, even if you don't make further insights into the pricing before you start.

The original table from the link I posted above is

When there are multiple ways of interpreting e.g. $2 \frac 1 2$ it is usually best to start with the simplest.

 

[FactChecker]

Yes, but that is something that you should take up with the OP: I suggest looking at the original problem in its original context (which is a Computational Maths course, not linear algebra):

Ok, I'll buy that. It would have also helped a lot if the hint had been included in the original post.

.. and perhaps also noting from the course notes linked on the same page:

Yes. I note, especially, this part: "This type of error is a problem when the solution to the equations are sensitive to small changes in the coefficients - this will always be a problem and is referred to as ill conditioning."

The original table from the link I posted above is
View attachment 319105
When there are multiple ways of interpreting e.g. $2 \frac 1 2$ it is usually best to start with the simplest.

I guess this leads to questions like whether '2' is two pints, or four half pints, or one pint and two half pints, etc.
In an ill-conditioned problem, I would hate to guess how many reasonable solutions there might be, and what the standard of "reasonable" is.

 

[pbuk]

In an ill-conditioned problem, I would hate to guess how many reasonable solutions there might be, and what the standard of "reasonable" is.

I often find that by not worrying about how hard and unreasonable something might be and instead just doing it, it turns out not to be so hard or unreasonable after all. You can see from the timings in #14 that it took me less than 10 minutes to find the solution once I had found a decent version of the question (which took about half an hour).

 

[FactChecker]

I often find that by not worrying about how hard and unreasonable something might be and instead just doing it, it turns out not to be so hard or unreasonable after all. You can see from the timings in #14 that it took me less than 10 minutes to find the solution once I had found a decent version of the question (which took about half an hour).

You found A solution. How many more are there? There are a lot of combinations of full and half pints that might be other solutions. In a simple, small, academic example, you might be able to handle it well, but nobody really needed this problem to be solved anyway; it's just a practice exercise. There are a lot of real-world problems that have hundreds, even thousands of variables.

IMHO, this is just a bad example. It is ill-conditioned, with no hint of how to handle that aspect. It is less well-defined than it needs to be. The solution is "ad-hoc".

 

[diegogarcia]

Anyway the question is available on the interweb: it is the bonus question in Part 1 of worksheet 3 from http://www.staff.city.ac.uk/o.s.kerr/CompMaths/.

Thanks for providing that link. I could not find the original site.

Yes, ill-conditioning is the issue here. For a very brief, although very comprehensive, discussion see this blog post:

Condition Number of a Matrix

Most CA software include functions to determine the condition number. For the FOSS Maxima software, one can use the functions described here:

https://def.fe.up.pt/pipermail/maxima-discuss/2007/018137.html

mat_norm2j(M) := sqrt(lmax(eigens_by_jacobi(transpose(conjugate(M)).M)[1]));

Using this function, the condition number of the matrix in this problem is 3923.4, which is large enough to cause considerable error.

I always thought that the issue of this problem was theoretical in nature, but the issue is actually numerical in nature.

 

[scottdave]

Since the person doesn't have all of the information (pricing of a half pint vs pint) then this is an estimation problem, rather than an algebra problem.

They are all friends. He could just find the average spent per pint for all of the beer. Then he knows how many pints each person consumed.

 

[pbuk]

Since the person doesn't have all of the information (pricing of a half pint vs pint)

I am not sure how many times it needs to be said that a half pint is priced at half of the price of a pint, rounded up to a £0.01 if necessary.

then this is an estimation problem, rather than an algebra problem.

No it isn't, it is a problem demonstrating the magnification of errors in ill-conditioned problems in computational linear algebra.

 

[FactChecker]

I am not sure how many times it needs to be said that a half pint is priced at half of the price of a pint, rounded up to a £0.01 if necessary.

Should we assume there are only marginal costs and no fixed cost? I think that is unusual. The per unit price is usually noticeably higher for the smaller quantity, and not just due to rounding up.

 

[pbuk]

Should we assume there are only marginal costs and no fixed cost? I think that is unusual. The per unit price is usually noticeably higher for the smaller quantity, and not just due to rounding up.

You should assume exactly as much as needs to be assumed to answer the question and no more. For the avoidance of doubt this means that instead of the first equation being $1.5b + 2l +2.5c + 0.5s = 8.99$, the correct sum could also be $8.985, 8.98 \text{ or } 8.975$ depending on how many of $b, c \text{ and } s$ have prices for a pint that are an odd number of pence. There are 16 combinations to try in all (including the one that leads to $b = -£3.86$) and only one gives a sensible answer. Remember this is a question in computational mathematics: iterating over a potential solution space is part of the standard toolbox (and each iteration is just 1 matrix multiplication).

 

[scottdave]

,... it is a problem demonstrating the magnification of errors in ill-conditioned problems in computational linear algebra.

For some reason it "clicked" for me, this time.

 

[FactChecker]

No it isn't, it is a problem demonstrating the magnification of errors in ill-conditioned problems in computational linear algebra.

It certainly illustrates that. I'm just not sure that was intended. I would have to see the text.
(I have seen an optimization example where the matrix was actually singular in a text where the code testing for a zero determinant was commented out.)

 

[Mark44]

The thread seems to have run its course, so I'm closing it. If anyone feels the need to add anything more of substance, please let me know and I'll reopen the thread.