Suppose we have $5$ points in plane, each lying on a line for which no three of these lines intersect in one point, and also non of these $5$ points is an intersection point of two lines. At time $t=0$, each of the points starts to move on its own line in an arbitrary direction and with an arbitrary but constant positive speed. Each point keeps going unless it meets another point. When so, the two points reverse their directions and go back the path they've come. Prove that after some finite time $T$, one of the points will never meet anymore points.

This problem popped into my mind some weeks ago. I kept thinking about it for a long while, but I couldn't reach anything. All the answers are welcomed!

  • 1
    $\begingroup$ To your first question, yes. Each point has it's own track. Also, each point move at its own distinct constant speed. $\endgroup$ – Goodarz Mehr Sep 11 '12 at 18:34
  • 1
    $\begingroup$ And I don't quite get the condition "none of these 5 points is an intersection point of two lines". This could make sense to me initially, but after some time has elapsed and two points encounter each other at the same time, then certainly at that moment two tracks are intersecting right there. $\endgroup$ – alex.jordan Sep 11 '12 at 18:39
  • 2
    $\begingroup$ Note that for an even number of points, this would not be true: you could have the points moving on a $2n$-gon, alternately clockwise and counterclockwise, so that at integer times each point reaches a vertex, collides with its neighbour, and reverses direction. $\endgroup$ – Robert Israel Sep 11 '12 at 18:56
  • 1
    $\begingroup$ Is this obvious for $3$ points? $\endgroup$ – mjqxxxx Sep 11 '12 at 19:01
  • 1
    $\begingroup$ @alex.jordan: I meant that only at the initial position, non of the points is an intersection point of two lines. It's obvious when they start moving, they may meet each other. $\endgroup$ – Goodarz Mehr Sep 12 '12 at 3:04

Just in case this helps someone. Let an initial "configuration" be associated with a $n \times n$ matrix $M$ ($n=5$ in the original question), with integer values, with dummy placeholders in the diagonal, and such that each row contains different values, not all negative or positive. Starting from an initial configuration, each iteration does the following:

  • decrement all values by one $m_{i,j} := m_{i,j}-1$ ($i\ne j$)
  • look for pairs of symmetric zeroes ($m_{i,j}=m_{j,i}=0$) and negate each corresponding row: $m_{i,k} := - m_{i,k}$ $m_{j,k} := - m_{j,k}$

This procedure will either eventually produce some all-negative row ("the point has escaped"), or repeat in a cycle. The conjecture would be that with $n=5$ ( perhaps for all odd $n$?) there cannot be such a cycle.

This model is slightly more general (and hence the impossibility conjecture is stronger) than the original problem ($m_{i,j}$ represents the distance from point $i$ to the line of point $j$, positive if it's approaching it) because it does not take into account the restrictions of having the points along straight lines.


Disclaimer: This does not answer the original question, since I overlooked a crucial assumption. I don't think it's a valid reason for deletion - this answer probably does no harm. Please don't upvote, though ;)

As requested in the comments, I present the construction of $7$ points in a periodic configuration, with each point moving at velocity $1$.

To begin with, imagine that there is a point $A$ and a ball (my name for point, to avoid confusion) $x$ such that it is guaranteed that if $x$ reaches $A$ and then collides with another ball, then it will return to $A$ after a fixed time (say, $\Delta t =1$). Then we can construct a periodic configuration with three additional points, as follows:

Pick points $B,C$ so that the triangle $ABC$ is equilateral with edge length $1$. Suppose $x$ is about to reach $A$ at time $t=0$. At time $t=-0.5$, place balls $a,b,c$ at midpoints of $BC,CA,AB$ respectively, with $a,b$ directed towards $C$ and $c$ direcred towards $A$. At time $t = 0$ we have two collisions: $c,x$ at $A$ and $b,a$ at $C$. As assumed, at $t=1$ the ball $x$ will return to $A$. At time $t=0.5$, all $a,b,c$ are at midpoints of appropriate sides, with $a,c$ moving towards $B$, $b$ moving towards $A$, and it's $0.5$ time untill $x$ reaches $A$ --- so it's exactly the same as at $t=-0.5$, up to relabelling. Thus, the balls will keep moving like this indefinitely.

To construct the configuration for $7$ balls, just take two equilateral triangles $ABC$, $A'B'C'$ with side lengths $1$ nad $\lvert A A' \rvert = 0.5$, place a ball $x$ with velocity $1$ between $AA'$, and repeat the construction above for both $A$ and $A'$.

For instance, at $t= -0.5$ it could be the case that $x$ and $b'$ are at $A'$, $x$ moving to $A'$ and $b'$ moving to $C'$; $a'$ and $c'$ are at $B$, $a'$ moving to $B'$ and $c'$ moving to $B'$; $a,b,c$ are at midpoints of $BC,CA,AB$ respectively, with $a,b$ moving to $C$ and $c$ moving to $A$.

This construction can be used directly to provide examples for any odd number no less than $11$: just add a $2k$-element periodic cycle hinted at in the comments. Unfortunately, this does not work with $9$ balls, but I believe the above idea can be extended to work for $9$ balls as well. I think it should be possible to find a periodic configuration with $5$ balls + extra ball, and then use it to construct a periodic configuration with a tringle connected to a pentagon (much like the above was a triangle connected to another triangle).

I think the above shows that, if there is no periodic configuration with $5$ balls, then it a rather special case and a peculiarity of number $5$ - not a general property of odd numbers.

  • 1
    $\begingroup$ Nice construction, but you didn't notice the condition that No three of the lines should intersect in one point. Without this condition, making an example for $5$ is also easy, just consider $5$ points on sides and one diagonal of a square. $\endgroup$ – Goodarz Mehr Sep 16 '12 at 11:19
  • $\begingroup$ You're right, I completely overlooked it. $\endgroup$ – Jakub Konieczny Sep 16 '12 at 11:35
  • $\begingroup$ It think you should note at the top of the post that it doesn't answer the question; people might not read the comments before reading through the entire answer. $\endgroup$ – joriki Sep 18 '12 at 11:27
  • $\begingroup$ @joriki : Done. $\endgroup$ – Jakub Konieczny Sep 18 '12 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.