As a student in 1939, the mathematician George Dantzig once arrived late to a lecture. He mistook the unsolved problems on the blackboard for homework, and solved two of them.
I imagine being told that a problem is unsolved changes the way you approach it. You'll assume that 'obvious' things have been tried before. Without that psychological barrier you can try out ideas that are obvious to you that might not have occurred to anyone yet. Telling someone that a problem is unsolved implies they won't be able to solve it unless they're better than all the people who've approached it before in some way. That isn't necessarily true; "better" doesn't really apply at the level of people attempting these problems.
> 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."
Or to quote Beyer's Grace Hopper and the invention of the information age:
>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.
Confidence is quite important in mathematics. You would usually go further if you are confident than if you are not. That said, most unsolved problems in mathematics require more knowledge to state than these simple problems.
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.
There's something to that, but for an approach to be worth trying you don't have to expect it to work: just that you'll learn something about the problem.
> A year later, when I began to worry about a thesis topic, Neyman just shrugged and told me to wrap the two problems in a binder and he would accept them as my thesis.
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.
A good down to earth mathematician will always look ahead and try to solve more problems, do more math, etc. It's not surprising that he wanted to create new math despite already doing so.
One of my favorite C.S. professors, in a first-year grad class, gave out 3 of these problems as homework, including the first one, without indicating whether it was easy or hard.
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
It was a tease. I tried a couple of different ways to prove it, but of course nothing worked. Then I tried to find a counter-example. The numbers get pretty big, in some cases, because applying
n = 3n + 1
several times in a row will blow "n" up, despite the intervening n = n/2. This was before arbitrary-precision arithmetic was a thing, so the only tool I knew that could do this was the Unix "dc". I think I was able to get up to n=10K or 50K on our campus VAX.
That was about 30 years ago. I still remember it fondly.
This is a pretty good example of how far computing hardware has come. I was able to eliminated 2 to 50k in 81ms in completely unoptimized C# just now. Makes me wonder who has taken this approach the farthest these days.
> ... who has taken this approach the farthest these days.
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.
My prof was also more impressed by my implementing it than by my attempted proofs. (Not the first time this has happened!)
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.
Just to clarify why, if the result is ever one (the loop's exit condition), then it would be about to get stuck repeating 1,4,2 forever if it didn't exit. If you can prove the loop does not exit (i.e., never reaches one) for some n, then you just proved that, for that n, it would never reach the 1,4,2 repetition pattern even without the stop condition.
It's a clever way to re-state the problem to look more computer-science-y.
As some of the people have already said, this is the Collatz conjecture aka 3n+1 problem aka half-or-triple-plus-one (HOTPO)problem. The fact that we don't know if the algorithm will certainly land on a power of two shows that it's quite a difficult problem. The famous mathematician Erdos said that math is not yet ready for such problems.
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.
It's rated HM45 (higher mathematics required, 45 out of 50) on a 'logarithmic' difficulty scale. Previous editions used to rate it M50 (mathematics, unsolved research problem).
This is great in class and for homework, but it can be taken too far. UChicago professors like to put open problems (without any indication that they are unsolved) on final exams. Half the battles is identifying which problems are unsolved to avoid wasting time on them.
In grad school, I had a graph theory professor who assigned a research problem he was stuck on as homework. He didn't tell us that until later, after I had a wasted a lot of time trying to solve it. It wasn't very cool.
I did feel like it has been a waste of time. He just mixed it in with a bunch of textbook problems. It wasn't a particularly elegant or insightful, just something technical he wanted the answer to. I don't think anyone in the class got it right, as we didn't really have the tools to make progress on it. It was a first year grad class.
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.
These are great problems the first two seem to have obvious modes of proof at first sight ...
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/.
The most important part of this was, "When I use these problems for in-class work, I will typically pose the problem to the students without telling them it is unsolved, and then reveal the full truth after they have been working for fifteen minutes or so."
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]
Undergraduates (at least for the first few years) have to be in the "Answer Getting" mentality. I'm fine with curve balls being thrown at graduate students, and maybe, just maybe, fourth year students, depending on the course - but can you imagine what a freshman/sophmore student would do if faced with this situation?
I disagree - in my experience the "answer getting" mentality is the largest barrier to doing "proper" math that there is. The students are unwilling to just try stuff to see what happens, because they think there's one way to do it, and one answer to find. They think they need to find the right process, apply it without making any stupid errors, get the answer, and move on.
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.
It also doesn't help that they hide details and sometimes straight up lie to students during those first 12 years. To avoid "confusing" them.
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.
> but can you imagine what a freshman/sophmore student would do if faced with this situation?
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.
I very strongly disagree. This applies to programming and engineering as well as math you know... There is way too much "there is a right answer" focus on undergrad. An aspect of working with newly graduated people I really dislike is that they always ask "am I doing it right?" or "What's the right way" and not even faintly grasping the idea when I tell them "I don't know, that's why we're doing it - if there was a known good solution, we'd just buy it and move on".
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.
One of the things people often fail to learn in university is that, once they leave, they will be judged on what they have learned, not on their grades. I think that the sooner an undergrad learns that getting an answer wrong on a homework assignment isn't the end of the world, the better. For their own stress levels, too.
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.
I'm guessing you've never taught math to undergraduates. Unless they are math majors, for the most part they really don't like being given harder-than-average questions, let alone open problems.
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.
I can imagine the students now. All of them like, "omigod we're being forced to learn something by investigating things and being creative omigodomigod it has no known answer gasp".
It's more like, "Student has a standard 15 credit semester, means 15 hours of classroom lecture + 45-60 hours of study/assignments outside of class. Student is micro-scheduling the number of minutes they have to answer each of the standard 20 Calculus questions (God, it was always 20 question) which they have to have in to the TAs before next lecture. 60 questions/week, every week, and you have about 12 hours allotted, which works out to no more than 12 minutes per question. Any questions you go over that 12 minutes, you need to steal from other questions and somehow solve more quickly, and remember, this is all new material for the student. If you blow your budget on math, it either comes out of other classes, or sleep.
That's the context in which being thrown a heretofore unsolved problem in calculus is not particularly amusing for an undergraduate.
This sounds more like secondary school than university. Certainly for first year undergrad there are worksheets and a significant workload, but it sounds like you're describing what I think of as straight school-type work.
I had courses like this as part of my degree, though of course the ones I had could easily turn out to be something completely different. If you're any good at maths, it's very possible you just never noticed that these courses exist ;) They seemed to be designed for people who hadn't done (or had done poorly at, or mature students who had forgotten the material for) later secondary school maths exams.
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.
Maybe I was just a lazy student in high school, but I don't ever recall stressing over math homework. I'm struggling now to remember if I even had math homework -presumably I did, but it didn't lay down any memories.
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...
I was traumatized by my undergraduate calculus courses. And that was without the profs (who were all excellent) slipping in any "Unsolved Research problems." This entire thread has been like Trauma Trigger [http://en.wikipedia.org/wiki/Trauma_trigger]
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 think what the professor did was exactly correct, have them experience something new mathematically, but give them the heads up that they weren't (likely) to be solving it, as it's a new pattern they hadn't recognized before.
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.
30 problems/week, 10/lecture would actually make calculus enjoyable, you could stretch out, and spend 20-30 minutes on some of the more challenging problems without freaking out.
There were a few unsolved conjectures presented on the board on occasions. What was more common, as a first year maths student, was to be presented with homework that had 10 questions on of which one would be marked "hard" and one "very hard". Some of the "very hard" questions would be unsolved research problems.
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.
What you are describing is entirely fair. The student has been fairly warned that they might not be able to solve the problem in the 8-10 minutes that their incredibly packed schedule allocates to it. They aren't being blindsided by an unsolved research problem masquerading as a standard question on a problem set. Fair game.
It strikes me that you expect students to behave that way for challenging them. Maybe it is a matter of cultural differences? In my university, at the most they would complain to the administration. And even then the problem would have to be tied to their grade so they could make the case of unfairness.
My university had a pretty liberal withdrawal policy if you did so prior to mid-terms. Instructors who weren't competent, or who acted like jackasses, didn't get complaints - the students just dropped the class and focussed their energy on instructors who were both competent, and not inclined to sabotage them.
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.
This isn't a meaningful question. There isn't a distinction between what is mathematics with a proof and what is mathematics without a proof. The examples that others have given about Ramsey numbers are, in fact, a proof. The proof could consist of a gigantic computation or it could be some other deep insight. But in the end, saying the Ramsey number R(5,5) is, say, 47, is not very meaningful without a convincing argument that establishes why it's that number. And those convincing arguments are a proof.
That's not true. There is a whole class of problems that are trivial to prove an answer is correct, but very difficult to find the answer. Like factoring the RSA numbers, or finding a large prime number, etc.
You're thinking of computer things like P vs NP. Any mathematician who develops some sort of algorithm for factoring large numbers would announce this algorithm and a proof of its correctness as the interesting thing to announce, not merely that some large number was factored, without disclosing how.
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.
There is no guarantee it's possible to factor large numbers quickly either.
"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.
You can model many problems as proofs, but not all, and it's not usually a useful observation. Most interesting math problems have nothing to do with proving things. The problem is people have already solved all the interesting problems. Proofs are just what's left.
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.)
Finding that resistance in the grid of resistors involves performing a computation. That computation is a proof.
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".
Finding [Ramsey numbers](http://en.wikipedia.org/wiki/Ramsey%27s_theorem) is one. They are hard to calculate even for small values. Most open problems are either to prove something because we can make a good guess to what the answer should be.
While these problems are interesting, it would be nice to have a little background on them. Where did they come from? What other problems would be solved by solving these problems?
The post links to the wikipedia pages for two of the problms, so it is pretty easy to get the background on them. At any rate, the point of the post was not those particular problems, but how the instructor uses them to challenge the students. I think digressions into why those problems are mathematically or practically interesting would distract from the main theme of the post.
That's missing the point. The journey is often more important than the destination (i.e., learning how to explore a problem space, learning how to deal with failure, etc)
http://en.wikipedia.org/wiki/George_Dantzig