1
$\begingroup$

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$.

  • 0
    You mean "a right angled triangle"? It seems too easy for an olympiad problem.2011-07-20
  • 0
    Uh... not that easy man. How about you give us an answer if it's so easy? =) (Not saying its impossible though.)2011-07-20
  • 0
    it is from 23rd moscow olympiad2011-07-20
  • 4
    @Patrick You are right, I was too fast, it's not as easy as I thought.2011-07-20
  • 0
    Can someone use combinatoric way to do this,since it is from a combinatoric book2011-07-20
  • 0
    @Victor: There is a branch of combinatorics (or if you wish, geometry) called *combinatorial geometry*. This problem could be considered a problem in combinatorial geometry. A "purely combinatorial" solution cannot be possible, because of the high geometric content.2011-07-20
  • 0
    @Andre-May you present a proof of combinatorial geometry please?2011-07-20
  • 0
    I don't see where combinatorics come in handy here. Sometimes it's just about geometry. That's my opinion though.2011-07-20

3 Answers 3

5

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$.

  • 1
    We basically shoot the same ideas, but your proof is more rigorous and mine more intuitive. +1 to yours.2011-07-20
  • 0
    i prefer combinatorics way,is it possible?2011-07-20
  • 0
    How the hell do you wanna use combinatorics to prove a problem about geometry? Do you have any suggestion or idea in mind? I don't see how this could be possible, enlighten me.2011-07-20
  • 1
    Nice. 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
3

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,

  • 0
    i prefer combinatorics way,is it possible?2011-07-20
1

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.