Which particle stays closest to the zero vector?

Question

This question comes from the following challenge at Day 20 of Advent of Code 2017.

Here, you are presented with a simulation consisting of a thousand particles, each with a set of three 3D vectors:

• an inital position $p_0$
• an initial velocity $v_0$
• a constant acceleration, $a$.

The simulation progresses in discrete ticks, starting at $t=0$. Each tick, $t$, all particles are updated simultaneously.

• First, a new velocity, $v_t$ is calculated by adding the acceleration, $a$ to the previous velocity $v_{t-1}$. In other words, $v_t = v_{t-1} + a$, when $t > 0$.
• Second, a new position is calculated by adding the new velocity, $v_t$, to the previous position, $p_{t-1}$. In other words, $p_t = p_{t-1} + v_t$, when $t > 0$.

The position over time can also be expressed as the following quadratic equation:

$P(t) = {\frac 1 2}at^2 + ({\frac 1 2}a + v_0)t + p_0$

Distances in this simulation are calculated as the manhattan distance, which is the sum of the absolute values of each component in the position vector, $p$.

The challenge poses the following question:

Which particle will stay closest to position $\langle0,0,0\rangle$ in the long term?

In my programming language of choice, I have managed to implement a couple of solutions that come up with the correct answer for the input I am given. However, I am not completely satisfied with these solutions.

I was wondering if there was a more elegant way to express a solution using a more mathematical approach, so to speak.

For example, it may be possible to compare the manhattan distances of two given particles, as $t$ approaches infinity. As my math skills are quite limited, I'm having trouble seeing how to express this.

Note 1: In this scenario, the particles do not interact with each other in any way.

Note 2: The particles may have similar or even equal acceleration and velocity vectors.

Note 3: All vector components are integers.

Answer 1

To add to Ross Millikan's answer, you can begin by minimizing $||\vec a||$ (note that this is the Manhattan magnitude, not the euclidean one). If two particles have exactly the same acceleration, we'll have to define a few more functions.

Using the sign function

$$\text{sgn}(x)=\begin{cases}-1 & x<0 \\ 0 & x=0 \\ 1 & x>0 \end{cases}$$

We can define $\text{sgn}(\vec x)$ to apply elementwise to vectors.

With equation of motion you derived, we can directly evaluate the magnitude:

$$\vec p(t)=\frac 12\vec at^2+\left(\frac 12\vec a+\vec v_0\right)t+\vec p_0$$

$$||\vec p(t)||=\sum_i\left|\frac 12a_it^2+\left(\frac 12a_i+v_{0, i}\right)t+p_{0, i}\right|$$

Using the identity $a>b\implies |a+b|=|a|+b\ \text{sgn}(a)$, as well as knowing $t^2>>t>>1$, we can simplify:

$$||\vec p(t)||=\sum_i\left[\frac 12|a_i|t^2+\text{sgn}(a_i)\left(\frac 12a_i+v_{0, i}\right)t+\text{sgn}(a_i)p_{0, i}\right]$$

Or, using vector notation, with $\cdot$ indicating a dot product:

$$||\vec p(t)||=\frac 12||\vec a||t^2+\text{sgn}(\vec a)\cdot\left(\frac 12\vec a+\vec v_0\right)t+\text{sgn}(\vec a)\cdot\vec p_0$$

We still have the same hierarchy of terms, so we should minimize $||\vec a||$ first. If there are any ties, we can next minimize $\text{sgn}(\vec a)\cdot\left(\frac 12\vec a+\vec v_0\right)$. Again, if multiple particles give the same value, we then minimize $\text{sgn}(\vec a)\cdot\vec p_0$. Any particles for which all three are equal will always be equidistant from the origin.

Answer 2

In the long term the acceleration term will dominate over the velocity term. This will occur about when $\frac {\frac 12at^2}{vt}=\frac {at}{2v} \gt 1$, so just take the particle with lowest magnitude of acceleration. You don't need to worry about initial velocity or position as they will get swamped by the acceleration. If the accelerations are reals there should not be two particles with exactly the same magnitude of acceleration. Any small difference is enough.