Famous Unsolved Math Problems as Homework
blogs.ams.org
blogs.ams.org
> When asked, "How could you possibly have done the first interactive graphics program, the first non-procedural programming language, the first object oriented software system, all in one year?" Ivan [0] replied: "Well, I didn't know it was hard."
>Common sense would dictate that the most experienced programmers should have been assigned to these difficult tasks, but, as Hopper glibly explained, young people did not know that they were supposed to fail.
He just happened to be the first to grok them. Question is how he came to face those problems without any apparent precedent.
I think for most people, not knowing a problem is unsolved will lead them to try out many more approaches than if they knew. The problem is that most of the approaches will be approaches that have already been tried before and the rest will be useless. This does nothing for the solving of the problem but greatly aids your own understanding.
I love fun stories like that. And I love that it shows this guy is crazy brilliant yet humble enough to shrug off that success and just assume he had to figure out something else for his thesis. At least that's my interpretation.
faithInHumanity++;The problem was posed as a while loop, and the question was, does the loop terminate for arbitrary n>0, so it seemed very tractable:
given: n > 0.
while n != 1:
if n is odd:
n = 3n + 1
else:
n = n/2
n = 3n + 1
That was about 30 years ago. I still remember it fondly.
Tomás Oliveira e Silva of the Universidade de Aveiro, in Portugal, apparently. According to a page on his personal website [http://sweet.ua.pt/tos/3x+1.html] he has verified it up to 5 x 2^60.
I just implemented it too. I notice that by 100K, you get an intermediate result of size just less than 2^31, but at 1M, you get an intermediate result of size about 2^36. Maybe I went up above 100K.
For more: http://en.wikipedia.org/wiki/Collatz_conjecture#Experimental..., which includes some very nice plots, and a fractal construction when iterating an extension of the map to the complex plane. Whew! (On the other hand, https://xkcd.com/710/)
It needs to land on a power of 2 at some point.
No one knows.
> Is there a name for this problem?
The statement that it always terminates is the Collatz Conjecture. It's the first problem in the posted article.
It's a clever way to re-state the problem to look more computer-science-y.
There are heuristic to show that the algorithm should terminate but there are numbers for which it takes an arbitrarily long time for convergence. Furthermore, there are similar problems that have divergence or loops. What makes matters worse is that it's been proven that such problems are undecidable in general.
Heh.
It was one of the only times I had a really bad professor in grad school. He was visiting for six months, and you could really tell he didn't want to be teaching. He used an out of print book (Graph Theory With Applications by Bondy and Murty), which meant I had to go to the library to even read it. He lectured at a level that was beyond us, and he literally wouldn't tell us where his office was, so he wouldn't have to answer questions. Maybe with a different teacher I would have been less annoyed about the research problem.
What I particularly like is that the Erdos-Strauss problem is one that's accessible to a junior schooler - once you know fractions you can investigate. I could see it forming part of a project like the graph theory investigations posted formerly, http://jdh.hamkins.org/math-for-eight-year-olds/.
Any professor who handed out that assignment to an undergraduate class without fair warning, would likely face a full scale revolt, possible threats of violence, and almost certainly a significant portion of the class immediately dropping him.
[Edit - to be clear, I'm commending the instructor for not hanging their students out to dry by giving a mission impossible homework assignment]
That's the important part of this - the instructor didn't give it as homework. And yes, I've seen students freak out on their instructor en-masse for far less than a mission impossible homework assignment.
* Students are forced to depart from the “answer-getting” mentality of mathematics.
* Students are forced to redefine success in learning as making sense and increasing depth of understanding.
* Students are able to work in a context in which failure is completely normal.
If your class tends toward revolt, they have been way too far strayed from the first point, and that may be the professors fault.
That's a huge problem when you've trying to teach them about proofs, and kicking them out of that mentality is the biggest challenge in first year under-grad. This idea of letting them work for a limited time on an unsolved problem seems a useful approach to changing their attitude.
Perhaps because they've been conditioned for 12 years to believe that this is what "math" is.
Students aren't usually taught subtraction is adding a negative number. Students aren't usually taught division is multiplying by a fraction. Students aren't usually taught that there are ways of counting outside of the decimal 'base 10' way of counting, or the advantages of counting in Octal, or how to count in Binary on your hands.
Math teachers love to say "2+2 does not always equal 4" but never explain that's only true in Base2-4 where the representation of "4" doesn't exist and it is represented as 100, 11, or 10.
So not only are we taught "there's always an answer". We're not taught other concepts and sometimes information is left out entirely until you reach a college level of mathematics - at which point all these lies, unexplained concepts, and "answer-seeking mentality" become a problem.
Learn, in my experience.
Getting people to leave a mere "answer getting" mindset and engage with the "technique and problem understanding" mindset is one of the most important parts of the job of teaching freshmen and sophomores (particularly in mathematics). They've often been rewarded for this approach in high school and have trouble letting it go -- but it really constrains the ability to understand things.
The really sad cases are the ones who are really good at it, good enough to survive all the way to grad school sometimes. They aren't doing themselves any favors, and invariably get left behind by people who may have less innate talent but engage more. Hopefully recoverably.
https://news.ycombinator.com/item?id=8972744
(I don't know why you were so heavily downvoted. I upvoted you.)
The focus on grades and "the right answer" instead of learning and thinking is probably why it can be so frustrating for both parties when someone fresh out of university comes to a (programming) job interview.
I've noticed a lot of attempts on freelancing sites to pay a contractor to complete homework and school assignments. I can't imagine a worse form of self-sabotage, and it seems like students have profoundly the wrong message about education.
Thing is - it's not these kids' fault, once they do grok the notion of "not yet solved", they are great. It's that they spend the last 16 years being punished for getting something wrong, in a context where there is only a right answer or wrong answer, and that fact is known - even in subjective topics.
Yes.
and not told your students what you had done prior to them leaving for the day?
No. As the comment I responded to says: I
reveal the full truth after they have been working for fifteen minutes or so.
Some interviewers would present unsolved problems in interviews as well, if a candidate was happily eating their way through the regular material.
Cambridge is a little unusual in that the only mark that people cite is the one on the final year exam. I believe US universities operate by continuous accumulation of marks? And that ongoing disputes over marking are more common because of this?
It's also already working with a highly selected group of people from the far tail of the ability distribution, and looking for a way to identify the exceptional among the merely very high ability.
Yeah, that'd be embarrassing.
That's the context in which being thrown a heretofore unsolved problem in calculus is not particularly amusing for an undergraduate.
I just want to make sure the undergraduate instructors reading this thread realize that doing this on the sly in a standard problem set would be a very, very bad idea. Not cool.
I don't see it!
Not being facetious or judgmental either. And there's strong pressure for calc profs these days to not assign more than 30 problems a week. Sensitivity about workload is very high at many institutions.
But SFU (a not so bad University in Canada), - Calculus 151 in Images theater, and Calculus 152. I recall the workload in those two courses very, very distinctly. Both first year courses. In hindsight, I think they served the purpose of filtering out students who weren't prepared to work hard...
This was university maths, in that it was maths, and you were at university, but in terms of the syllabus it was pretty much later secondary school standard, and there was very little emphasis that I can recall on preparing people for further study of maths. So no proving anything. Just telling you how stuff worked, and then a zillion exercises for you to do to try to make it stick.
There are a number of problems that basically boil down to "what's the smallest value that has property <x>", which can be solved via brute force - or rather, could be, except that naive brute force would take too long, and no-one has figured out any tricks to make it fast enough to be practical.
For example, calculating the value of any but the first few Ramsey numbers (the minimum number of vertices v = R(m, n) such that all undirected simple graphs of order v contain a clique of order m or an independent set of order n).
There are also a lot of problems that could be proven or disproven via (counter)example - something like the Collatz conjecture, for instance.
Or perhaps they would keep it secret, but it would be a huge cultural faux pas to have a method to factor large numbers without also explaining (and thus proving) how it works.
Proving things seems really boring and uninteresting to me, and there is no guarantee the task is even possible.
"Proving" isn't distinct from "mathematics". That's what I'm trying to get at. In a sense, a proof is equivalent to a computation (and it's possible to make this precisely true in some contexts).
The public at large has gotten some impression that proofs are something only some kind of mathematics needs, probably after being traumatised by high school geometry classes. Proofs are all that mathematics is.
One interesting math problem someone told me just the other day was to come up with a series of forward and backward steps that would keep you from falling off a cliff, if a malicious person only chose each 2nd, 3rd or 4th step. Or to find the resistance between two points on an infinite grid of resistors. Or to find a series of bridges to get between several island without ever crossing a bridge twice. Or coloring a map with only 4 colors. Or in machine learning, tons of unsolved problems involving approximating intractable inference problems.
That's a pretty wide variety of problems just off the top of my head, none of which are proving things.
Sure some of the problems might not have a solution, but at least I'm not asking people to solve the halting problem, which is what half of those "unsolved math proofs" require.
Even if you do solve them, the result is uninteresting. You could, at least in theory, quickly explain fermats last theorem to almost anyone. Or the four color theorem, or most of the problems I mentioned. But only a few mathematicians understand the proofs, and sometimes no one understands them (the ones proved computers.)
You have it in your mind that proofs are something that you don't like and completely distinct from computations. You don't have a clear distinction in your mind between what you like and you don't. It seems to me that some mathematics is just unfamiliar to you, and when that happens, you call it "proofs".
got any clues?
EDIT: Also wolfram alpha
Instructions at http://saskatoon.cs.rit.edu/min_instructions/