This week’s post looks at the problem of proving that you cannot possibly solve a problem. Occupy Math met a woman, Carly Rosins, at the math education conference he attended in June. She had taken a couple of her undergraduate courses from him. In the fall she will be starting a postdoctoral fellowship in Berkeley, Occupy Math’s hometown. She had just finished working as a councilor for a math camp. One of the problems she posed to the students had no solution – and the point of the problem was teaching that some problems cannot be solved. The whole situation went a little retrograde. One student refused to believe that the problem could not be solved – even after Carly had proved no solution existed. The student had a philosophical problem with the idea you could prove something couldn’t be done. One of the things that studying math does is to give you the tools to let you see no solution exists for some problems.
Sadly, this is a skill that university faculty sometimes lack.
The problem Carly posed appears below. Before we get to it, let’s look at a classroom example of an unsolvable problem. Occupy Math and his master’s student Mandy Saunders recently drove to Brock University to meet with a collaborator. During the course of the drive, Mandy told the story of a very frustrating animal science lab from her undergraduate education. A big topic in animal science is mixing up animal feed to meet nutritional requirements. This is tricky because you want the cheapest ingredients that are currently available. The things you use, like corn, soybean hulls, or treated sawdust, have changing prices and availability as well as variable nutrient content. This means that the mixture-to-meet-nutrition problem has to be solved over and over.
The issue in Mandy’s lab is that she was told to make a mix, one of whose properties was that it be 30% ingredient X. This is a fairly simple goal, but all the available inputs contained well over 30% ingredient X. When she reported the problem to the lab instructor he told her “try some numbers in the spreadsheet”. Now spreadsheets are fairly cool, if you know how to use them, but they cannot violate conservation of mass or any of the other fundamental laws of nature. If you mix things that all have more than 30% X, you get something with more than 30% X.
The professor had set a completely impossible problem for his students and did not notice. When shown it was impossible by a student, he blew her off.
With that sad example as motivation, let’s try to state and work through the unsolvable utility problem that Carly posed. As shown in the picture below, we have three houses that need to be hooked up to electricity, water, and sewer lines. Government safety regulations, written by a government official with no mathematical training, require that the lines for these utilities not pass over or under one another. His perfectly benevolent intent was to avoid workplace accidents, like electrocuting the workers hooking up the water or rupturing the sewer lines while working on one of the other utilities.
If we abstract the problem what we need are to draw lines (or curved paths) between each of the utilities and each of the houses without lines crossing one another. The diagram below (left) shows the simplest way to do this if we completely ignore the rule about lines crossing. Look at the lines shown in red. These lines demonstrate that the hookup contains six connections that make a simple closed path. The red paths are shown as a hexagon on the right side of the picture. This hexagon is the starting point for the demonstration of insolubility.
Start with just the hexagon, labeled E, W, S for electricity, water, and sewer, and H for house. Notice that every other node is a house and that the missing connections need to join each house to the utility that appears directly across from it:
Now a hookup can go across the inside of the hexagon or around the outside. If we do both of these, it does not matter which we do first. There is no other place to put hookups than inside or outside the hexagon, since that includes every available location. Given that, let’s hook up electricity to the house that does not have it:
The argument about space inside and outside the hexagon now require us to make an outside connection. Because the hexagon is symmetric, it does not matter which order we try and hook up the (as yet unconnected) utilities in. We did electricity first, so let’s hook up water around the outside of the hexagon next:
We have one connection still to make – hooking up the sewer to the one house that does not yet have all of its utilities. The problem is that, if it goes across the inside of the hexagon it crosses an electricity hookup and if it goes around the outside, it crosses a water hookup. The two hookups that are not part of the hexagon blocked off all places the sewer hookup could go! The possible routes for the sewer are shown in red and the crossings they force are circled in green:
Unless we can get the government to ease the regulatory burden, the third homeowner will need an outhouse.
The utility problem is the first problem that arises when studying planarity in diagrams and graphs. This turns out to be an applied problem. If you are laying out a printed circuit board or a microchip it is really convenient if the wires don’t ever need to cross. This is perhaps another reason Occupy Math favors teaching graph theory over calculus for students that are not going into physics and engineering. The planarity issue has its origins in the famous four color problem.
We now have a solid example of a problem that cannot be solved and a (hopefully) plain English demonstration of that insolubility. What about the student of Dr. Rosin’s that declined to believe in demonstrations of this kind? Carly thought it likely that the student remembered the correct maxim you cannot prove a negative, but mis-applied it. This is an important point and it concerns a different type of impossibility from that in the utility problem. This notion is also critical to understanding hypothesis testing in statistics.
Suppose we have the claim “alien spaceships have visited the earth in modern times”.
If a starship landed in the mall in Washington D.C. or on Parliament Hill in Ottawa, all doubt would be removed. It’s possible to imagine evidence that would prove the claim, conclusively. The negative claim is “alien spaceships have never visited the earth in modern times”. That one cannot be proved, because it requires you to be omniscient (all-knowing and all-seeing). If the spaceships, with advanced stealth technology, and only landing in Vanuatu, have asked the locals to keep it under their hat, well, you’re probably never going to find out about it.
In statistics, a null hypothesis (e.g. these two tests are not giving different results) and an alternative hypothesis (e.g. the tests are giving different results) are posed. Since accepting the null hypothesis is logically the same as claiming you proved a negative, you never accept the null hypothesis. The negative claim is that the two tests do not have different results; since the next set of samples might prove they are different, you can never be sure. You either reject the null hypothesis or fail to reject it. If you fail to reject it, it might still be false, but you haven’t piled up enough evidence to reject it yet. This point comes up over and over in introductory statistics – if you have to take such a class, keep it in mind.
Proving a negative is quite different from proving something is impossible. The take-home message from this edition of Occupy Math is that you should keep in mind that a problem may be impossible to solve. If you’re a teacher or professor, a secondary moral in this post is that listening to your students isn’t a bad idea. Occupy Math has dozens of publications that started with listening to a student. Have you had problems with your instructor not listening to you? Have you encountered impossible problems? Occupy Math would love to hear about it, especially in a comment or tweet!
I hope to see you here again,
University of Guelph,
Department of Mathematics and Statistics