17
$\begingroup$

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!

  • 0
    You want one fixed track (line) for each point. Is that right? The intro might be clearer if you defined the tracks first, then put a moving point on each track.2012-09-11
  • 0
    Can each point move at its own distinct constant speed, or are all of the points moving at the same speed?2012-09-11
  • 1
    To your first question, yes. Each point has it's own track. Also, each point move at its own distinct constant speed.2012-09-11
  • 1
    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.2012-09-11
  • 2
    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.2012-09-11
  • 1
    Is this obvious for $3$ points?2012-09-11
  • 0
    @mjqxxxx Given the general position of the tracks, if pucks $A$ and $B$ bounce off each other at some point $X$, puck $A$ needs to hit a third puck $C$ after $t$ units of time to avoid going to infinity. With no fourth puck, puck $A$ returns to $X$ at time $2t$, where puck $B$ needs to have simultaneously returned for another bounce. That means puck $B$ needed to change direction at time $t$ as well. And this would require puck $C$ to have been in two places at once.2012-09-11
  • 1
    @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.2012-09-12
  • 0
    If we did not forbid the points to lie on intersection lines, then we could have one of them move at speed $0$ and find a configuration, I guess that's why the condition is needed - that made me wonder: Is speed $0$ allowed?2012-09-12
  • 1
    @rattle: no, it's not allowed.2012-09-12
  • 0
    It's simple to construct a periodic configutarion with $7$ points (or more), so if you can't do it with $5$ points it's a rather special case.2012-09-15
  • 1
    @Feanor: would you please show us your construction? Thanks a lot.2012-09-16

2 Answers 2

1

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.

0

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
    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.2012-09-16
  • 0
    You're right, I completely overlooked it.2012-09-16
  • 0
    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.2012-09-18
  • 0
    @joriki : Done.2012-09-18