In a city, there are some buildings. We say the building $A$ is dominant to the building $B$ if the line that connects upside of $A$ to upside of $B$ makes an angle more than $45^{\circ}$ with earth. We want to make a building in a given location. Suppose none of the buildings are dominant to each other. Prove that we can make the building with a height such that again, none of the buildings are dominant to each other. (Suppose the city as a horizontal plain and each building as a perpendicular line to the plain.)
Problem
Source:
Tags: analytic geometry, combinatorics proposed, combinatorics
29.09.2010 14:33
Denote by B the building we are going to build and $a$ be the $x$-coordinate of the given location. For any other building X, there is a range of allowed height for B so that X and B is not dominant to each other. Each range consists of an upper bound and a lower bound. If the highest lower bound is greater than the lowest upper bound, we can build B with the height in this range. Otherwise, there are two buildings, say $B_1$ and $B_2$, whose top coordinates are $(a_1,b_1)$ and $(a_2,b_2)$, so the range of allowed height for B is $[b_1-|a-a_1|,b_1+|a-a_1|]\cup[b_2-|a-a_2|,b_2+|a-a_2|]$, thus we assume that $b_1-|a-a_1|>b_2+|a-a_2|$. Therefore $b_1-b_2>|a-a_1|+|a-a_2|\ge|a-a_1+a_2-a|=|a_1-a_2|$. Therefore $B_1$ is dominant to $B_2$, a contradiction. Our proof is complete.
03.04.2022 09:33
WLOG we can assume buildings in Cartesian coordinate system. For building $A$ let $h_A$ be it's height and $d_A$ it's distance from $0$ in $x$-coordinat. Note that $45^{\circ}$ condition means for any $A,B$ we have $|h_B - h_A| \le |d_B - d_A|$. Let $h_P$ be least height between buildings and let $S$ be our new building in the given location. Let assume buildings $P,Q$ such that $S,P$ are not dominant to each other but $S,Q$ are, we will prove then $P,Q$ are dominant which will give contradiction. $h_S \le h_P + |d_S - d_P|$ Now that $S,Q$ are dominant we have $h_S$ is not in range ${(-|d_S-d_Q| + h_Q, |d_S-d_Q| + h_Q)}$ but then with triangle inequality we have $|h_P - h_Q| \ge |d_P -d_Q|$ which means $P,Q$ are dominant which gives contradiction.