4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ steps along $x,y$ (N,S,E,W) ? or else ? .. $\endgroup$ – G Cab Oct 20 '18 at 15:55
  • $\begingroup$ What is a step? Is the direction of that step given in any way? As written, the question leaves to many things open. $\endgroup$ – Ingix Oct 20 '18 at 15:55
  • $\begingroup$ the ant can move in the xy plane in any direction :) $\endgroup$ – Lance Oct 20 '18 at 15:58
  • $\begingroup$ I don't think there is such a condition. For example, consider that the ant always moves along the positive direction of the x axis. After the n steps, it will not be on the origin, so a condition on the lengths will never be enough to force it to end there. $\endgroup$ – J. C. Oct 20 '18 at 16:14
  • $\begingroup$ sorry, I didn't explain well: the ant can mone in any direction but she also tries to come back to the origin... now the text is edited $\endgroup$ – Lance Oct 20 '18 at 16:23
2
+50
$\begingroup$

$\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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.