Find the least $n\in N$ such that among any $n$ rays in space sharing a common origin there exist two which form an acute angle.
Problem
Source: Romanian TST 2001
Tags: vector, induction, linear algebra, combinatorics proposed, combinatorics
16.01.2011 18:51
I think the answer is $n=5$. If there are three rays, then they can be at a distance of $120^{\circ}$ from each other. If there are four rays, they can be at a distance of $90^{\circ}$ from each other. For five rays, let the angles be $a, b , c, d, e$ and we have $a, b, c, d, e\ge 90^{\circ}\Longrightarrow a+b+c+d+e>360^{\circ}$ which is the angle around a point. So, there exists two which form an acute angle. [Edit: Above proof holds only for the rays in a plane]
16.01.2011 19:26
"Space" is not the same thing as "the plane."
16.01.2011 19:27
NO. The answer above is correct in the plane, not in the (three dimensional) space. In general, in the space $\mathbb{R}^d$ of dimension $d$, we need at least $2d +1$ vectors, since a set of $d$ vectors along the axes of an orthogonal system, together with their opposites, has no acute angle. The proof is by induction, using specific (and not too hard) linear algebra techniques.
17.01.2011 06:09
JBL wrote: "Space" is not the same thing as "the plane." mavropnevma wrote: NO. The answer above is correct in the plane, not in the (three dimensional) space. Sorry, my mistake. Didn't read the question properly.
25.03.2015 07:29
I have an idea. We need to have sufficiently many vectors such that the cosine of the angle between two of them is positive. Using the dot product, this is equivalent to having two vectors $(x_1,y_1,z_1)$ and $(x_2,y_2,z_2)$ such that $0<(x_1x_2+y_1y_2+z_1z_2)$. First if none of our vectors have $x,y$ or $z$ are zero, then are $8$ possibilities for the sign (positive or negative) of $(x,y,z)$. If two of our vectors have the same sign combination, the dot product is obviously positive. We ignore $(0,0,0)$ since this is not a ray. Thus $8$ vectors suffices. Now mavropnevma says $7$ suffices. So maybe we can do this without induction? It's quite late and its likely that I have made a mistake with considering the vectors with one component is zero, so actually this argument might only be able to show that some number much greater than $8$ vectors suffices. In any case, please someone post a solution to this beautiful problem.
25.03.2015 12:42
Let us prove that the largest number of not-null vectors in $\mathbb{R}^d$, of pairwise non-positive dot-products, is $2d$. We will proceed by simple induction on $d$, starting with the obvious case $d=1$. In dimension $d+1$, let $u$ be one of the vectors. Denote by $U = \ <u>^{\perp}$ the orthogonal complement of $u$, of dimension $d$. Any of the other vectors $v$ can now be uniquely written as $v = v_{\perp} + v_{\dashv}$, with $v_{\dashv} = \dfrac {\left <u, v\right >} {||u||^2} u$, thus $v_{\perp} \perp u$, i.e. $v_{\perp} \in U$. Notice that the coefficients $\dfrac {\left <u, v\right >} {||u||^2}$ are non-positive under our conditions, and also notice that we can only have $v_{\perp} = 0$ once, for some $u' = v$ (trivially so, since then $u' = u'_{\dashv} = \lambda u$ for some negative real $\lambda$). Let us consider next the orthogonal components $v_{\perp} \in U$, whence $\left <v,w\right > = \left <v_{\perp} + v_{\dashv}, w_{\perp}+w_{\dashv}\right > = \left < v_{\perp}, w_{\perp}\right > + \left <v_{\perp}, w_{\dashv}\right > + \left <v_{\dashv}, w_{\perp}\right > + \left <v_{\dashv}, w_{\dashv}\right > = \left < v_{\perp}, w_{\perp}\right > + \dfrac {\left <u,v\right > \left <u,w\right >} {||u||^2}$, and therefore $\left < v_{\perp}, w_{\perp}\right > = \left <v,w\right > - \dfrac {\left <u,v\right > \left <u,w\right >} {||u||^2} \leq 0$, since $\left <v,w\right > \leq 0$ and $\left <u,v\right > \left <u,w\right > \geq 0$. We fall under the induction hypothesis, so the number of the not-null vectors is at most $2d$, therefore (together with $u$ and possibly $u'$) there were at most $2(d + 1)$ not-null vectors for dimension $d+1$, and the induction is completed. To build a model, notice further that in order to achieve the bound we must have the pair $u$, $u'$, with all other vectors orthogonal to them. By inductive reasoning it follows that the only possible model is made by some $d$ pairwise orthogonal not-null vectors, and some other $d$, obtained from them by multiplication with arbitrary negative scalars. In a similar way, we can prove that the largest number of vectors in $\mathbb{R}^d$, of pairwise negative dot-products, is $d+1$.
25.03.2015 20:07
I do not understand your proof, probably because of the linear algebra terminology and notation. Could you state the proof in more understandable terms (just for $d=3$)?
05.06.2021 06:17
$n=7$ use Area of Spherical cap
05.06.2021 06:27
Very similar to the https://artofproblemsolving.com/community/c893771h1897981p12965429