A fun problem! (Problem 1)
Uh, Hi! This is my first blog post. I’m not sure where this impending train-wreck is headed; but as of now, it seems to be chugging along just fine – and perhaps that’s all that matters.
The current plan for this blog is that I want it to be a place where I record some interesting math I happen to chance upon from time to time. The blog is intended to serve as a repository of my thoughts, understanding and the math that I find exciting.
I am currently preparing to write my qualifying exams (in August) as I enter my PhD program, and so I plan to post fairly regularly as I progress through reviewing real and functional analysis, some group, Galois, field, ring and Module theory. I am also reading Eisenbud and the Rising sea at the moment to teach myself some Algebraic Geometry, so you might find me raving about that from time to time.
I also want to have a “A fun problem!” series going, where I post (hopefully maybe) on a weekly basis, some elementary (not so easy, but very fun) math problems that I come across either in Olympiad problem books, exams, or just the sea of questions in MSE.
But that’s enough yapping – here is the inaugural post of the problem series.
Problem
If $a_1, \dots, a_7$ are not necessarily distinct real numbers such that $1 < a_i < 13$ for all $i$, then show that we can choose three of them such that they are the lengths of a side of a triangle
Source: ISI B.Math entrance – subjective paper, 2011
Solution
At first glace this problem seems to have a lot of moving parts, and finding a particular triplet of numbers seems like a hassle (especially when they could really be anything!). So lets just assume the statement doesn’t hold, and hope to find a contradiction somewhere down the line.
So we are essentially saying, there are seven numbers $a_1, \dots, a_7$ each strictly between $1$ and $13$ such that no three of them form the sides of a triangle. Since we are talking about triangles, it only makes sense to invite our best friend, the triangle inequality, to the party. The triangle inequality says the following:
If $a_1, a_2, a_3$ make up the sides of a triangle, then they satisfy $$a_i + a_j \geq a_k \quad \text{ for } i, j, k \in {1,2,3}$$
Essentially, this says that the sum of the lengths of any two sides of a triangle is greater than or equal to the length of the third (remaining) side.
Now, since the $a_i$ are arbitrary, let us begin by introducing some structure to them. So without loss of generality, given the seven numbers, let us rearrange and rename them such that $1<a_1 \leq \dots \leq a_7 < 13$.
This might seem quite unnecessary now, but we still consider the following (trivial) inequalities (so that a certain very nice pattern becomes apparent later)
$$a_1 \geq 1 \cdot a_1 > 1$$
$$a_2 \geq 1 \cdot a_1 > 1$$
Now, for the fun bit. Through our assumption, we know no three triplets form the sides of a triangle, and in particular, we know that $a_1, a_2$ and $a_3$ do not form the sides of a triangle. So, they don’t satisfy the triangle inequality.
So
$$a_3 > a_1 + a_2 \geq a_1 + a_1 = 2a_1> 2$$
Similarly $a_2, a_3$ and $a_4$ do not form a triangle either. So,
$$a_4 > a_3 + a_2 \geq 2a_1 + a_1 = 3a_1 > 3$$
For good measure, lets do one more before we wave our hands up in the air and say that the pattern is obvious
$$a_5 > a_4 + a_3 \geq 3a_1 + 2a_1 = 5a_1 > 5$$
Now we wave our hands up in the air and say that the pattern is obvious1. In the very end we have
$$a_7 > a_6 + a_5 \geq 8a_1 + 5a_1 = 13a_1 > 13$$
But this is clearly a contradiction! (because we know $a_7 < 13$). So we win!
Generalization
The heart of the contradiction came from the fact that in the above set up, after rearranging in the given numbers in ascending order, it is forced that $a_7 > 13$ regardless of the choice of $a_i$. The way we got to $13$ is very reminiscent of (if not quite literally) the construction of the Fibonacci sequence. What is more, it is also just as important that $13$ is the $7^{th}$ Fibonacci number2.
With this little bit of insight we can almost immediately generalize the above statement as follows
Given $r, a_1, \dots, a_n$ real numbers such that $1< a_i < r \leq F_n$ (where, $F_n$ is the $n^{th}$ Fibonacci number) for all $i \in 1, \dots, n$ one can always choose a triplet $a_i, a_j$ and $a_k$ such that they form the sides of a triangle.
I leave filling in the little details and generalizations as a fairly easy exercise to the reader.