0

So there are two people, person A and person B, walking their own route at the same time. These routes take an arbitrary amount of time to walk and they start at an arbitrary point along this route. So if we take an intersection point p, I would like to know if they ever meet on that point.

So I thought of the problem like this:

There is a certain intersection time in a round $I_A$ at which person A is at the intersection point. So if $r_A$ is the time it takes for A to finish one route then $I_A \equiv t \mod r_A$ (where $t$ is the time, with $t = 0$ being at the start of the hike).

For B this would be the same, so: $I_B \equiv t \mod r_B$. I have also rewritten this expression to $t = r_B \cdot k + I_B = r_A \cdot l + I_A$ where $k, l \in \mathbb{N}$

However, I couldn't really find any solutions. (Or the infinite set of solutions that should be there or not).

Yadeses
  • 171

1 Answers1

1

In general there does not need to be a solution. Assume that person A walks on the real line between 0 and 1 back and forth with speed 1 and person B walks between 1 and $1+\pi$ back and forth with speed 1. Now depending on the starting point of person A and B they will meet either never or once. Assume that they meet a second time, then person B has walked a distance $2n\pi$ with some $n\in \mathbb{N}\setminus \{0\}$ and person A has traveled a distance $m\in \mathbb{N}\setminus\{0\}$. As both are moving with the same speed the two distances have to be equal, but this implies $\pi=\frac{m}{2n}\in \mathbb{Q}$, which is a contradiction. Hence, they can meet at most once. Meeting once is easy, just let them both start at the intersection point. If on the other hand person A starts at 0 and person B starts at $1+\pi$ then they will never meet (by essentially the same argunent like before that they can meet at most once).

Added: If you want to attack this problem in full generality, you will realise that it is not so easy. If $I_A=I_B$ then you are asking whether $r_A$ and $r_B$ are linearly independent over $\mathbb{Q}$. It is for example not so easy to prove that $\pi$ and $\ln(2)$ are not linearly independent over $\mathbb{Q}$ (check Are $\pi$ and $\ln(2)$ linearly independent over rational numbers?).

Severin Schraven
  • 19,179
  • Hmm that is true indeed. Though that still would not answer the question of how to find a solution (if there is one given) some random input variables. Like finding the lowest t for which the equation holds true. – Yadeses Aug 29 '18 at 02:10
  • Well, yes, that's a question you did not ask :) I just answered the question whether they will meet in the intersection point. I am not sure whether it is possible to give an algorithm for finding the smallest solution. If all the coefficients were rational, the problem would be easier as you could use methods from diophantine equations – Severin Schraven Aug 29 '18 at 07:30
  • @Yadeses I added some argument why you should not expect to have an algorithm to solve your equation in the generality you proposed. – Severin Schraven Aug 30 '18 at 22:04
  • And if we just think about integers? I have searched diophante equations and I get their idea, but how to find a solution I do not see. Could you maybe explain how that would work? – Yadeses Aug 30 '18 at 23:24
  • Okay, google apparently had the answer as this form has already been solved. So basically write it as the from ax + b y = 1, and then use euclides algorithm, right? – Yadeses Aug 30 '18 at 23:30
  • @Yadeses Indeed, using the euclidean alogorithm you get everything. Also, you can allow rational coefficients (then multiply with the common denominator and reduce to the case of integer coefficient). – Severin Schraven Aug 31 '18 at 09:42