Suppose $n$ lines in plane are such that no two are parallel and no three are concurrent. For each two lines their angle is a real number in $[0,\frac{\pi}2]$. Find the largest value of the sum of the $\binom n2$ angles between line. By Aliakbar Daemi
Problem
Source: Iran TST 2007, Day 3
Tags: combinatorics proposed, combinatorics
27.05.2007 18:28
Actually,If we denote by $\angle(l_{1},l_{2})$ the angle between $l_{1},l_{2}$,and $0\leq \angle(l_{1},l_{2})<\frac{\pi }{2}$ and $\measuredangle(l_{1},l_{2})$ the measured angle between $l_{1},l_{2}$($0\le\measuredangle(l_{1},l_{2})<\pi$) then$\measuredangle(l_{1},l_{2})\leq \angle(l_{1},l_{2})$ IF the n lines are $l_{1},...l_{n}$ THen For$n=2m+1$ \[\sum_{1\leq i<j\leq 2m+1}{\angle(l_{i},l_{j})}\le \sum_{1<i<j\leq m,j-i\leq m}{\measuredangle(l_{i},l_{j})}+\sum_{1<i<j\leq m,j-i\geq m+1}{\measuredangle(l_{j},l_{i})}=\frac{m(m+1)}{2}\pi \] for $n=2m$ \[\sum_{1\leq i<j\leq 2m,}{\angle(l_{i},l_{j})}=\sum_{1\leq i<j\leq 2m,j-i\leq m-1}{\angle(l_{i},l_{j})}+\sum_{1\leq i<j\leq 2m,j-i\geq m+1}{\angle(l_{j},l_{i})}+\sum_{1\leq i\leq m,j=i+m}{\angle(l_{i},l_{j})}\le \sum_{1\leq i<j\leq 2m,j-i\leq m-1}{\measuredangle(l_{i},l_{j})}+\sum_{1\leq i<j\leq 2m,j-i\geq m+1}{\measuredangle(l_{j},l_{i})}+m\frac{\pi}{2}=\frac{m^{2}}{2}\pi \] I left the detailed(i.e.how to prove $\sum_{1<i<j\leq m,j-i\leq m}{\measuredangle(l_{i},l_{j})}+\sum_{1<i<j\leq m,j-i\geq m+1}{\measuredangle(l_{j},l_{i})}=\frac{m(m+1)}{2}\pi$ and the other one) to the reader.I am busy today.........
29.05.2007 15:56
Hawk Tiger wrote: Actually,If we denote by $\angle(l_{1},l_{2})$ the angle between $l_{1},l_{2}$,and $0\leq \angle(l_{1},l_{2})<\frac{\pi }{2}$ and $\measuredangle(l_{1},l_{2})$ the measured angle between $l_{1},l_{2}$($0\le\measuredangle(l_{1},l_{2})<\pi$) then$\measuredangle(l_{1},l_{2})\leq \angle(l_{1},l_{2})$ IF the n lines are $l_{1},...l_{n}$ THen For$n=2m+1$ \[\sum_{1\leq i<j\leq 2m+1}{\angle(l_{i},l_{j})}\le \sum_{1<i<j\leq m,j-i\leq m}{\measuredangle(l_{i},l_{j})}+\sum_{1<i<j\leq m,j-i\geq m+1}{\measuredangle(l_{j},l_{i})}=\frac{m(m+1)}{2}\pi \] for $n=2m$ \[\sum_{1\leq i<j\leq 2m,}{\angle(l_{i},l_{j})}=\sum_{1\leq i<j\leq 2m,j-i\leq m-1}{\angle(l_{i},l_{j})}+\sum_{1\leq i<j\leq 2m,j-i\geq m+1}{\angle(l_{j},l_{i})}+\sum_{1\leq i\leq m,j=i+m}{\angle(l_{i},l_{j})}\le \sum_{1\leq i<j\leq 2m,j-i\leq m-1}{\measuredangle(l_{i},l_{j})}+\sum_{1\leq i<j\leq 2m,j-i\geq m+1}{\measuredangle(l_{j},l_{i})}+m\frac{\pi}{2}=\frac{m^{2}}{2}\pi \] I left the detailed(i.e.how to prove $\sum_{1<i<j\leq m,j-i\leq m}{\measuredangle(l_{i},l_{j})}+\sum_{1<i<j\leq m,j-i\geq m+1}{\measuredangle(l_{j},l_{i})}=\frac{m(m+1)}{2}\pi$ and the other one) to the reader.I am busy today......... I forgot to post that lines $l_{1},...l_{n}$ is in order.(My english is bad,I mean that there exist line $l$ such that $\measuredangle(l_{i},l)\leq \measuredangle(l_{i+1},l)$,for any i)
05.06.2022 13:28
Note translating a line does not effect its angle with some other line. Basically, all that matters is the direction of lines. Hence we may WLOG assume that all lines are concurrent at some point ($O$ say). Let $S$ be the set of those $n$ lines. Key Claim: The maximum sum is attained when two of the lines are perpendicular. Proof: Consider any random line $\ell \in S$ and $m$ be the line passing through $O$ and perpendicular to $\ell$ (which we assume is not currently in $S$). We WLOG assume all lines lie on the same side of $\ell$ (say all of them lie above $\ell$). Let $\ell_1,\ell_2,\ldots,\ell_{n-1}$ be the $n-1$ lines (other than $\ell$). Now other than $\ell$, there are lines on left and right side of $m$. WLOG, the left side has $\ge$ lines than right side. On the left side, let $\ell_i$ be the line next to $m$. Observe replacing $\ell_i$ by $m$ does not decrease the sum of angles, proving our Claim. $\square$ Now observe if two lines $a,b$ are perpendicular, then for any line $x$ we have $$ \angle (a,x) + \angle (b,x) = \frac{\pi}{2} $$So if $f(n)$ denotes the max sum in the question, then using our Claim we obtain the reccursion $$ f(n) = f(n-2) + (n-1) \cdot \frac{\pi}{2} ~~ \forall ~ n \ge 3$$Now it is easy to note that $f(1) = 0$ and $f(2) = \frac{\pi}{2}$. Hence, \begin{align*} f(2k+1) &= f(1) + \frac{\pi}{2} \left(2k + (2k-2) + \cdots + 2 \right) = \frac{\pi}{2} \cdot k(k+1) \\ f(2k+2) &= f(2) + \frac{\pi}{2} \left((2k+1) + (2k-1) + \cdots +3 \right) = \frac{\pi}{2} \left((2k+1) + (2k-1) + \cdots + 1 \right) = \frac{\pi}{2} \cdot (k+1)^2 \end{align*}This completes the proof. $\blacksquare$