As an amusement at the start of this talk, Moshe Rosenfeld poses the following question.
Suppose that there are n salmon which begin at distinct points on a unit circle, each facing either clockwise or counterclockwise. On a signal, each salmon moves around the circle in its chosen direction at a constant speed (the same for all salmon). When two salmon meet, they both instantly reverse directions. If any salmon ever returns to its starting point, it dies. (If two salmon meet at one of their starting points, there is a death and no change of direction; as Rosenfeld says, "Death comes first.")
- Is it true that all the salmon will eventually die?
- (assuming the answer to part 1 is yes) Give an algorithm to find the last survivor.
I spent a certain amount of time on buses and planes tinkering with this. It's quite easy to show that every configuration is preperiodic, as a start. I have some ideas about how one might finish. Eventually I decided just to look for more information on the problem, with no real success.
One of the themes of his talk is how some problems become popular and some gather dust on the shelf. Is the latter what happened to this problem?
His second question is a bit mysterious. The problem setup itself is algorithmic in nature, so what does it mean? Is there anything besides "elegance" that would distinguish the kind of answer we should have in mind from a stupid answer like "just watch the salmon"? ("Running time" could be an answer, but it seems likely that just letting the salmon swim wouldn't take all that long.)
I am really asking three subquestions on this topic.
- Did this question ever get solved or taken up seriously? If so, where?
- Is there a natural, nonvacuous interpretation of the second part of the question?
- What is the solution? (This is actually the subquestion I am least interested in, but it felt wrong not to ask it.)
(Please feel free to re-tag, still getting used to things here.)