Let $ u_1, u_2, \ldots, u_m$ be $ m$ vectors in the plane, each of length $ \leq 1,$ with zero sum. Show that one can arrange $ u_1, u_2, \ldots, u_m$ as a sequence $ v_1, v_2, \ldots, v_m$ such that each partial sum $ v_1, v_1 + v_2, v_1 + v_2 + v_3, \ldots, v_1, v_2, \ldots, v_m$ has length less than or equal to $ \sqrt {5}.$
Problem
Source: IMO ShortList 1988, Problem 8, France 3, Problem 11 of ILL
Tags: vector, algebra, combinatorics, combinatorial geometry, Inequality, IMO Shortlist
21.03.2016 16:49
How to deal with this?
03.01.2017 09:46
This bound can be improved to $\sqrt2$.
08.02.2017 16:36
P-H-David-Clarence wrote: This bound can be improved to $\sqrt2$. I think it isn't
23.12.2017 12:57
First we consider the question in one-division, we can prove the bound is 1. By finding the maximal length of subsum of $v_i$ (say $v=v_1+\cdot\cdot\cdot+v_k$), we can dissect $v_i$ into to vectors which are orthogonal to each other. Considering the maximal condition, the projections of vectors on $v$ is at most 1, which of $v_i(i<k)$ is positive, and negative otherwise. Applying the same process for two orthogonal directions, we can reach the bound $\sqrt{1^2+2^2}=\sqrt{5}$
01.07.2019 02:04
I think post #5 is missing some detail.
01.07.2019 11:44
@above can u tell what $<x,y>$ means ? I tried searching but couldn't find anything Thanks @below
01.07.2019 12:55
Pluto1708 wrote: @above can u tell what $<x,y>$ means ? I tried searching but couldn't find anything For any vector $u_i$, the notation $u_i=\left<x_i,y_i\right>$ means that the $x$-component of $u$ is $x_i$, and the $y$-component of $u$ is $y_i$.