Find the maximal possible value of $n$ such that there exist points $P_1,P_2,P_3,\ldots,P_n$ in the plane and real numbers $r_1,r_2,\ldots,r_n$ such that the distance between any two different points $P_i$ and $P_j$ is $r_i+r_j$.
Problem
Source: Spanish Communities
Tags: combinatorics unsolved, combinatorics
20.04.2006 05:52
In a convex quadrilateral $ABCD$ you always have, up to relabeling, $AC+BD>AB+CD$: if the quadrilateral is non-degenerate take $AC,BD$ to be the diagonals, if three vertices are collinear, and the fourth is not on the same line take the three vertices to be $B,C,D$ in this order, and if all four points are collinear, take them to be $A,B,D,C$ in this order. For every $i,j,k,l$, notice that $P_iP_j+P_kP_l=P_iP_k+P_jP_l=P_iP_l+P_jP_k$. This, together with the above, implies that either we have some three collinear points, in which case these are all the points in our set ($n\le 3$), or no three points are colinear, and we don't have any convex quadrilaterals. By the Erdos-Szekeres Theorem, among any $5$ points in the plane, no three collinear, we can find the vertices of a convex quadrilateral. This means that $n\le 4$. Conversely, $n=4$ is possible to achieve: take $4$ mutually externally tangent circles centered at $P_1,P_2,P_3,P_4$, and take $r_i$ to be the radii of the circles.
28.09.2009 21:01
I assume that all the points are distinct, so $ n$ could be as large as we want. If $ r_a, r_b$ are nonpositive reals we get $ \overline{AB}\leq 0$ which is impossible since $ A\not = 0$. But $ \overline {CB}\leq\overline{CA} + \overline{AB} = r_c + r_a + r_a + r_b\Leftrightarrow 0\leq r_a$ whit equality iff all points lie on a straight line. So all points must be nonnegative. The case $ n = 5$ its impossible. Easily you can proof that no such formation lie on a straight line, okay. Simply supose that $ A$, $ B$, $ C$, $ D$, $ E$ are such points that contradict my afirmation, and $ D$ must be the Inner Soddy Point of $ \triangle ABC$. By the uniqueness of the Inner Soddy Point $ r_e$ can't be positive, but $ r_e = 0$ implies that all lie on a straight line, contradiction! Or $ E$ must be the Outer Soddy point. But the Outer Soddy circle and the Inner Soddy circle never are tangent to each other out of degenerate cases.* And we are done For $ n = 4$ the formation $ A$, $ B$, $ C$, Inner Soddy Point of $ \triangle ABC$ match. QED *(just check the tangential triangle of $ \triangle ABC$, none of circles touch te triangle, one of the circles are out an another are in)
18.10.2021 23:26
We claim the maximum to be $n=4$. To achieve this, Let $P_1, P_2, P_3$ be the vertices of an equilateral triangle of side length $2$, and let $P_4$ be its barycenter. Pick $r_1=r_2=r_3=1$, and it is easy to derive that $r_4=\frac{2\sqrt{3}}{3}-1$ meets the conditions of the problem. $\rightarrow$ First consider the case where all $r_i$ are nonzero . For every $i = 1, ..., n$, construct a circle $C_i$ centered at $P_i$ and with radius $|r_i|$. We notice then that the hypothesis holds true for two $P_i, P_j$ if and only if: 1. $C_i$, $C_j$ are externally tangent to each other, if $r_i, r_j >0$ 2. $C_i$ is internally tangent to $C_j$, if $r_j > 0 > r_j$ Notice that if $0 > r_i, r_j$ then $\overline{P_iP_j} \ge 0 > r_i+r_j$, contradiction. From this it follows that there is at most one $k$ such that $r_k$ is negative. If there is such an $r_k$, then by our obervation $C_k$ must be internally tangent to all other $C_i$. If we assume, by way of contradiction, that this case allows for $n>2$, then there are $i \not= j$ such that -$r_i, r_j >0$ thus $C_i, C_j$ are externally tangent to each other. -$C_k$ is internally tangent to both $C_i$, $C_j$ These two conditions cannot hold simultaneously, a contradiction. If there is not such an $r_k$, then we have $r_i >0$ for all $i$. Thus all $C_i$ are pairwise externally tangent to each other. It is clear from the initial construction that $n \ge 3$ is possible, so we consider only such $n$. Notice then, that if we want to add a $C_4$, there is only one way to do it: If we place $P_4$ outside of the triangle $\triangle P_1P_2P_3$, then $C_4$ can be tangent to at most 2 other $C_i$, so $P_4$ can only be placed inside of the triangle. By a continuity argument we can conclude that there is a unique way to do so, so we reach our maximum $n=4$. $\rightarrow$ Now consider the case where there exists $r_k = 0$ . It is clear that there is at most one nonpositive value, otherwise we'd have $\overline{P_kP_l} = r_k+r_l \le 0$ for some $k, l$, which is not possible for all distinct points. This means that all other $r_i > 0$, so: -$P_k$ lies on $C_i$ for all $i \not= k$ -$C_i, C_j$ are externally tangent to each other for all $i \not= j \not= k$ From this we can infer that all $C_i, C_j$ are externally tangent to each other at the point $P_k$ specifically. This can only happen for at most two circles, so in this case we have the bound $n \le 3$. $\square$