8
$\begingroup$

Let $S$ be a set of $n$ points in the plane, no $3$ collinear. Determine the maximum number of right-angled triangles with all three vertices as points in $S$.

This is a slightly more difficult and precise question than IMO 1970. For $n=3$, clearly the maximum is one. For $n=4$, we can have four triangles, etc. However, I don't know how to continue.

$\endgroup$
2
  • 1
    $\begingroup$ Could be of interest: oeis.org/A186926 (without the requirement of general position and with the additional requirement that the triangles are isoceles) $\endgroup$
    – joriki
    Commented Apr 11, 2016 at 14:39
  • $\begingroup$ After spending some time thinking about it (see my answers below), I would like to opine that this problem is considerably more difficult than the aforementioned question from IMO 1970 (namely, the main difficulty lies in the case of odd $n$). $\endgroup$
    – JimT
    Commented Sep 25, 2023 at 15:55

5 Answers 5

3
$\begingroup$

For 5 points the maximal number of right triangles is 7.

Seven triangles

In the following figure, $\phi$ is the golden ratio. Drop two and one of the extremal points to obtain 12 and 16 right triangles on 6 and 7 points. Partially based on the Kepler triangle.

Twenty triangles

For 8 points, 24 right triangles are possible with a regular octagon. Dropping a point yields only 15 triangles, so the above solution is better.

octagon

The regular decagon gives 40 right triangles.
The regular dodecagon gives 60 right triangles.

$\endgroup$
1
  • 1
    $\begingroup$ Beautiful diagrams. $(+1)$ $\endgroup$
    – Mr Pie
    Commented Jul 17, 2018 at 1:05
2
$\begingroup$

OK, for record's sake here's a solution.

The answer is $\frac{n(n-2)}{2}$ for even $n$ and $\frac{(n-1)(n-2)}{2}$ for odd $n$. The construction is to draw a circle, and pair up your points to be diametrically opposite (so when $n$ is odd, we have one lonely point not in a pair).

To show that we can't do better, for each point $P$, we count the number of triangles for which $P$ is the right angle. The key insight is that if $X,Y$ form a right angle at $P$, then this is the only right triangle at $P$ involving $X$ or $Y$. Otherwise, if (say) $\angle YPZ=90^{\circ}$, then $X$, $P$, $Z$ are collinear, contradiction. So there are at most $\lfloor\frac{n-1}{2}\rfloor$ triangles that their right angle at $P$.

Applying this to all $n$ choices of $P$ implies the result for even $n$. Some more fiddling is required when $n$ is odd.

$\endgroup$
1
  • $\begingroup$ Indeed, the reasoning works only for even $n$; for odd $n$ it is close but not exact. Also, as the examples for $n=5,7$ in one of the answers above show, the formula should be $(n−1)(n−2)/2+1$. So, yes, some extra tweaking is needed. $\endgroup$
    – JimT
    Commented Sep 1, 2023 at 15:17
1
$\begingroup$

Now, for an upper bound when $n$ is odd; $n = 2k+1$. We already have $n(n-1)/2$ but that is too far away from the presumed answer which is our lower bound $(n-1)(n-2)/2+1$---these two bounds differ by $n-2$.

Here is the proof of the ``better'' upper bound, which is two times closer (compared to $n(n-1)/2$) to our lower bound.

Consider arbitrary point $P_i$ from the given set $\mathcal P = \{P_1,\ldots,P_n\}$. Let $d_i$ be the maximum distance from it to all other points in $\mathcal P$, i.e., $$ d_i = \max_{X\in\mathcal P} |P_i X| . $$ For every point $P_j$ such that $P_iP_j = d_i$, connect points $P_i$ and $P_j$ with oriented edge $\vec{P_iP_j}$. After doing that for all points of $\mathcal P$, we obtain oriented graph $G$ with $n$ vertices and at least $n$ edges. Denote the number of the edges going into vertex $P_i$ by $x_i$---obviously, we have $\sum x_i = n$.

Now for any given point $P_j \in \mathcal P$ we want to bound from above the number of right-angled triangles $P_jP_aP_b$, in which $P_j$ is the right-angle vertex. If $G$ contains edge $\vec{P_iP_j}$, then vertex $P_i$ cannot be a vertex in right-angled triangle $P_jP_aP_b$ where $P_aP_b$ is a hypotenuse. Indeed, assume the opposite, and let $P_jP_iP_m$ be such a triangle. But then leg $P_jP_i$ must be shorter than hypotenuse $P_iP_m$, which is in contradiction with $P_j$ realizing the maximum distance from $P_i$ to the points of $\mathcal P$. Therefore, no more than $n-1-x_j = 2k-x_j$ points of $\mathcal P$ can serve as vertices of right-angled triangles with their right-angle at $P_j$. Hence, the number of such triangles does not exceed $$ \left[ \frac{2k - x_j}2 \right] = k - \left\lceil \frac {x_j}2 \right\rceil . $$ Thus, the total number of right-angled triangles cannot exceed $$ nk - \sum_{j=1}^n \left\lceil \frac {x_j}2 \right\rceil \leqslant nk - \left\lceil \frac n2 \right\rceil = nk - k - 1 = \frac{(n-1)(n-2)}2 + \frac {n-3}2 . $$

Therefore, we have an upper bound which is only $(n-5)/2$ ``worse'' than our lower bound. This is, of course, still not the complete solution for the case of odd $n$, but we are getting closer.

$\endgroup$
1
  • $\begingroup$ Another (simpler) way of proving the same upper bound for odd $n$ would be to count the number of right-angled triangles $PQR$ (with $Q$ being the right angle) by choosing point $P$ and then noticing that $Q$ must be selected among $n-2$ points (excluding the point realizing the maximum distance from $P$ to points of $\mathcal P$). Since every triangle is counted twice, we obtain the upper bound of $[n(n-2)/2]$. That number equals $(n(n-2)-1)/2$, which in turn is equal to the expression in the above post. $\endgroup$
    – JimT
    Commented Jan 26 at 17:29
0
$\begingroup$

The arguments below are mainly from observation without proofs. It may even not be the best case, but it follows logically from the case for $n=4$ by considering how to maximize the numbers of right triangles.

Start with the case for $n=4$ , clearly a square pattern gives us the most numbers of right triangle. Then, we want to maximize the number of right angled triangle formed by adding an extra point. Can we add 2? The answer is No. The only point that would give us more than $2$ extra triangles would be at the centre of the square, but that would violate the rule. You can try to find out the points which would give you an extra right angled triangle by drawing circle using any line segment between two points as the diameter. Any point lying on the circles would be a possible choice of the next point. Let's randomly choose one point $A$ from it, we will use it later. But for now, we know the maximum number of triangles formed by $5$ points would be $5$ since we can only add one triangle.

For case $n=6$, we try to find another point that would add some more right angled triangles to the shape. Now I claim that there is a point that can give you at least $2$ extra right angled triangles. (I cannot prove the existence/ non existence of a point that gives 3 extra triangles.) As shown it the diagram below, $B$ is a point that lies on two circles. (Excuse my bad drawings, I didn't have a compass in hand) Constructing $B$

So that would make the number of right angled triangles $7$.

Now we would like to add two points at once. Recall that we could construct a square from $4$ points, which would give us $4$ extra triangles. We can add points $C,D$ so that $A,B,C,D$ form a square, thus giving us $4$ extra triangles: C,D

So for $n=8$, we can at least have a configuration that gives us $11$ right angled triangles. I cannot say for sure that $C,D$ must not lie on any circle (thus giving more right angled triangles) but it looks pretty unlikely.

So following this construction, for the nineth point, unlike the fifth point, can be chosen to be on two circles: (excuse my terrible drawing, I hope you can at least see what's going on roughly)

constructing E

So $E$ would give us $2$ more triangles.

Im not going to draw this one but we can find the tenth point that could give us $2$ more triangles. And an eleventh and twelfth point that form a square with the previous two points. Up to $n=12$ , we can get to $15$.

So my deduction is that for $n=4k$, where $k>1$ is a positive integer. We could at least get $n+3$ points. I am expecting someone to find a better result than this.

$\endgroup$
5
  • $\begingroup$ hmm for $n=6$ there is a way to get $3$ more triangles. Take a square and its centre ($5$ points). There are $8$ triangles. Now reflect the centre in one of the sides: this gives $3$ more triangles. I think that the upper boud is extremely dependant on $n$: see my revised question. $\endgroup$
    – jlammy
    Commented Apr 11, 2016 at 14:04
  • $\begingroup$ @jlammy I dont see how that could give us 3 more triangle. Can you specify with which points can it link to form right angled triangles? Maybe I am a bit too tired to think. $\endgroup$
    – lEm
    Commented Apr 11, 2016 at 14:11
  • $\begingroup$ @jlammy I think you want to consider the case where no 3 points are collinear? $\endgroup$
    – lEm
    Commented Apr 11, 2016 at 14:13
  • $\begingroup$ oops sorry I was being silly. $\endgroup$
    – jlammy
    Commented Apr 11, 2016 at 14:15
  • $\begingroup$ @jlammy It's ok. I have considered some cases where it doesn't rely on forming squares but I don't think they would work. Also maybe there exists some kind of construction to get an extra three. As we construct more and more, it would be hard to tell if it is possible or not though. Maybe we would need help from a computer. $\endgroup$
    – lEm
    Commented Apr 11, 2016 at 14:18
0
$\begingroup$

Following beautiful example for $n = 7$ (by EdPegg) above I would like to confirm that for any odd $n$ there exists an example with $\frac{(n-1)(n-2)}{2} + 1$ right-angled triangles.

The idea is to place all points but one on unit circumference $S$, with one exceptional point $P_n$ positioned at $(1+\epsilon, 0)$. The examples follow the same main idea, although they differ slightly based on parity of number $k = (n-1)/2$. The idea is to generate points on $S$ in quadruples where each quadruple consists of two pairs of diametrically opposite points, with two diameters being symmetric with respect to the $Ox$ axis. First point $P_i$ in each subsequent quadruple is constructed as the leftmost intersection of $S$ and line $L_i$ which is defined as the line passing through $P_n$ and perpendicular to $P_{i-2}P$ (therefore ensuring that angle $P_{i-2}P_nP_i$ equals $90^\circ$). Let us call this operation a ``dagger''. The second point is constructed in the same manner (just with value of $i$ increased by one); the third and the fourth points are diametrically opposed to the first and the second points respectively.

In case of $n = 4m+1$ the very first quadruple is defined as follows: points $P_1$ and $P_2$ need to be symmetric with respect to $Ox$ and form the right angle with $P_n$. That is, $\angle P_1P_nP_2 = 90^\circ$. Again, we always consider the ``leftmost'' points only when looking at the intersections with $S$.

In case of $n = 4m+3$ we begin with $P_1 = (0,1)$, $P_2 = (0,-1)$ and then generate $P_3$ and $P_4$ by applying the dagger to $P_1$ and $P_2$ respectively. Then we go to diametrically opposed points, then aplly the dagger, and so on and so forth.

If $\epsilon$ is small enough, then it is easy to see that we can perform $m$ steps of this algorithm to construct our set. However, one more requirement has to be met, otherwise we would not be able to achieve the promised number of right triangles. We need the final diameters of the constructed sequence to form right triangles with point $P_n$. In other words, in the last quadruple either the first or the last two points must coincide with the points where tangents from $P_n$ to $S$ touch circumference $S$. It can be shown using continuity (or some other tools) that by slowly increasing the value of $\epsilon$ this condition can be met as well.

Then this set of points would give us exactly $\frac{(n-1)(n-2)}{2}+1$ right-angled triangles.

Below is the example for $n = 9$ with $29$ right triangles. $24$ of them are formed within the set of first eight points (all lying on $S$), three more (with the right angle vertex at $P_9$) are formed as the result of dagger operations, and two more are triangles formed by diameters $P_5P_7$, $P_6P_8$ and point $P_9$ (with $P_9$ not serving as the vertex of the right angle).

enter image description here

The required value of $\epsilon$ in this case is approximately $0.2064$. This number, in fact, can be described as follows. Consider the roots of polynomial $25x^4 - 54x^3 + 21x^2 + 4x + 4$. One of them equals $1$, two more are complex, and the remaining root $\beta$ lies somewhere between $1.3$ and $2$ (its approximate value is $1.455405613925$). Then $\epsilon = \sqrt{\beta}-1$.

In general case it can be shown that the required value of $\epsilon$ is a root of some polynomial equation of degree $2^{m+1}$.

Now with this example in hand all we need to finalize the solution is to come up with the proof that we cannot have more than $\frac{(n-1)(n-2)}{2}+1$ right-angled triangles when $n$ is odd. Perhaps it can be shown that all but one point must lie on the same circumference...

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .