Have you ever realized you can't solve the homework you assigned? This question is targeted at people who assign problems: teachers, student assistants, tutors, etc.

This has happened to me a handful of times in my 12-year career as a professor: I hurriedly assigned some problem from the text thinking "this looks good."  Then later realized I couldn't solve it.  Few things are more embarrassing.

Here's a recent example: "Give a linear-time algorithm that determines if digraph $G$ has an odd-length cycle."  I assigned this thinking it was trivial, only to later realize my approach wasn't going to work.

My question: what do you think is the "professional" thing to do:


Obsess on the problem until you solve it, then say nothing to your students.
Cancel the problem without explanation and move on with your life.
Ask for help on cstheory.SE (and suffer the response, "is this a homework problem?")


Note: I'm looking for practical and level-headed suggestions that I perhaps haven't thought of.  I realize my question has a strong subjective element since handling this situation involves one's own tastes to a large extent, so I understand if readers would prefer to see it not discussed.
Yes, sadly, I've done this several times, as well as the slightly more forgivable sin of assigning a problem that I can solve, but only later realizing that the solution requires tools that the students haven't seen.  I think the following is the most professional response (at least, it's the response I've settled on after several false starts):


Immediately and publicly admit the mistake.  Explain steps 2 and 3.
Give every student full credit for the problem.  Yes, even if they submit nothing.
Grade all submitted solutions normally, but award the resulting points as extra credit.  In particular, give the usual partial credit for partial solutions.


The first point is both the hardest and the most important.  If you try to cover your ass, you will lose the respect and attention of your students (who are not stupid), which means they won't try as hard, which means they won't learn as well, which means you haven't done your job.  I don't think it's fair to let students twist in the wind with questions I honestly don't think they can answer without some advance warning.  (I regularly include open questions as homework problems in my advanced grad classes, but I warn the students at the start of the semester.)  Educational, sure, but not fair.

It's sometimes useful to give hints or an outline (as @james and @Martin suggest) to make the problem more approachable; otherwise, almost nobody will even try.  Obviously, this is only possible if you figure out the solution first.  On the other hand, sometimes it's appropriate for nobody to even try.  (For example, "Describe a polynomial-time algorithm for X" when X is NP-hard, or if the setting is a timed exam.)

If you still can't solve the problem yourself after sweating buckets over it, relax.  Probably none of the students will solve it either, but if you're lucky, you'll owe someone a LOT of extra credit and a recommendation letter.

And if you later realize the solution is easy after all, well, I guess you screwed up twice.  Go to step 1.