Math Challenge - December 2021

[Not anonymous]

Sorry, please ignore my previous post (post #90). I think I found a mistake in that solution for question #31. I will attempt to find a correct solution later and make a new post.

 

[fresh_42]

Sorry, please ignore my previous post (post #90). I think I found a mistake in that solution for question #31. I will attempt to find a correct solution later and make a new post.

You do not need an algorithm or any iteration. Consider pairs $(g,P)$ of a straight line in the plane and a point $P\not\in g.$ Then choose a pair such that $\operatorname{dist}(g,P)$ is minimal.

 

[Not anonymous]

You do not need an algorithm or any iteration. Consider pairs $(g,P)$ of a straight line in the plane and a point $P\not\in g.$ Then choose a pair such that $\operatorname{dist}(g,P)$ is minimal.

I didn't expect a reply to my withdrawn incorrect solution. ** thanks for that hint. Below is a solution, hopefully correct this time.

Spoiler: Question 31

Let $\mathcal{L} = \{l_1, l_2, ..., l_m\}$ be the set of all lines that pass through 2 or more points belonging to $\mathcal{P} = \{P_1, P_2, ..., P_n\}$. Suppose $A \in \mathcal{P}, l_i \in \mathcal{L}$ be a point and a line such that $\mathtt{dist}(A, l_i) = \min \limits_{P_j \in \mathcal{P}} \min \limits_{l_k \in \mathcal{P}, P_{j} \notin_{l_k}} \mathtt{dist}(P_j, l_k)$. Such a pair will always exist if not all points of $\mathcal{P}$ are collinear. Without loss of generality, we will assume $l_i = l_1$ for convenience hereafter. By definition, $l_1$ will contain at least two points from $\mathcal{P}$. We will prove that $l_1$ cannot contain more than 2 points from $\mathcal{P}$, thus making it a line passing through exactly 2 points from $\mathcal{P}$.

Let $B, C$ be the two closest points to $A$ among all points from $\mathcal{P}$ lying on $l_1$. With reference to attached figure, $h_{A[BC]} \equiv \mathtt{dist}(A, l_1)$, using the notation $h_{X[YZ]}$ to denote the height of vertex $X$ w.r.t. the base $\bar {YZ}$ in triangle $\Delta {XYZ}$. Note that $BC$ must be the longest edge of $\Delta ABC$ (more precisely, no smaller than the other edges), since otherwise, we could have, for e.g., $h_{B[AC]} \lt h_{A[BC]}$, i.e. distance between $B$ and line passing through $A,C$ is smaller than $\mathtt{dist}(A, l_1)$, a contradiction. Therefore, $\angle{ABC}, \angle{ACB}$ must be acute angles as shown in the figure.

Now suppose there exists yet another point $D \in \mathcal{P}$ that lies on $l_1$. Without loss of generality, we can assume that it lies to the right of point $C$. Let $l_2 \in \mathcal{L}$ denote the line passing through $A, D$. From the figure, we see that $\mathtt{dist}(C, l_2) = h_{C[AD]}$. Using the area computation formulae for triangle $\Delta {AQ_{1}D}$, it follows that $h_{A[BC]} \times \mathtt{len}(Q_{1}D) = h_{C[AD]} \times \mathtt{len}(AD)$. Since $\mathtt{len}(AD) \gt \mathtt{len}(Q_{1}D)$ (as $AD$ is the hypotenuse of $\Delta {AQ_{1}D}$), it follows that $h_{C[AD]} \lt h_{A[BC]}$, i.e. $\mathtt{dist}(C, l_2) < \mathtt{dist}(A, l_1)$. But this contradicts the initial assumption that $\mathtt{dist}(A, l_1)$ is the minimum possible distance between any point in $\mathcal{P}$ and any line in $\mathcal{L}$. Since the contradiction arises only when we assume that there exists a point $D$ as defined above, it must be the case that such as point cannot exist. Hence, $l_1$ must contain only two points from $\mathcal{P}$.

 

[Not anonymous]

Once again I found a mistake in my solution. This time in one of equalities used in the proof. Posting the correction here.

Spoiler: Question 31 - correction to previous post

To show that $h_C[AD] < h_{A[BC]}$ if a point $D$ exists as described in my previous post, I must have used an inequality since I was comparing two different triangles.

The area of $\Delta AQ_{1}D$ is $\dfrac{1}{2} \times h_{A[BC]} \times \mathtt{len}(Q_1D)$. The area of $\Delta ACD$ is $\dfrac{1}{2} \times h_{C[AD]} \times \mathtt{len}(AD)$. From the figure, it can be seen that the area of $\Delta AQ_{1}D$ must be larger than that of $\Delta ACD$. Hence we get:
$$
\dfrac{1}{2} \times h_{A[BC]} \times \mathtt{len}(Q_1D) > \dfrac{1}{2} \times h_{C[AD]} \times \mathtt{len}(AD) \Rightarrow h_{A[BC]} > \dfrac{\mathtt{len}(AD)}{\mathtt{len}(Q_1D)} \times h_{C[AD]}
$$

Since $\mathtt{len}(AD) > \mathtt{len}(Q_1D)$ (as $AD$ is the hypotenuse of $\Delta AQ_1D$), it follows that $h_{A[BC]} > h_{C[AD]}$, i.e. $\mathtt{dist}(A, l_1) > \mathtt{dist}(C, l_2)$, but this contradicts the initial assumption about the minimality of $\mathtt{dist}(A, l_1)$.

The rest of the solution is the same as in the previous post.