Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
14  
This is part (a) of problem 11524 in the October 2010 issue of the American Mathematical Monthly. –  Byron Schmuland Apr 26 '11 at 17:46
3  
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. –  Joseph O'Rourke Apr 26 '11 at 17:55
1  
... and Luke asked you this around last October ??? –  Gerald Edgar Apr 26 '11 at 18:55
2  
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). –  Pietro Majer Apr 26 '11 at 22:17
1  
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. –  Gjergji Zaimi Apr 27 '11 at 3:07
show 5 more comments

closed as not a real question by Ryan Budney, Cam McLeman, Gerry Myerson, fedja, Harry Gindi Apr 27 '11 at 4:40

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

3 Answers

up vote 5 down vote accepted

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

share|improve this answer
add comment

One word: AoPS

share|improve this answer
    
This proposed solution is hard to understand. There is a typo in claim 2). –  Andrew Stout Apr 27 '11 at 5:39
    
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. ;) –  fedja Apr 27 '11 at 12:01
    
oh. i see. different culture there. –  Andrew Stout Apr 27 '11 at 16:03
add comment

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.

share|improve this answer
2  
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? –  darij grinberg Apr 26 '11 at 17:35
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.