Triangle Inequality

Given a triangle $ABC$ and a point $M$ inside the triangle.

Let $\alpha = \angle BMC, \beta = \angle AMC, \gamma = \angle AMB$

Prove that:
$$\frac{AM}{BM.CM} + \frac{BM}{CM.AM} + \frac{CM}{AM.BM} \geq -2 \left( \frac{\cos \alpha}{AM} + \frac{\cos \beta}{BM} + \frac{\cos \gamma}{CM} \right)$$

Solution In Progress

Let
$a = \frac{AM}{\sin \alpha}, b = \frac{BM}{\sin \beta}, c = \frac{CM}{\sin \gamma}$

Because $M$ is in the interior of the triangle, then $0 < \alpha, \beta, \gamma < \pi$ and thus $0 < \sin \alpha, \sin \beta, \sin \gamma \leq 1$. Thus $a,b,c > 0$. Without loss of generality, we may assume that $a \geq b \geq c$.

So we have:
$AM = a \sin \alpha, BM = b \sin \beta, CM = c \sin \gamma$

Substitute it to our inequality, and use the following shorthand:

$C_\alpha = \cos \alpha \sin \beta \sin \gamma$
$C_\beta = \sin \alpha \cos \beta \sin \gamma$
$C_\gamma = \sin \alpha \sin \beta \cos \gamma$

So our inequality becomes
$$ \iff a^2\sin^2 \alpha + b^2 \sin^2 \beta + c^2 \sin^2 \gamma +2 ( bc C_\alpha + ac C_\beta + ab C_\gamma ) \geq 0$$

Note the following identities:
$$C_\beta + C_\gamma = \sin \alpha \cos \beta \sin \gamma + \sin \alpha \sin \beta \cos \gamma = \sin \alpha \sin (\beta + \gamma) = \sin \alpha \sin (2 \pi - (\beta + \gamma)) = - \sin^2 \alpha$$

Similarly,
$$C_\alpha + C_\gamma = - \sin^2 \beta$$
$$C_\alpha + C_\beta = - \sin^2 \gamma$$

So that
$$C_\alpha = (\sin^2 \alpha - \sin^2 \beta - \sin^2 \gamma)/2$$
$$C_\beta = (\sin^2 \beta - \sin^2 \alpha - \sin^2 \gamma)/2$$
$$C_\gamma = (\sin^2 \gamma - \sin^2 \beta - \sin^2 \alpha)/2$$

Substituting back to our inequalities, we have:
$$\iff (a-b)(a-c)\sin^2 \alpha + (b-a)(b-c) \sin^2 \beta + (c-a)(c-b) \sin^2 \gamma \geq 0$$

It's also equivalent to:
$$\iff (a-b)^2 C_\gamma + (a-c)^2 C_\beta + (b-c)^2 C_\alpha \leq 0$$

Cannot be all negative

Suppose $a_1,a_2,a_3,a_4$ and $b_1,b_2,b_3,b_4$ are eight real numbers. Prove that there is $i,j$ distinct indices such that $a_ia_j + b_ib_j \geq 0$.

Advanced version:
Suppose $a_i,b_i,c_i, 1 \leq i \leq 5$ are fifteen real numbers. Prove that there is $i,j$ distinct indices such that $a_ia_j + b_ib_j + c_ic_j \geq 0$.

General version:
Suppose $A_{i,j}, 1 \leq i \leq n, 1 \leq j \leq n+2$ is a matrix of $n \times (n+2)$ real numbers, prove that there are two columns $p,q$ such that their dot product is non-negative. That is:
$$\sum_{i=1}^{n} A_{i,p} A_{i,q} \geq 0$$

Also find an example of a $n \times (n+1)$ matrix where this property does not hold

A geometric interpretation of this problem is that, given $n+2$ vectors in $n$-dimensional space, two of them must form an angle of 90 degrees or less.

Sequence with prime number

Suppose $p$ is a prime number greater than 2, and $m$ is a natural number. Let $a_n$ be sequences defined by:
$a_1 = 1$
$a_2 = m$
$a_{n+2} = \frac{a_{n+1}^2 +p}{a_n}, n = 1,2,...$

Determine all values of $m$ such that $a_n$ is an integer for all $n$.

Largest k for arbitrary function

Find the largest number $k$ that satisfies the following property:

For every real-valued function $f$ defined over $[0,1]$, there exist $a,b,c \in [0,1]$ such that:
$$|f(ab) + f(bc) + f(ca) - abc | \geq k$$

Solution

First we show that $k = 1/6$ satisfies the condition of the problem.

For $k=1/6$, suppose to the contrary that for all $a,b,c$ chosen in the interval $[0,1]$ we have:
$$|f(ab) + f(bc) + f(ca) - abc | < \frac{1}{6}$$

Let $y = f(0),y=f(1)$.
Plugging in $a=b=c=0$ we have $|3x| < 1/6 \iff |x| < 1/18$
Plugging in $a=b=c=1$ we have $|3y-1| < 1/6$
Plugging in $a=b=1, c=0$ we have $2x+y| < 1/6$

That means $y = (2x+y) - 2x < 1/6 + 2/18 = 5/18$
But also $3y-1 > -1/6 \iff y > 5/18$, a contradiction.

Thus $k= \frac{1}{6}$ satisfies the condition of the problem.

Now we show that it is the largest such constant. We choose a function $f(x) = \frac{6x^\frac{3}{2} - 1}{18}$ and prove that
$$ -\frac{1}{6} \leq f(ab)+f(bc)+f(ca) - abc \leq \frac{1}{6}$$
for all $a,b,c \in [0,1]$

Indeed, the first inequality is equivalent to
$$(ab)^\frac{3}{2} + (bc)^\frac{3}{2} + (ca)^\frac{3}{2} \geq 3abc$$ which is true by AM-GM.

The second inequality is equivalent to
$$(ab)^\frac{3}{2} + (bc)^\frac{3}{2} + (ca)^\frac{3}{2} - 3abc \leq 1$$

Now consider the LHS, and try to find its maximum value over $a,b,c \in [0,1]$
First, we try a substitution $x = \sqrt{ab}, y = \sqrt{ac}, z = \sqrt{bc}, x,y,z \in [0,1]$ and WLOG, we may assume that $x \geq y \geq z$ (which corresponds to $a \geq b \geq c$)
So now our objective function becomes $x^3 + y^3 + z^3 - 3xyz$.

Let $g(x) = x^3 + y^3 + z^3 - 3xyz$, and fix $y,z$.
$$g(1) - g(x) = (1-x^3) - 3yx(1-x) = (1-x)(1 + x + x^2 - 3yz)$$
Because $x \leq 1$, then $1-x \geq 0$
$1+x+x^2-3yz \geq 1 + 2x^2-3yz = (1-yz) + 2(x^2 - yz) \geq 0$
So $g(1) \geq g(x)$.

So the maximum happens when the largest of 3 variables equals to 1. But this means that $ab = 1$ which implies $a=b=1$. Then $y = z = \sqrt{c}$. Our objective function now becomes:
$$x^3 + y^3 + z^3 - 3xyz = 2y^3 - 3y^2 +1$$
Let $h(y) = 2y^3 - 3y^2 + 1$, then $h(y) - h(0) = y^2(2y-3) < 0$ because $y \geq 1$. So the maximum happens when $y = 0$

In conclusion, our maximum happens when $x = 1, y=z=0$ and that's when $a=b=1, c= 0$. At this point, the maximum value is 1, thus proving our assertion.

Another way to determine the maximum value of the function above is by observing that it is a convex function on each of its variable, and all three variables are freely chosen from the interval $[0,1]$. Thus, the maximum must happen when all of its variables are zero or one. Plugging in all permutations of $(0,0,0), (0,0,1), (0,1,1), (1,1,1)$, we find that the maximum is indeed 1.

Solution: Passengers Boarding Airplane

Credit goes to Ed Kao, Vallent Lee and Laurence Tai for helping with the second solution.

Original problem: http://dharmath.blogspot.com/2009/10/passengers-boarding-airplane.html

2009 passengers are waiting in a line to board an airplane with 2009 seats. Each passenger has a boarding pass that has his/her seat number on it. The first passenger, however, was oblivious and chose a random seat to sit on.

For each subsequent passenger, he/she will try to sit on his/her assigned seat first. If that seat is taken by someone else, he/she will choose a random empty seat to sit on.

What is the probability that the last passenger would sit on his assigned seat?

Answer: $\frac{1}{2}$

First Solution

We generalize the problem to $n$ passengers boarding an airplane with $n$ seats.

The probability that the first passenger sits in his seat is $1/n$. We will prove by induction that the probability that the $k$-th ($k > 1$) passenger sits in his seat is $\frac{n-k+1}{n-k+2}$

For $k=2$, it's obvious that the second passenger has probability $\frac{n-1}{n}$ of finding his seat unoccupied. As long as the first passenger chooses something other than his seat, he will find his seat unoccupied and sits there correctly.

For $k>2$, consider the time when $k$-th passenger is about to board. If he finds his seat unoccupied, he will sit there. The only way that he does NOT sit on his correct seat is if it's already occupied by a previous passenger. We will divide this into two cases, depending on who sits at his seat.

Case 1: Passenger $k-1$ sits there. The only way this could happen is if passenger $k-1$ finds her seat occupied by someone else, and then she chooses to sit at passenger $k$'s seat. The probability of passenger $k-1$ finds her seat occupied by someone else is $1-\frac{n-(k-1)+1}{n-(k-1)+2} = \frac{1}{n-k+3}$.
At that point, there are $k-2$ occupied seats total and there are $n-k+2$ empty seats on the plane. The probability that she chooses to sit at this particular seat is $\frac{1}{n-k+2}$

Case 2: Passenger $i (i < k-1)$ sits there (at passenger $k$'s seat). Now we consider the moment where passenger $i$ was about to board. Passenger $k$'s seat was open.

If passenger $k-1$'s seat had been occupied by someone else before $i$, then passenger $i$'s seat would have been open, and passenger $i$ must have sit there correctly.

In order for passenger $i$ to NOT sit on his seat, both passenger $k$ and $k-1$'s seat are both open. That means, the probability that passenger $i$ sits at passenger $k$'s seat is the same as the probability that passenger $i$ sits at passenger $k-1$'s seat, since both choices are equally likely and they're always made with both choices available.

Thus the probability from case 2 is $\frac{1}{n-k+3}$

The total probability that passenger $k$ does not sit at his correct seat is:
$$\frac{1}{n-k+3} \frac{1}{n-k+2} + \frac{1}{n-k+3} = \frac{1}{n-k+2}$$
so the probability that he sits at his seat is:
$$1 - \frac{1}{n-k+2} = \frac{n-k+1}{n-k+2}$$
which completes the inductive step.

From this formula, it's clear that the probability passenger $n$ sits on his correct seat is $\frac{1}{2}$

Second Solution
We make the following observations:

1. In the beginning, both seat #1 and #2009 are both empty.
2. The moment someone chooses to sit on either seat (that is, the moment they stop being both empty), there is no more choices to be made for the rest of the boarding process. The rest of the passengers must thus sit deterministically from that point on.

Indeed, when passenger $k$ sits on seat #2009, then seat $k+1, ..., 2008$ would be empty and the subsequent passengers don't have to choose at all. Passenger #2009 has a random "choice" of 1 seat.
If passenger $k$ sits on seat #1, then the remaining vacant seats match the unboarded passengers perfectly and everyone can sit in their correct seat save for those who've already boarded.

That means, for every event that someone illegitimately sits on seat #2009, that passenger had an equally likely choice of seat #1, and vice versa. The moment this symmetry is broken, there would be no more choices to be made for the rest of the boarding process.

3. When passenger #2009 is about to board, there is only one empty seat. That empty seat is either seat #1 or seat #2009. If there is another seat $k ( 1 < k < 2009)$ empty, then one might ask: why didn't passenger $k$ sit there? A contradiction.

From the observations above, we define two events:
A: an event that passenger #2009 sits at seat #1
B: an event that passenger #2009 sits at seat #2009

These two events are mutually exclusive, and are the only two possibilities. Furthermore, they have equal probability since the moment one event becomes impossible, there is no more choices to be made by the rest of the passengers.

So the probability that passenger #2009 sits at his correct seat is $\frac{1}{2}$

Triangle Inequality

In a triangle $ABC$, let $a = BC, b = AC, c = AB$. For any point $M$ and real numbers $x,y,z$, show that

$(x+y+z)(xMA^2 + yMB^2 + zMC^2) \geq xyc^2 + xzb^2 + yza^2$

Solution
We shall show that the inequality above is equivalent to
$$(x \vec{MA} + y \vec{MB} + z \vec{MC})^2 \geq 0$$

Indeed, since:
$$2\vec{MA} \vec{MB} = MA^2 + MB^2 - c^2$$
so
$$2xy\vec{MA} \vec{MB} = xyMA^2 + xyMB^2 - xyc^2$$
$$2yz\vec{MB} \vec{MC} = yzMB^2 + yzMC^2 - yza^2$$
$$2zx\vec{MC} \vec{MA} = zxMC^2 + zxMA^2 - zxb^2$$

Adding them, we obtain:
$$RHS = \sum x(y+z)MA^2 - 2\sum xy \vec{MA} \vec{MB}$$

So
$$LHS - RHS = \sum x^2MA^2 + \sum x(y+z)MA^2 - RHS = \sum x^2 MA^2 + 2\sum xy \vec{MA} \vec{MB}$$
$$= (x \vec{MA} + y \vec{MB} + z \vec{MC})^2 \geq 0 $$

Combined Sequence

Let $A,B$ be two distinct positive integers greater than 1, and define the sequences:

$a_m = m + \frac{Bm}{A}, m = 1,2,3,\cdots, A-1$
$b_m = m + \frac{Am}{B}, m = 1,2,3,\cdots, B-1$

And combine those two sequence to form a new sequence $c_1,c_2,\cdots, c_{A+B-2}$ with $c_1 \leq c_2 \leq \cdots \leq c_{A+B-2}$.

Prove that the difference between any two consecutive $c_i$s are less than 2.

Solution

It suffices to prove that for each $a_k$, we can find another $a_i$ or $b_j$ that lies between $a_k$ and $a_k+2$, and vice versa, for each $b_l$, we can find another $a_i$ or $b_j$ that lies between $b_l$ and $b_l + 2$.
Without loss of generality, we may assume that $A > B$.
The distance between two consecutive $b_j$s are $b_{j+1} - b_j = 1 + B/A < 2$, so for each $b_l$, we're guaranteed that $b_l < b_{l+1} < b_l+2$.

Now we're left to consider $a_k$.
Fix $k$, and now take the smallest $l$ such that $b_l > a_k$. This is always possible because:
\[a_k \leq a_{B-1} = (B-1)(1+A/B) < (A-1)(1+B/A) = b_{A-1}\]
(the middle inequality is true because $A > B$.)

If $l$ is the smallest such $l$, that means
\[b_{l-1} \leq a_k \iff (l-1)(1+B/A) \leq k(1+A/B) \iff l/A - k/B \leq 1/A\]

So
\[b_l - a_k = l(1+B/A) - k(1+A/B) = (A+B)(l/A - k/B) \leq (A+B)/A < 2\]
which completes the proof

3 arbitrary functions

Suppose $f,g,h$ are functions that are defined in the closed interval $0 \leq x \leq 1$. Show that we can always find $a,b,c \in [0,1]$ such that:

$$|f(a)+g(b)+h(c) - (1-a)(1-b)(1-c)| \geq \frac{1}{3}$$

Also show that the constant $\frac{1}{3}$ cannot be replaced by a larger constant.

Finite Prime Set

Let $P$ be a finite set of primes. Define $m(P)$ as the largest number of consecutive integers each of which is divisible by a prime in $P$.
Let $|P|$ denote the size of $P$ and $\min(P)$ to be the smallest element in $P$.

Prove that:
1. $m(P) \geq |P|$
2. $m(P) = |P|$ if and only if $\min (P) > |P|$

Solution

Let $s = |P|$. We proceed by constructing $s$ consecutive integers which are each divisible by a prime in $P$. Indeed, the following system has a solution, according to Chinese Remainder Theorem:
$x+1 \equiv 0 \pmod {p_1}$
$x+2 \equiv 0 \pmod {p_2}$
...
$x+s \equiv 0 \pmod {p_s}$

Second part:
Suppose we have $s < \min(P)$ and that we have $s+1$ consecutive integers all divisible by some $p_i$: $x, x+1, x+2, ... , x+s$. Let $p_1 = \min(P)$.

For each $p_i$, it can only divide at most one of the above-mentioned integers. For if it divides $x+a$ and $x+b$ then it also divides $|a-b| \leq s < p_1$, a contradiction (since $p_1$ is the smallest prime in $P$).
So $m(P) \leq s$. But it's been shown that $m(P) \geq s$, so $m(P) = s$.

Now suppose we have $s \geq \min(P)$. We will show $s+1$ consecutive integers such that each is divisible by a prime in $P$, which then establishes $m(P) > s$.
Let $k = \min(P)$.
Again, we set up a system of equations as described above, but we choose the ordering of $p_i$s such that $p_k = k$. The rest can be arbitrary ordering. This is always possible if $s \geq k$.
According to CRT, there is a solution of $s$ consecutive integers that satisfy the above system of equations. But then we also have $x = x+k - k$ divisible by $p_k = k$. So together with $x$, they form $s+1$ consecutive integers.

Chess Board Coloring

Each cell in an infinite chess board is colored with one of the $n$ available colors. Prove that we can always find a rectangle such that all four corners have the same color.

Advanced version: Suppose not all cells are colored, but only some of them. Furthermore, for any circle with radius R, we can always find a colored cell in that circle. Prove that we can still find a monochromatic rectangle.

Solution: Cyclic quadrilateral

Original Problem: http://dharmath.blogspot.com/2010/05/cyclic-quadrilateral.html

First Solution

Let $AB=AD=x, BC=y$ and $CD=x+z$ with $y < z$.

Let $\theta = \angle ADC$ so $\angle ABC = 180^o-\theta$. It's easy to see that because $CD > BC$ then $\angle ABC > \angle ADC$ thus $0 < \theta < 90^o$

Now $AC^2 = x^2 + y^2 + 2xy \cos \theta = x^2 + (x+z)^2 - 2x(x+z)\cos \theta$, simplify it to get:
$\cos \theta = \frac{(x+z)^2-y^2}{2x(x+y+z)} = \frac{x+z-y}{x}$

But since $\theta$ is an acute angle, $\theta < 60^o \iff \cos \theta > 1/2$
So we need to show
$x+z-y > x$ which is true because $z > y$

Second Solution



Let $R$ be a point on $CD$ such that $CB = CR$ (see the picture).

Since $AB=AD$, then $CA$ is an internal angle bisector, and thus $\triangle ABC$ are congruent to $\triangle ARC$. That means $RD = CD - CR = CD - CB > AB = AD$.
Also, $AD = AB = AR$.
So $\triangle ARD$ is an isosceles where $AD = AR$ and $RD > AD$, which means that $\angle ADR < 60^o$ and thus $\angle ABC > 120^o$

Cyclic quadrilateral

In a cyclic quadrilateral $ABCD$ such that $AB = AD$ and $AB+BC < CD$, show that $ABC > 120^o$

Solution: http://dharmath.blogspot.com/2010/05/solution-cyclic-quadrilateral.html