Strange succession

137 Views Asked by At

An ant starts from the origin of a cartesian plane and makes $n \ge 2$ steps of lengh $d_1, d_2, \cdots, d_n$. Is there a condition (necessary and sufficient) on $d_i$'s for which the ant can come back to the origin after the $n$ steps? (The ant can move in any direction.)

I think the claim is $d_i \leq \sum\limits_{j ≠ i} d_j$ for all $i$, which of course is necessary, but I cannot prove it is sufficient.

2

There are 2 best solutions below

0
On BEST ANSWER

$\def\vec{\overrightarrow}$If the ant is assumed to be smart enough to select the right direction in each step, then the problem can be restated as:

Given $d_1, \cdots, d_n > 0$. Find the necessary and sufficient condition under which there exist vectors $v_1, \cdots, v_n \in \mathbb{R}^2$ such that $|v_k| = d_k$ and $\sum\limits_{k = 1}^n v_k = \vec{0}$.

And your condition is indeed necessary and sufficient.

Necessity: If there exist vectors $v_1, \cdots, v_n \in \mathbb{R}^2$ such that $|v_k| = d_k$ and $\sum\limits_{k = 1}^n v_k = \vec{0}$, then for each $k$,$$ v_k = \sum_{j ≠ k} v_j \Longrightarrow d_k = |v_k| = \left| \sum_{j ≠ k} v_j \right| \leqslant \sum_{j ≠ k} |v_j| = \sum_{j ≠ k} d_j. $$

Sufficiency: For $n = 2$, $d_1 \leqslant d_2$ and $d_2 \leqslant d_1$ implies $d_1 = d_2$, thus it suffices to take an arbitrary vector $v$ with $|v| = d_1$ and take $v_1 = v$, $v_2 = -v$.

For $n = 3$, since $d_1 \leqslant d_2 + d_3$, $d_2 \leqslant d_1 + d_3$, $d_3 \leqslant d_1 + d_2$, then there exists a triangle $ABC$ (possibly degenerate) with $|AB| = d_1$, $|BC| = d_2$, $|CA| = d_3$. Thus it suffices to take $v_1 = \vec{AB}$, $v_2 = \vec{BC}$, $v_3 = \vec{CA}$.

Now assume that the condition is sufficient for $n - 1$ where $n \geqslant 4$. For $n$, denote $d = \sum\limits_{k = 1}^n d_k$, then the condition becomes $d_k \leqslant \dfrac{1}{2} d$ for each $k$. If there do not exist $k_1 ≠ k_2$ such that $d_{k_1} + d_{k_2} \leqslant \dfrac{1}{2} d$, denoting $d_{n + 1} = d_1$, then$$ 2d = \sum_{k = 1}^n (d_k + d_{k + 1}) > n · \frac{1}{2} d \Longrightarrow n < 4, $$ a contradiction. Therefore, without loss of generality, suppose that $d_{n - 1} + d_n \leqslant \dfrac{1}{2} d$. Using the induction hypothesis on $(d_1, \cdots, d_{n - 2}, d_{n - 1} + d_n)$, there exist $u_1, \cdots, u_{n - 1} \in \mathbb{R}^2$ such that$$ |u_k| = d_k\ (1 \leqslant k \leqslant n - 2),\ |u_{n - 1}| = d_{n - 1} + d_n,\ \sum_{k = 1}^{n - 1} u_k = \vec{0}. $$ Now take$$ v_k = u_k(1 \leqslant k \leqslant n - 2),\ v_{n - 1} = \frac{d_{n - 1}}{d_{n - 1} + d_n} u_{n - 1},\ v_n = \frac{d_n}{d_{n - 1} + d_n} u_{n - 1}, $$ then $|v_k| = d_k\ (1 \leqslant k \leqslant n)$ and $\sum\limits_{k = 1}^n v_k = \vec{0}$. End of induction.

0
On

Your condition is clearly necessary and there is no sufficient condition. At each step, even if the distance is right you only reach the origin if the angle you choose is exactly right, representing a point out of $[0,2\pi)$. As there are only a countable number of steps, there are only (at most) a countable number of chances to pick the right angle. The measure of a countable set of points in a line segment is zero.