{"id":4978,"date":"2019-07-08T12:00:09","date_gmt":"2019-07-08T17:00:09","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=4978"},"modified":"2019-11-09T00:08:55","modified_gmt":"2019-11-09T05:08:55","slug":"the-worlds-simplest-impossible-problem","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2019\/07\/08\/the-worlds-simplest-impossible-problem\/","title":{"rendered":"The World’s Simplest Impossible Problem"},"content":{"rendered":"\r\n

(This is a reprint of the second ever Cleve's Corner from the Winter 1990 MathWorks Newsletter<\/i><\/a>).<\/p>

The other day at lunch with a couple of other MathWorks people, I posed the following problem:<\/p>

“I'm thinking of two numbers. Their average is 3. What are the numbers?”<\/p>

Now stop a minute and, before you read any further, provide your own answer to my question.<\/p>

Of course, my problem doesn't have a “right” answer. The solution is not unique. The problem is “underdetermined” or “ill posed.”<\/p>

Most of the people I was having lunch with wouldn't give me an answer. When I pressed them, one person finally said, “Both numbers could be 3.\" Another person said, “Yes, but one could be 6 and the other 0. That's what I hoped they would say. In some sense, these are both “nice” answers. Nobody said “23 and minus 17,” or “2.71828 and 3.28172.” Those would also have been been correct, but not as “nice.”<\/p>

What does this have to do with MATLAB? Well, MATLAB doesn't balk at impossible problems. It will solve this one. And it does it without complaining like my buddies at lunch.<\/p>

Naturally the problem is a matrix problem. It is a \"system\"<\/p>

A*x = b<\/pre>
of one \"simultaneous\" linear equation in two unknowns.  The matrix is<\/p>
A = [1\/2 1\/2]<\/pre>
and the right-hand side is<\/p>
b = 3<\/pre>
MATLAB’s backslash solves such equations.  Typing<\/p>
x = A\\b<\/pre>
tell's me<\/p>
x =\r\n     6\r\n     0\r\n<\/pre>
The solution is a 2-by-1 matrix representation of one of the “nice” answers I expected.  The second half of the help entry for “\\” gives some indication of where this solution came from.<\/p>
If A is an m-by-n matrix with m <\r\nor > n and B is a column vector\r\nwith m components, or a matrix with\r\nseveral such columns, then X = A\\B\r\nis the solution in the least squares\r\nsense to the under- or overdetermined\r\nsystem of equations A*X = B.\r\nThe effective rank, k, of A is\r\ndetermined from the QR decomposition\r\nwith pivoting.  A solution X is\r\ncomputed which has at most k nonzero\r\ncomponents per column. If k < n\r\nthis will usually not be the same\r\nsolution as PINV(A)*B.<\/pre>
In our case, we have m = 1<\/tt> and n = 2<\/tt>. My matrix has full rank, but the most that can be is k = 1<\/tt>. So, we get a solution with at most one nonzero component. Even that isn't unique. There are exactly two solutions with one nonzero component, [6 0]’<\/tt> and [0 6]’<\/tt>. We get the one where the nonzero component has the smallest index.<\/p>
What about my other “nice” solution? That comes from the pseudoinverse.<\/p>
x = pinv(A)*b<\/pre>
produces<\/p>
x =\r\n    3.0000\r\n    3.0000<\/pre>
(The fact that I got that I get 3.000 instead of the integer 3 without the trailing zeros indicates that there has been some roundoff error and I don't have the other “nice” solution exactly, but you can pursue that yourself if you really want to.)<\/p>
Of all the possible solutions to A*x = b<\/tt>, this one, x = [3 3]’<\/tt>, is the “shortest.” It minimizes norm(x)<\/tt>. In fact x = A\\b<\/tt> has<\/p>
norm(x) = 6.0000<\/pre>
while x = pinv(A)*b<\/tt> has<\/p>
norm(x) = 4.2426<\/pre>
Now, finally, we have uniqueness.  Of all the possible solutions to A*x = b<\/tt>, the one that also minimizes norm(x)<\/tt> is unique.<\/p>
So, MATLAB not only solves the problem, it gives us a choice between two different solutions, x = A\\b<\/tt> and x = pinv(A)*b<\/tt>.  I think the first solution, A\\b  = [6 0]'<\/tt>, is \"nice\", because it is \"simple\"; i.e, it has the fewest possible nonzero components.  I think the second solution, pinv(A)*b = [3 3]'<\/tt>, is \"nice\" because it is \"short\" and \"unique\".  None of the other possible solutions have such nice characteristics.<\/p>
This problem, \"Given the average of two numbers, find the numbers,\" captures the essence of many ill-posed and underdetermined problems. Computer tomography, which is the life-saving business of generating images from X-ray, magnetic resonance, and other scanners, is really a grown-up version of this question.  Additional constraints, like minimum norm or fewest nonzero components, or \"good looking picture,\" have to be specified to make it a reasonable mathematical and computational task.<\/p>
By the way, I first learned about this \"World's Simplest Impossible Problem\" from Don Morrison, who also started the University of New Mexico's Computer Science Department, invented the Fast Fourier Transform before Cooley and Tukey, and, years ago, got me to move to New Mexico. Thanks for all those things, Don.<\/p>
I have to confess that I wrote this anecdote about posing a problem at a MathWorks lunch before it really happened.  The results of the actual experiment were even more interesting.  As I had expected, everybody did grumble and complain about my problem.  Then one person said \"9 and -3.\" She had obviously picked up on the idea.  Another person said \"3 and 1.\" Luckily, he is not responsible for any numeric portions of MATLAB. But three people said \"2 and 4.\"  That is certainly another \"nice\" answer, but the constraints it satisfies are more subtle.  They have something to do with requiring the solution to have integer components that are distinct, but near the average.  It's harder to state and compute in MATLAB without just giving the answer.<\/p>
Okay, now I'm thinking off three numbers whose average is $\\pi$. What are those numbers?<\/p>