8
$\begingroup$

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.")

  1. Is it true that all the salmon will eventually die?
  2. (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.

  1. Did this question ever get solved or taken up seriously? If so, where?
  2. Is there a natural, nonvacuous interpretation of the second part of the question?
  3. 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.)

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
3
$\begingroup$

Ah, irony. Now that I've publicly asked the question, I practically trip over a reference.

I just found this paper of Rosenfeld from 2008, which has large overlap with the talk mentioned in my original post. In the paper it is shown that there are initial configurations which do not lead to extinction, though little progress is made on how one might recognize these special configurations in advance.

(I'm still interested in answers to subquestion 2 above.)

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I checked the paper and there he asks another problem. Is it possible for an odd number of salmons to survive forever? I think that this is clearly not possible as if there are an odd number of salmons then the ``center of gravity'' of the salmons must be moving clockwise or counterclockwise. But this implies that sooner or later one of the salmons must make a complete cycle and thus die. What do you think? $\endgroup$
    – domotorp
    Commented Jan 20, 2010 at 21:56
  • 1
    $\begingroup$ Yes, I came up with the same basic argument. If a salmon lives forever, it has 0 average speed, but if an odd number of salmon live forever then the sum of the speeds is a nonzero constant. $\endgroup$
    – Douglas Zare
    Commented Jan 20, 2010 at 22:00
  • $\begingroup$ I agree. I'm pretty sure the "center of gravity" argument can be made rigorous, but the following argument is easier (for me) to be convinced by. If on some time interval $[t_0,\infty)$ there are no deaths, then the configuration is necessarily periodic on that time interval. Since each salmon's eventual range of motion is a closed interval (not the whole circle), each individual salmon spends as much time going one way as the other. So the total amount of time spent going clockwise in one period, summed over all salmon, equals the corresponding thing for counterclockwise. $\endgroup$
    – Cap Khoury
    Commented Jan 21, 2010 at 2:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .