22
$\begingroup$

This problem was first put to me by Luke Pebody (who did not know the answer at the time) and after some work I am yet to find a proof or counterexample. I would be grateful of any insights.

Call a vector $v$ in $\mathbb{R}^2$ 'short' if it has modulus less than 1. Let $v_1,\dots,v_6$ be short vectors such that $\sum_{i=1}^6 v_i = 0$. Prove that some three of the $v_i$ have a short sum.

$\endgroup$
10
  • 15
    $\begingroup$ This is part (a) of problem 11524 in the October 2010 issue of the American Mathematical Monthly. $\endgroup$
    – user6096
    Commented Apr 26, 2011 at 17:46
  • 3
    $\begingroup$ Interesting. If three have a short sum, then the other three must also. Because rearrangement puts the three first, and the other three must reach back to the origin. $\endgroup$ Commented Apr 26, 2011 at 17:55
  • 1
    $\begingroup$ ... and Luke asked you this around last October ??? $\endgroup$ Commented Apr 26, 2011 at 18:55
  • 2
    $\begingroup$ Note that $\sum _ {1\le i < j < k \le 6 } |v_i+v_j+v_k|^2 = 6 \sum_{i=1}^6 |v_i|^2$, so at least one of the 20 triples has modulus less than or equal to $3/\sqrt 5$ (this does not use the assumption on the dimension). $\endgroup$ Commented Apr 26, 2011 at 22:17
  • 1
    $\begingroup$ I don't even see a nice way of showing the result for 4 vectors (and two of them having a short sum), my approach is basically some ugly analysis. $\endgroup$ Commented Apr 27, 2011 at 3:07

3 Answers 3

5
$\begingroup$

Lemma 1:

If the angle, $\theta$, between two 'short' vectors, $v_1$ and $v_2$ (placed head to tail) satisfies $\theta \leq \pi/3$, then their sum is a short vector.

Proof:

Place $v_1$ at the origin, then the terminal point of $v_1$ lies within the unit ball. Placing the $v_2$ at the tail of $v_1$ creates an angle $\theta \leq \pi/3$. Any arc of radius $r < 1$ traced between $\pi/3$ and $-\pi/3$ from the terminal point of $v_1$ lies within the unit ball as well. Thus $v_1+v_2$ is a 'short' vector. $\blacksquare$

Since $\Sigma v_i = 0$ we can order the vectors in such a way as to create a convex polygon. If any of the interior angles satisfy the conditions for lemma 1, then we can reduce the problem to a polygon with fewer sides.

Lemma 2:

In a convex n-gon (n=4,5 or 6), with interior angles $\theta_i$, either $\theta_i \leq \pi/3$ for some $i$ or at least one pair of adjacent sides (as vectors) may be interchanged so that an angle less than $\pi/3$ is created.

Proof:

If $v_1$ and $v_2$ create interior angle $\alpha$ and $v_2$ and $v_3$ create angle $\beta$, then interchanging $v_2$ and $v_3$ creates an angle $\alpha+\beta-\pi$ between $v_1$ and $v_3$ (which are now adjacent by exchanging $v_2$ and $v_3$). Aiming for a contradiction, assume that this new angle, $\alpha+\beta-\pi > \pi/3$. Thus, $\alpha+\beta > 4\pi/3$. If this were true for every pair of adjacent angles in a quadrilateral, then $16\pi/3 < 2(\Sigma^4_{i=1} \theta_i)$. $\sharp$ For a 5-gon, $20\pi/3 < 2(\Sigma^5_{i=1} \theta_i)$. $\sharp$ And for a 6-gon $8\pi < 2(\Sigma^6_{i=1} \theta_i)$. $\sharp$ Thus, there exists at least one pair of adjacent vectors which may be exchanged to get an interior angle less than or equal to $\pi/3$. $\blacksquare$

Thus, in a 6-gon, we can always exchange two vectors to get the sum of two adjacent vectors to be 'short'. Replacing $v_1, ... ,v_5, v_6$ with $v_1, ... , v_4, v_5+v_6$ to get 5 'short' vectors whose sum is zero. If $v_5+v_6$ is pair-able with another vector in such a way that their sum is 'short', then we are done. Otherwise, we get two other vectors whose sum is a 'short' vector, and we reduce to the four vector case. Because we can again reduce the quadrilateral case, we are done unless we must pair the two non-"sum" vectors to get a 'short' vector. If this is the case, I claim we still have the sum of three of the original six vectors is 'short'.

Proof of claim:

Looks like fedja just beat me to it, but this was just too much to write to delete it. :P

$\endgroup$
7
$\begingroup$

One word: AoPS

$\endgroup$
3
  • $\begingroup$ This proposed solution is hard to understand. There is a typo in claim 2). $\endgroup$ Commented Apr 27, 2011 at 5:39
  • $\begingroup$ You mean the missing period? I do not see any other typos there (i=1,2 of course). Keep in mind that the AoPS culture is different: the idea of an answer there (if somebody asks for help explicitly) is to give a sketch or even just a hint that should enable the OP to solve the problem by himself, not to have everything explained in detail. ;) $\endgroup$
    – fedja
    Commented Apr 27, 2011 at 12:01
  • $\begingroup$ oh. i see. different culture there. $\endgroup$ Commented Apr 27, 2011 at 16:03
0
$\begingroup$

I think this was a problem in my graph theory class. We used Ramsey theory... I don't remember the details, but you have to force a condition on the angles that ensures modulus less than 1.

$\endgroup$
1
  • 2
    $\begingroup$ I don't think it's that easy. Again, consider the points (0,1), (0,1), (0,1), (0,-1), (0,-1), (0,-1). I don't know how you want to color them, but if you want to use R(3,3)=6 to get a monochromatic triangle, you would want to color them in such a way that two of the (0,1)'s and one (0,-1) get the same color - or the other way round. How can we define such a coloring? $\endgroup$ Commented Apr 26, 2011 at 17:35

Not the answer you're looking for? Browse other questions tagged .