<p>I'm not a teacher yet, but as a TA, I once did this.</p>

<p>I didn't find the problem in a textbook; instead, I came up with the problem myself. It turned out that, in spite of looking innocent, the problem had been the subject of a lot of debate back in 1980s, but was settled then.</p>

<p>Well, after knowing that, I announced that solving that problem has extra credit. No one came up with the correct result, but I gave half the (extra) mark to those whose answers were reasonable. Then, in the class, I admitted that this had been indeed a hard problem, and pointed the students to the relevant history.</p>

<p><strong>PS1:</strong> The problem was about the DES cipher: Are there a plaintext (P) and a ciphertext (C) such that, for two distinct keys K1 and K2, DES enciphers P to C under both keys? That is, C = DES(P, K1) = DES(P, K2).</p>

<p>The answer seemed to be "NO," but turned out that was not the case. See the relevant research here: <a href="http://www.springerlink.com/content/8yh6t8rru264cg4w/">How easy is collision search? New results and applications to DES</a>.</p>

<p><strong>PS 2:</strong> The <a href="http://en.wikipedia.org/wiki/Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem">Immerman–Szelepcsényi theorem</a> has been proved in much the same way! Quoting from <a href="http://rjlipton.wordpress.com/2009/02/19/we-all-guessed-wrong/">Lipton's blog</a>:</p>

<blockquote>
  <p>There is one more comment I must add. Robert [Szelepcsényi] was a student when he solved the problem. The legend is that he was given a list of homework problems. Since he missed class he did not know that the last problem of his homework was the famous unsolved LBA question. He turned in a solution to the homework that solved all the problems. I cannot imagine what the instructor thought when he saw the solution. Note, it is rumored that this has happened before in mathematics. Some believe this is how Green’s Theorem was first solved. In 1854 Stoke’s included the “theorem” on an examination. Perhaps we should put P=NP on theory exams and hope ...</p>
</blockquote>

CC BY-SA 3.0
2011-04-21T18:57:53.010Z
Nota: Immerman's first name is Neil.  Szelepcsenyi's is Robert.
Michaël Cadilhac
CC BY-SA 3.0
2011-04-22T08:10:55.347Z
Lipton's quotation is great!
Lamine
CC BY-SA 3.0
2011-04-28T21:07:19.430Z
"An event in Dantzig's life became the origin of a famous story in 1939 while he was a graduate student at UC Berkeley. Near the beginning of a class for which Dantzig was late, professor Jerzy Neyman wrote two examples of famously unsolved statistics problems on the blackboard. When Dantzig arrived, he assumed that the two problems were a homework assignment and wrote them down. According to Dantzig, the problems "seemed to be a little harder than usual", but a few days later he handed in completed solutions for the two problems, still believing that they were an assignment that was overdue"
Christopher Monsanto
CC BY-SA 3.0
2011-04-29T15:47:04.283Z
@fahrenheit: Great comment! Here's the source: http://en.wikipedia.org/wiki/George_Dantzig#Mathematical_statistics.
Sadeq Dousti
CC BY-SA 3.0
2011-04-21T18:53:35.980Z
2011-04-22T20:57:19.650Z
2011-04-22T20:57:19.650Z
Sadeq Dousti
<p>I've been on the other side of this I'm sure.. However, sometimes it isn't really necessary for there to be an answer to have students learn. The process of trying many different approaches to solving a problem is often more important than the outcome. </p>

<p>Personally, I would go to class the next day and say I don't expect that many of you got the answers but let's talk about what steps you used to try to figure it out. If that isn't a real world type of question I don't know what is(used by many job interviewers). </p>

<p>We sometimes get side tracked with learning facts and getting answers that we don't talk about the process which in itself can tell you more about where your students (or even you) are.
-j</p>

CC BY-SA 3.0
2011-04-21T22:08:03.050Z
2011-04-21T22:08:03.050Z
jamesC
<p>This answer is possibly as useful as a stable door, but it's for this reason that I have a rule never to set homework exercises that I haven't already solved myself.  This is not only so that I know it's solvable, but also to check that it's the right length and level - I implemented this rule after once or twice getting caught with setting questions that were too hard or required things that the students hadn't done yet.</p>

CC BY-SA 3.0
2011-04-28T21:01:56.057Z
2011-04-28T21:01:56.057Z
SCurtis
<p>One of my professors in graduate school assigned a problem he later realized he couldn't solve.  He emailed everyone explaining the situation and turning it into an extra credit problem.  It really motivated me to solve it (which took hours), but it was a lot of fun.</p>

CC BY-SA 3.0
2011-04-25T00:14:19.517Z
hours??? I had problems which I tried to solve for YEARS!
trg787
CC BY-SA 3.0
2011-04-25T00:18:13.617Z
And never solved them, of course.
trg787
CC BY-SA 3.0
2011-04-23T21:15:40.220Z
2011-04-23T21:15:40.220Z
Lucas Wiman
<p>I'm a TA.</p>

<p>I think you should "Obsess on the problem until you solve it". Afterwards, simplify it such that parts of it or hints can be handed out. As one example, the simplification step could be to divide the problem into small subproblems  and these subproblems can be then be given as subquestions to the original. For your example-question that could be as simple as "reduce the problem to another O(n)-problem that we have just taught you how to solve" and "prove that it is a linear time reduction".</p>

<p>With programming exercises there can often be some boilerplate that they wont learn that much from, which can be handed out as skeleton-code. On an Operating Systems class we recently posed the assignment "Implement a FAT32 driver in your kernel" (which they had created over the previous course-assignments). That required way more code than we expected, so we handed out a lot of code handling FAT access, that actually made some students do it. Such a huge assignment was of course an error, so next year we will probably try with ext2 or MINIX. Those who did the majority of the assignment really enjoyed that it was a realistic file system which they themselves had used. Those who only did parts of it (e.g. only just realised they had to endian-conversion) also got it approved.</p>

<p>So my suggestions are: Hand out subquestions, hints and skeletons. Be lenient when correcting.</p>

CC BY-SA 3.0
2011-04-24T03:00:55.753Z
This is exactly what I've done in these situations: obsess until I find an answer, then give strong hints to make the problem doable for undergrads.
Fixee
CC BY-SA 3.0
2011-04-23T23:41:03.730Z
2011-04-23T23:41:03.730Z
Martin Dybdal
<p>Yes, sadly, I've done this several times, as well as the <em>slightly</em> more forgivable sin of assigning a problem that I <em>can</em> 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):</p>

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

<p>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.)  <em>Educational</em>, sure, but not fair.</p>

<p>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.)</p>

<p>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 <strong>LOT</strong> of extra credit and a recommendation letter.</p>

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

CC BY-SA 3.0
2011-04-24T20:08:08.640Z
This is a great answer.  My approach in the past has always been a little different: I'll obsess until I solve the problem, then give strong hints.  Sometimes, out of guilt, I'll give away the answer as a "hint" with the apology that "the problem was a bit harder than I had intended".
Fixee
CC BY-SA 3.0
2011-04-24T07:06:15.250Z
2011-04-24T07:06:15.250Z
Jeffε
<p>This question is targeted at people who assign problems: teachers, student assistants, tutors, etc.</p>

<p>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.</p>

<p>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.</p>

<p>My question: what do you think is the "professional" thing to do:</p>

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

<p><strong>Note:</strong> 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.</p>

CC BY-SA 3.0
2011-04-21T19:08:45.563Z
In this case, I'd recommend obsessing until you solve it ... I suspect the problem isn't all that hard. But if you can't solve it, the professional thing to do is confess this to the students, and either cancel it or (as recommended in Sadeq's answer) make it extra credit.
Peter Shor 
CC BY-SA 3.0
2011-04-21T19:14:08.957Z
A graph does not have an odd length cycle if and only if it is bipartite -> BFS.
5501
CC BY-SA 3.0
2011-04-21T20:04:08.210Z
@5501: That was my initial thought when I assigned the problem, and it's correct for undirected graphs.  For digraphs things get harder.
Fixee
CC BY-SA 3.0
2011-04-21T20:49:10.853Z
A digraph has an odd cycle iff at least one of its strongly connected components is non-bipartite as an undirected graph. So if you've already talked about both strong connectivity and bipartiteness, this still might make a good exercise.
David Eppstein
CC BY-SA 3.0
2011-04-21T21:07:35.160Z
@Fixee: Sorry, I did not see that it was a digraph.
5501
CC BY-SA 3.0
2011-04-21T22:47:14.000Z
We had a similar case in our complexity course this semester: prove that Linear Integer Programming is NP-complete. The difficult part is showing that the problem is in NP (see C. Papadimitriou, "On the complexity of integer programming", 1981).
Kaveh
CC BY-SA 3.0
2011-04-22T01:50:50.180Z
@Fixee: I don't think it's as terrible or embarrassing as it looks. You can simply put a note on the course website saying that the problem was harder than what you expected. Then either revise the problem, give more hints or make it a bonus question. Science is full of uncertainty, so a little bit of uncertainty in the course is fine! :-)
Dai Le
CC BY-SA 3.0
2011-04-22T04:58:57.863Z
@David: You are correct (of course). But this was not immediately obvious to me when I realized a simple BFS would not suffice.  I did eventually focus on strongly-connected graphs which makes the problem easier.  I normally do not talk about bipartite graphs, but we do Kosaraju's algorithm for SCCs and that with DFS makes this problem tractable for them (after a few hints).
Fixee
CC BY-SA 3.0
2011-04-22T10:32:47.790Z
From the student point of view, the most successful and fair solution is to award extra credit to the ones who solved it (how much depends on how hard it was) and grade the rest of the solutions giving more weight to the approach rather than the result (this should be always be true, but in this case, even more).
chazisop
CC BY-SA 3.0
2011-04-22T19:46:06.583Z
Whatever you do, be honest and do not punish students for your mistake. Btw, we got exercises that were actually unsolvable for subtle reasons once. The points were removed from the total achievable sum but awarded points counted.
Raphael
<soft-question><teaching>
Have you ever realized you can't solve the homework you assigned?
Fixee
# Have you ever realized you can't solve the homework you assigned?

(Asked by: username_0 on 2011-04-21)

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.

**Tags:** soft-question, teaching
> **Comments:**
> **username_1**: In this case, I'd recommend obsessing until you solve it ... I suspect the problem isn't all that hard. But if you can't solve it, the professional thing to do is confess this to the students, and either cancel it or (as recommended in Sadeq's answer) make it extra credit.  
> **username_2**: A graph does not have an odd length cycle if and only if it is bipartite -> BFS.  
> **username_0**: @5501: That was my initial thought when I assigned the problem, and it's correct for undirected graphs.  For digraphs things get harder.  
> **username_3**: A digraph has an odd cycle iff at least one of its strongly connected components is non-bipartite as an undirected graph. So if you've already talked about both strong connectivity and bipartiteness, this still might make a good exercise.  
> **username_2**: @Fixee: Sorry, I did not see that it was a digraph.  
> **username_4**: We had a similar case in our complexity course this semester: prove that Linear Integer Programming is NP-complete. The difficult part is showing that the problem is in NP (see C. Papadimitriou, "On the complexity of integer programming", 1981).  
> **username_5**: @Fixee: I don't think it's as terrible or embarrassing as it looks. You can simply put a note on the course website saying that the problem was harder than what you expected. Then either revise the problem, give more hints or make it a bonus question. Science is full of uncertainty, so a little bit of uncertainty in the course is fine! :-)  
> **username_0**: @David: You are correct (of course). But this was not immediately obvious to me when I realized a simple BFS would not suffice.  I did eventually focus on strongly-connected graphs which makes the problem easier.  I normally do not talk about bipartite graphs, but we do Kosaraju's algorithm for SCCs and that with DFS makes this problem tractable for them (after a few hints).  
> **username_6**: From the student point of view, the most successful and fair solution is to award extra credit to the ones who solved it (how much depends on how hard it was) and grade the rest of the solutions giving more weight to the approach rather than the result (this should be always be true, but in this case, even more).  
> **username_7**: Whatever you do, be honest and do not punish students for your mistake. Btw, we got exercises that were actually unsolvable for subtle reasons once. The points were removed from the total achievable sum but awarded points counted.  

---

## 6 answers

### Answer by username_17 on 2011-04-24. Score: 28 | Accepted answer

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):

1. Immediately and publicly admit the mistake. Explain steps 2 and 3.
2. Give every student full credit for the problem. Yes, even if they submit nothing.
3. 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.

> **Comments:**
> **username_0**: This is a great answer.  My approach in the past has always been a little different: I'll obsess until I solve the problem, then give strong hints.  Sometimes, out of guilt, I'll give away the answer as a "hint" with the apology that "the problem was a bit harder than I had intended".  

---

### Answer by username_8 on 2011-04-21. Score: 18

I'm not a teacher yet, but as a TA, I once did this.

I didn't find the problem in a textbook; instead, I came up with the problem myself. It turned out that, in spite of looking innocent, the problem had been the subject of a lot of debate back in 1980s, but was settled then.

Well, after knowing that, I announced that solving that problem has extra credit. No one came up with the correct result, but I gave half the (extra) mark to those whose answers were reasonable. Then, in the class, I admitted that this had been indeed a hard problem, and pointed the students to the relevant history.

**PS1:** The problem was about the DES cipher: Are there a plaintext (P) and a ciphertext (C) such that, for two distinct keys K1 and K2, DES enciphers P to C under both keys? That is, C = DES(P, K1) = DES(P, K2).

The answer seemed to be "NO," but turned out that was not the case. See the relevant research here: [How easy is collision search? New results and applications to DES](http://www.springerlink.com/content/8yh6t8rru264cg4w/).

**PS 2:** The [Immerman–Szelepcsényi theorem](http://en.wikipedia.org/wiki/Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem) has been proved in much the same way! Quoting from [Lipton's blog](http://rjlipton.wordpress.com/2009/02/19/we-all-guessed-wrong/):

> There is one more comment I must add. Robert [Szelepcsényi] was a student when he solved the problem. The legend is that he was given a list of homework problems. Since he missed class he did not know that the last problem of his homework was the famous unsolved LBA question. He turned in a solution to the homework that solved all the problems. I cannot imagine what the instructor thought when he saw the solution. Note, it is rumored that this has happened before in mathematics. Some believe this is how Green’s Theorem was first solved. In 1854 Stoke’s included the “theorem” on an examination. Perhaps we should put P=NP on theory exams and hope ...

> **Comments:**
> **username_9**: Nota: Immerman's first name is Neil.  Szelepcsenyi's is Robert.  
> **username_10**: Lipton's quotation is great!  
> **username_11**: "An event in Dantzig's life became the origin of a famous story in 1939 while he was a graduate student at UC Berkeley. Near the beginning of a class for which Dantzig was late, professor Jerzy Neyman wrote two examples of famously unsolved statistics problems on the blackboard. When Dantzig arrived, he assumed that the two problems were a homework assignment and wrote them down. According to Dantzig, the problems "seemed to be a little harder than usual", but a few days later he handed in completed solutions for the two problems, still believing that they were an assignment that was overdue"  
> **username_8**: @fahrenheit: Great comment! Here's the source: http://en.wikipedia.org/wiki/George_Dantzig#Mathematical_statistics.  

---

### Answer by username_12 on 2011-04-21. Score: 6

I've been on the other side of this I'm sure.. However, sometimes it isn't really necessary for there to be an answer to have students learn. The process of trying many different approaches to solving a problem is often more important than the outcome.

Personally, I would go to class the next day and say I don't expect that many of you got the answers but let's talk about what steps you used to try to figure it out. If that isn't a real world type of question I don't know what is(used by many job interviewers).

We sometimes get side tracked with learning facts and getting answers that we don't talk about the process which in itself can tell you more about where your students (or even you) are.
-j


---

### Answer by username_13 on 2011-04-28. Score: 4

This answer is possibly as useful as a stable door, but it's for this reason that I have a rule never to set homework exercises that I haven't already solved myself. This is not only so that I know it's solvable, but also to check that it's the right length and level - I implemented this rule after once or twice getting caught with setting questions that were too hard or required things that the students hadn't done yet.


---

### Answer by username_14 on 2011-04-23. Score: 4

One of my professors in graduate school assigned a problem he later realized he couldn't solve. He emailed everyone explaining the situation and turning it into an extra credit problem. It really motivated me to solve it (which took hours), but it was a lot of fun.

> **Comments:**
> **username_15**: hours??? I had problems which I tried to solve for YEARS!  
> **username_15**: And never solved them, of course.  

---

### Answer by username_16 on 2011-04-23. Score: 4

I'm a TA.

I think you should "Obsess on the problem until you solve it". Afterwards, simplify it such that parts of it or hints can be handed out. As one example, the simplification step could be to divide the problem into small subproblems and these subproblems can be then be given as subquestions to the original. For your example-question that could be as simple as "reduce the problem to another O(n)-problem that we have just taught you how to solve" and "prove that it is a linear time reduction".

With programming exercises there can often be some boilerplate that they wont learn that much from, which can be handed out as skeleton-code. On an Operating Systems class we recently posed the assignment "Implement a FAT32 driver in your kernel" (which they had created over the previous course-assignments). That required way more code than we expected, so we handed out a lot of code handling FAT access, that actually made some students do it. Such a huge assignment was of course an error, so next year we will probably try with ext2 or MINIX. Those who did the majority of the assignment really enjoyed that it was a realistic file system which they themselves had used. Those who only did parts of it (e.g. only just realised they had to endian-conversion) also got it approved.

So my suggestions are: Hand out subquestions, hints and skeletons. Be lenient when correcting.

> **Comments:**
> **username_0**: This is exactly what I've done in these situations: obsess until I find an answer, then give strong hints to make the problem doable for undergrads.  

---

