# Prove that the shortest side of one triangle is the longest side of another, given 3 pairs of points.

I have received this question and am having great difficulties. I don't even know how to try to solve it.

It goes like this:

6 points are given in a room. These points are pairwise differently distant from each over. However no 3 points may lie on a straight line. Observe all triangles whose corners are the aforementioned points.

Now prove that there is always one triangle whose shortest side is the longest side of another triangle.

• You have a certain number of points, a certain number of sides, none of which are the same length, a certain number of triangles, a certain number of longest sides and a certain number of shortest sides. You will probably need the Pigeon Hole Principle: en.wikipedia.org/wiki/Pigeonhole_principle – John Wayland Bales Dec 10 '17 at 22:21

Maybe there's a more general combinatorial method to this interesting problem.

I was so scared by the length of your answer that concentrated all my mind power for an insight about such a method and after a few minutes found a solution. :-)

Consider a complete graph $K_6$ whose vertices are given points. Color its edges as follows. If a segment between the vertices is incident to the edge is the longest side of some triangle then color it red, otherwise color it blue. By a well-known fact, there exists a triangle $T$ with monochoromatic edges. If $T$ is blue then the edge between the endpoints of its longest side should be colored red, a contradiction. So $T$ is red and then its shortest side is a longest side of some triangle.

• +1 Thanks for your remarks. That's why I'm offering my reputation. – GNUSupporter 8964民主女神 地下教會 Feb 2 '18 at 2:16
• @GNUSupporter Thanks. I say a few words about my insight. As a usual insight, it was based on a (huge) experience on the relevant topics. First of all, the question sounds like a typical contest problem, with a simple formulation and an elegant solution. So I applied a usual contest brainstorm. The first and the simplest idea was to use Pigeon Hole Principle, but it failed, because we have $20$ distinct triangles and $15$ sides, but a priori some sides may be only the longest triangle sides and some sides may be only the shortest triangle sides. – Alex Ravsky Feb 2 '18 at 8:21
• Since we have a problem about six points and two kinds of segments between them, the next standard contest idea was to somehow attach to the problem the above Ramsey fact. For this it remained to define an edge coloring rule. Tthis led me to the solution. – Alex Ravsky Feb 2 '18 at 8:21
• Dear Alex, I just saw in your profile that "This account is closed." I just wanted to say that I learnt so much math from your answers here, and I am sure thousands of other people also did. You helped me personally with this question more than 5 years ago! I really really hope you come back :) – Prism Aug 6 '18 at 19:17

# Overview

I don't know how to use Pigeon Hole Principle: since it's possible that the shortest side of a triangle is also the shortest side of another one, so I am uncertain whether I can get enough sides for applying this principle.

I'll first start with some simple lemmas, then divide the proof into three stages.

# Setup

• "Save ink": if one side is the shortest side of some triangle, we say it's an (S) side (for a triangle). An (L) side (...) is similarly defined.
• Goal: Prove that at least one of these 6C2=15 sides is simultaneously an (L) side and an (S) side.
• "Form two teams": Partition these six points into two subsets of three points.
• "Icebreaking": In each subset, form a triangle by joining the points. These two triangles $\triangle_1,\triangle_2$ are called "funda $\triangle$"(mental $\triangle$). Their sides are called "funda sides". For each $i=1,2$,
• Funda sides: $L_i$ and $S_i$ are the (L) and (S) sides for $\triangle_i$ respectively.
• "Team members": $L_i\setminus S_i, L_i \cap S_i, S_i \setminus L_i$

# Heat-up

When we see a "triangle"/"star" of (S) sides, then we're done.

Lemma $\triangle$: A triangle formed by three (S) sides contains an (L) side.
Lemma $\star$: If three (S) sides share a common point, then the "goal" in the previous section is achieved.
Proof:

1. Cover the common point with your hand.
2. Form a triangle with dotted lines linking the other three vertices.
• One of the three dotted sides is an (S) side.
• Each of the dotted side is attached to (at least) two (S) sides.
3. Uncover the common point to observe the triangle formed in step (2). It's a "triangle" of (S) sides, so apply lemma $\triangle$ to conclude. $\square$

These two lemmas are the keys to end this game.

# Round 1: Attack

"Team 1 uses its strengh ($L_1$) to attack the weakness ($S_2$) of another team": Form a triangle with $L_1$ and a vertex of $S_2$ (either $S_2\setminus L_2$ or $L_2 \cap S_2$). To keep this game, assume that $L_1$ is never an (S) side. We try to "encircle" $S_2$ with two (S) sides in order to apply lemma $\triangle$. There are $2\times 2=4$ possible choices of the (S) sides for these two triangles.

## Case 1: Ideal case

Invoke lemma $\triangle$ and finish. For the upper part of the figure, we assign $\color{red}{L_1\cap S_1 L_2\cap S_2}$ to be the (S) side for $\triangle L_1 L_2\cap S_2$ and $\color{red}{L_1\cap S_1 S_2\setminus L_2}$ to be the (S) side for $\triangle L_1 S_2\setminus L_2$. The lower part is similar.

## Case 2: X & Case 3: =

For these two cases, move to next round. # Round 2: Counterattack

Team 2 now do the same to team 1. The ideal cases are omitted to save ink.

## Case 2: X

We focus on $\triangle L_2 S_1\cap L_1$. Either apply

• lemma $\star$ on $L_1\cap S_1$; or
• lemma $\triangle$ on $\triangle L_1\cap S_1 L_2$

## Case 3: =

We focus on $\triangle S_1 L_2\cap S_2$. • On the left half, $\color{red}{S_1\setminus L_1 L_2\cap S_2}$ is the (S) side for $\triangle S_1 L_2\cap S_2$. Apply lemma $\triangle$ to conclude.
• On the right half, it's the only case left: $\color{red}{L_1\cap S_1 L_2\cap S_2}$ is the common (S) side for $\triangle L_1 L_2\cap S_2$ and $\triangle L_1\cap S_1 L_2$.

# Round 3: Mobilise the commoners

When the situation gets stagnant, we have to get the "commoners" involved. Since it's team 1's turn, we introduce it's remaining funda side $L_1\setminus S_1 S_1\setminus L_1$. Since it wasn't there in rounds 1&2, we can identify one more (S) side for $\triangle L_1\setminus S_1 S_1\setminus L_1 L_2\cap S_2$.

• Any one of the two sides connecting $L_2\cap S_2$ is (S): apply lemma $\triangle$; or
• $\triangle L_1\setminus S_1 S_1\setminus L_1$ is (S): apply lemma $\star$ on $S_1\setminus L_1$.

Q.E.D.

COMMENT.- Let $P_1,P_2,\cdots P_6$ be the six points. Because of there are no three collinear points, each triple $(P_i,P_j,P_k)$ determines a triangle so there are $\dbinom 63=20$ distinct triangles. Besides, by hypothesis, there are $\dbinom62=15$ distinct sides and numbering points conveniently we can put for these fifteen sides $$\overline {P_1P_2}\lt\overline {P_1P_3}\lt\overline {P_1P_4}\lt\overline {P_1P_5}\lt\overline {P_1P_6}\lt\overline {P_2P_3}\lt\overline {P_2P_4}\lt\overline {P_2P_5}$$ $$\overline {P_2P_5}\lt\overline {P_2P_6}\lt\overline {P_3P_4}\lt\overline {P_3P_5}\lt\overline {P_3P_6}\lt\overline {P_4P_5}\lt\overline {P_4P_6}\lt\overline {P_5P_6}$$

Each side $\overline {P_iP_j}$ gives rise to four triangles $\triangle{P_iP_jP_k}$ for $k$ distinct of $i$ and $j$.

So there are fifteen sides of different length with which twenty triangles are formed.

What else? I believe the end is almost given so I invited young beginners to win the offered bounty. Go ahead!

• We assign $20$ triangles to $15$ shortest sides: apply the Pigeon-Hole Principle to conclude that there exists $i,j$ such that $\overline {P_iP_j}$ corresponds to two triangles. – GNUSupporter 8964民主女神 地下教會 Feb 3 '18 at 8:36
• OIC. Why there's no upvote for this answer? $\triangle P_1 P_2 P_3$ is the triangle so that each of its sides is a shortest side for another triangle. – GNUSupporter 8964民主女神 地下教會 Feb 3 '18 at 8:40
• If we can enumerate the given points in such a way that the long inequality holds then the comment above provides a solution. Unfortunately, such an enumeration does not always possible (because it needs five shortest sides incident to one vertex). Anyway, I expect that similar approaches lead to case consideration which is better to avoid. – Alex Ravsky Mar 17 '19 at 15:04
• @Alex Ravsky: Your solution is overwhelming and I like it very much even though it results from a well-known strong result. I just wanted to give a comment that might lead to an original solution and right now it occurs to me that I would try to apply a demonstration for the absurd. But I'm very busy with non-mathematical things for now. Greetings. – Piquito Mar 18 '19 at 20:19