There are $n$ ($n\ge 3$) given points in the plane such that any three of them form a right angled triangle.Find the largest possible $n$.
A olympiad problem about combinatorics and geometry
-
0I don't see where combinatorics come in hand$y$ here. Sometimes it's just about geometry. That's my opinion though. – 2011-07-20
3 Answers
Clearly, you can arrange 4 points in such a way, namely in a rectangle. I claim that 4 is the highest possible.
Among your $n$ points, let $A$ and $B$ be two points with the smallest distance between them. That means that in any triangle with vertices $A$ and $B$, the angle opposite the side $\overline{AB}$ will always be the smallest. Thus, in any triangle $ABC$, the right angle must be at the vertex $A$ or at the vertex $B$. Since no three points can be on a line, there is at most one point $C_1$ with the property that $ABC_1$ has a right angle at $A$, and similarly there is at most one point $C_2$ such that $ABC_2$ has a right angle at $B$.
-
1Nice. Alternative: Use the largest distance. Then all other points are on the circle with diameter AB, and there can be no more than one on each side. – 2011-07-20
How about this. Let $n$ be the maximum number of points you can place on the plane having this property. Therefore you can obtain a particular solution of this by letting three points on the plane at first, and then adding the next points to reach n points. This is because if the set has $n$ points, then any arbitrary subset of $n-1$ points out of this set has also the property that any three points from it form a right angle, so we can "build" the set of $n$ points out of the one with $n-1$ (inductive argument).
Place three points on the plane that form a right angle. Say they are placed so that $\{a,b,c\}$ has a right angle at $b$. If I am trying to place $d$ on the plane, $ad$ must be perpendicular to $ab$ and $cd$ must be perpendicular to $bc$, which leaves the possibility that $\{a,b,c,d\}$ form a rectangle.
Let's try to place a fifth point on the plane. We already know that a set of four points who satisfy this property, call it $\{a,b,c,d\}$, MUST form a rectangle. Suppose we had a fifth point possibly placed on the plane, call it $e$, so that we now have $\{a,b,c,d,e\}$ satisfying this property. Consider two sets of four points out of this set, say $\{a,b,c,d\}$ and $\{a,b,c,e\}$. They both form a rectangle because they satisfy your property, but they have three vertices in common, so that $d = e$, contradicting the fact that the set contains $5$ distinct points. Since any set with $n$ points and $n \ge 5$ would contain a set with $5$ points with this property, $n \ge 5$ also leads to a contradiction, thus the maximum is $n = 4$.
Hope that helps,
-
0i prefer combinatorics way,is it possible? – 2011-07-20
A combinatorial proof can be given by using the Fubini Principle. Please refer to "principles and techniques in combinatorics" by Chen chuang-chong and khee-meng.pp 68
Anyway, it is almost the same as counting the maximum number of points that can be placed on an integer lattice such that no three are collinear and the answer is logically 4.
Anurag.