Prove that the fraction $\frac{21n+4}{14n+3}$ is irreducible for every natural number $n$.

Denoting the greatest common divisor of $a, b$ as $(a,b)$, we use the Euclidean algorithm:

Their greatest common divisor is 1, so $\frac{21n+4}{14n+3}$ is irreducible.  Q.E.D.

Proof by contradiction:
Assume that $\dfrac{14n+3}{21n+4}$ is a reducible fraction where $p$ is the greatest common factor of $14n+3$ and $21n + 4$. Thus,
Subtracting the second equation from the first equation we get $1\equiv 0\pmod{p}$ which is clearly absurd.
Hence $\frac{21n+4}{14n+3}$ is irreducible.  Q.E.D.

Proof by contradiction:
Assume that $\dfrac{14n+3}{21n+4}$ is a reducible fraction.
If a certain fraction $\dfrac{a}{b}$ is reducible, then the fraction $\dfrac{2a}{3b}$ is reducible, too.
In this case, $\dfrac{2a}{3b} = \dfrac{42n+8}{42n+9}$.
This fraction consists of two consecutives numbers, which never share any factor. So in this case, $\dfrac{2a}{3b}$ is irreducible, which is absurd.
Hence $\frac{21n+4}{14n+3}$ is irreducible.  Q.E.D.

We notice that:
So it follows that $7n+1$ and $14n+3$ must be coprime for every natural number $n$ for the fraction to be irreducible. Now the problem simplifies to proving $\frac{7n+1}{14n+3}$ irreducible. We re-write this fraction as:
Since the denominator $2(7n+1) + 1$ differs from a multiple of the numerator $7n+1$ by 1, the numerator and the denominator must be relatively prime natural numbers. Hence it follows that $\frac{21n+4}{14n+3}$ is irreducible.
Q.E.D

By Bezout's Lemma, $3 \cdot (14n+3) - 2 \cdot (21n + 4) = 1$, so the GCD of the numerator and denominator is $1$ and the fraction is irreducible.

To understand why its irreducible, let's take a closer look at the fraction itself. If we were to separate both fractions, we end up with $\frac{21n}{14n}$ + $\frac{4}{3}$.
Simplifying the fraction, we end up with.    $\frac{3}{2}$. Now combining these fractions with addition as shown before in the problem, we end up with $\frac{17}{6}$. It's important to note that 17 is 1 off from being divisible by 6, and you'll see why later down this explanation. Now we expirement with some numbers. Plugging 1 in gives us
$\frac{25}{17}$. Notice how both numbers are one off from being divisible by 8(25 is next to 24, 17 is next to 16).
Trying 2, we end up with $\frac{46}{31}$. Again, both results are 1 off from being multiples of 15.
Trying 3, we end up with $\frac{67}{45}$. Again, both end up 1 away from being multiples of 22. This is where the realization comes in that two scenarios keep reoccurring:
1. Both Numerator and Denominator keep ending up 1 value away from being multiples of the same number, but
2. One always ends up being a prime number. Knowing that prime numbers only factors are 1 and itself, the fraction ends up being a paradoxical expression where one prime number is always being produced, and even with larger values, like say 15, implementing it in gives us $\frac{319}{199}$, we keep ending up with results that at the end will only have a common divisor of 1.

Let $\gcd (21n+4,14n+3)=a.$ So for some co-prime positive integers $x,y$ we have   Multiplying $(1)$ by $2$ and $(2)$ by $3$ and then subtracting $(1)$ from $(2)$ we get   We must have $a=1$, since $a$ is an positive integer. Thus, $\gcd(21n+4,14n+3)=1$ which means the fraction is irreducible, as needed.


Determine all three-digit numbers $N$ having the property that $N$ is divisible by 11, and $\dfrac{N}{11}$ is equal to the sum of the squares of the digits of $N$.

Let $N = 100a + 10b+c$ for some digits $a,b,$ and $c$. Then  for some $m$. We also have $m=a^2+b^2+c^2$. Substituting this into the first equation and simplification, we get  For an integer divisible by $11$, the the sum of digits in the odd positions minus the sum of digits in the even positions is divisible by $11$. Thus we get: $b = a + c$ or $b = a + c - 11$.
Case $1$: Let $b=a+c$. We get   Since the right side is even, the left side must also be even. Let $c=2q$ for some $q = 0,1,2,3,4$. Then
Substitute $q=0,1,2,3,4$ into the last equation and then solve for $a$.
When $q=0$, we get $a=5$. Thus $c=0$ and $b=5$. We get that $N=550$ which works.
When $q=1$, we get that $a$ is not an integer. There is no $N$ for this case.
When $q=2$, we get that $a$ is not an integer. There is no $N$ for this case.
When $q=3$, we get that $a$ is not an integer. There is no $N$ for this case.
When $q=4$, we get that $a$ is not an integer. There is no $N$ for this case.
Case $2$: Let $b = a + c - 11$. We get
Now we test all $c=0\rightarrow10$. When $c=0,1,2,4,5,6,7,8,9$, we get no integer solution to $a$. Thus, for these values of $c$, there is no valid $N$. However, when $c=3$, we get    We get that $a=8$ is a valid solution. For this case, we get $a=8,b=0,c=3$, so $N=803$, and this is a valid value. Thus, the answers are $\boxed{N=550,803}$.

Define a ten to be all ten positive integers which begin with a fixed tens digit.
We can make a systematic approach to this:
By inspection, $\dfrac{N}{11}$ must be between 10 and 90 inclusive. That gives us 8 tens to check, and 90 as well.
For a given ten, the sum of the squares of the digits of $N$ increases faster than $\dfrac{N}{11}$, so we can have at most one number in every ten that works.
We check the first ten:
$11*11=121$
$1^2+2^2+1^2=4$
$12*11=132$
$1^2+3^2+2^2=14$
11 is too small and 12 is too large, so all numbers below 11 will be too small and all numbers above 12 will be too large, so no numbers in the first ten work.
We try the second ten:
$21*11=231$
$2^2+3^2+1^2=14$
$22*11=242$
$2^2+4^2+2^2=24$
Therefore, no numbers in the second ten work.
We continue, to find out that 50 and 73 are the only ones that works.
$N=50*11=550$, $N=73*11=803$ so there are two $N$ that works.

Note that there are only 900 three-digit numbers. Of these, only 81 are divisible by 11. This brings to mind the great strategy of listing and bashing. Being organized while listing will get you the answer. There is plenty of time on the IMO, and listing is highly unlikely to miss cases. We end up getting $\boxed{N=550,803}$.


(Hungary)
Solve the system of equations:
where $a$ and $b$ are constants.  Give the conditions that $a$ and $b$ must satisfy so that $x, y, z$ (the solutions of the system) are distinct positive numbers.

Solution:
Note that $x^2 + y^2 = (x+y)^2 - 2xy = (x+y)^2 - 2z^2$, so the first two equations become
We note that $(x+y)^2 - z^2 = \Big[ (x+y)+z \Big]\Big[ (x+y)-z\Big]$, so if $a$ equals 0, then $b$ must also equal 0.  We then have $x+y = -z$; $xy = (x+y)^2$.  This gives us $x^2 + xy + y^2 = 0$.  Mutiplying both sides by $(x-y)$, we have $x^3 - y^3 = 0$.  Since we want $x,y$ to be real, this implies $x = y$.  But $x^2 + x^2 + x^2$ can only equal 0 when $x=0$ (which, in this case, implies $y,z = 0$).  Hence there are no positive solutions when $a = 0$.
When $a \neq 0$, we divide $(**)$ by $(*)$ to obtain the system of equations
which clearly has solution $x+y = \frac{a^2 + b^2}{2a}$, $z = \frac{a^2 - b^2}{2a}$.  In order for these both to be positive, we must have positive $a$ and $a^2 > b^2$.  Now, we have $x+y = \frac{a^2 + b^2}{2a}$; $xy = \left(\frac{a^2 - b^2}{2a}\right)^2$, so $x,y$ are the roots of the quadratic $m^2 - \frac{a^2 + b^2}{2a}m + \left(\frac{a^2 - b^2}{2a}\right)^2$.  The discriminant for this equation is
If the expressions $(3a^2 - b^2), (3b^2 - a^2)$ were simultaneously negative, then their sum, $2(a^2 + b^2)$, would also be negative, which cannot be.  Therefore our quadratic's discriminant is positive when $3a^2 > b^2$ and $3b^2 > a^2$.  But we have already replaced the first inequality with the sharper bound $a^2 > b^2$.  It is clear that both roots of the quadratic must be positive if the discriminant is positive (we can see this either from $\left(\frac{a^2 + b^2}{2a}\right)^2 > \left(\frac{a^2 + b^2}{2a}\right)^2 - \left(2\frac{a^2 -b^2}{2a}\right)^2$ or from  Descartes' Rule of Signs).  We have now found the solutions to the system, and determined that it has positive solutions if and only if $a$ is positive and $3b^2 > a^2 > b^2$.  Q.E.D.


Find the smallest natural number $n$ which has the following properties:
(a) Its decimal representation has 6 as the last digit.
(b) If the last digit 6 is erased and placed in front of the remaining digits, the resulting number is four times as large as the original number $n$.

As the new number starts with a $6$ and the old number is $1/4$ of the new number, the old number must start with a $1$.
As the new number now starts with $61$, the old number must start with $\lfloor 61/4\rfloor = 15$.
We continue in this way until the process terminates with the new number $615\,384$ and the old number $n=\boxed{153\,846}$.


Find all real roots of the equation
where $p$ is a real parameter.

Solution:
Assuming $x \geq 0$, square the equation, obtaining
.
If we have $p + 4 \geq 4x^2$, we can square again, obtaining
We must have $4 - 2p > 0 \iff p < 2$, so we have
However, this is only a solution when
so we have $p\geq 0$ and $p \leq \frac {4}{3}$
and $x = \frac {4 - p}{2\sqrt {4 - 2p}}$


(a) Find all positive integers $n$ for which $2^n-1$ is divisible by $7$.
(b) Prove that there is no positive integer $n$ for which $2^n+1$ is divisible by $7$.

We claim $2^n$ is equivalent to $2, 4,$ and $1$ $\pmod{7}$ for $n$ congruent to $1$, $2$, and $0$ $\pmod{3}$, respectively.
(a) From the statement above, only $n$ divisible by $3$ will work.
(b) Again from the statement above, $2^n$ can never be congruent to $-1$ $\pmod{7}$, so there are no solutions for $n$.

This solution is clearer and easier to understand.
(1) Since we know that $2^n-1$ is congruent to 0 (mod 7), we know that $2^n$ is congruent to 8 mod 7, which means $2^n$ is congruent to 1 mod 7.
Experimenting with the residue of $2^n$ mod 7:
$n$=1: 2
$n$=2: 4
$n$=3: 1 (this is because when $2^n$ is doubled to $2*2^n$, the residue doubles too, but $4*2=8$ is congruent to 1 (mod 7).
$n$=4: 2
$n$=5: 4
$n$=6: 1
Through induction, we easily show that this is true since the residue doubles every time you double $2^n$.
So, the residue of $2^n$ mod 7 cycles in 2, 4, 1. Therefore, $n$ must be a multiple of 3. Proved.
(2) According to part (1), the residue of $2^n$ cycles in 2, 4, 1.
If $2^n+1$ is congruent to 0 mod 7, then $2^n$ must be congruent to 6 mod 7, but this is not possible due to how $2^n$ mod 7 cycles. Therefore, there is no solution. Proved.
~hastapasta


Determine all values $x$ in the interval $0\leq x\leq 2\pi$ which satisfy the inequality

Solution:
We shall deal with the left side of the inequality first ($2\cos x \leq \left| \sqrt{1+\sin 2x} - \sqrt{1-\sin 2x } \right|$) and the right side after that.
It is clear that the left inequality is true when $\cos x$ is non-positive, and that is when $x$ is in the interval $[\pi/2, 3\pi/2]$. We shall now consider when $\cos x$ is positive. We can square the given inequality, and the resulting inequality will be true whenever the original left inequality is true. $4\cos^2{x}\leq 1+\sin 2x+1-\sin 2x-2\sqrt{1-\sin^2 2x}=2-2\sqrt{\cos^2{2x}}$. This inequality is equivalent to $2\cos^2 x\leq 1-\left| \cos 2x\right|$. I shall now divide this problem into cases.
Case 1: $\cos 2x$ is non-negative. This means that $x$ is in one of the intervals $[0,\pi/4]$ or $[7\pi/4, 2\pi]$. We must find all $x$ in these two intervals such that $2\cos^2 x\leq 1-\cos 2x$. This inequality is equivalent to $2\cos^2 x\leq 2\sin^2 x$, which is only true when $x=\pi/4$ or $7\pi/4$.
Case 2: $\cos 2x$ is negative. This means that $x$ is in one of the interavals $(\pi/4, \pi/2)$ or $(3\pi/2, 7\pi/4)$. We must find all $x$ in these two intervals such that $2\cos^2 x\leq 1+\cos 2x$, which is equivalent to $2\cos^2 x\leq 2\cos^2 x$, which is true for all $x$ in these intervals.
Therefore the left inequality is true when $x$ is in the union of the intervals $[\pi/4, \pi/2)$, $(3\pi/2, 7\pi/4]$, and $[\pi/2, 3\pi/2]$, which is the interval $[\pi/4, 7\pi/4]$. We shall now deal with the right inequality.
As above, we can square it and have it be true whenever the original right inequality is true, so we do that. $2-2\sqrt{\cos^2{2x}}\leq 2$, which is always true. Therefore the original right inequality is always satisfied, and all $x$ such that the original inequality is satisfied are in the interval $[\pi/4, 7\pi/4]$.


Prove that there is one and only one triangle whose side lengths are consecutive integers, and one of whose angles is twice as large as another.

In triangle $ABC$, let $BC=a$, $AC=b$, $AB=c$, $\angle ABC=\alpha$, and $\angle BAC=2\alpha$. Using the Law of Sines gives that

Therefore $\cos{\alpha}=\frac{a}{2b}$. Using the Law of Cosines gives that

This can be simplified to $a^2c=b(a^2+c^2-b^2)$. Since $a$, $b$, and $c$ are positive integers, $b|a^2c$. Note that if $b$ is between $a$ and $c$, then $b$ is relatively prime to $a$ and $c$, and $b$ cannot possibly divide $a^2c$. Therefore $b$ is either the least of the three consecutive integers or the greatest.
Assume that $b$ is the least of the three consecutive integers. Then either $b|b+2$ or $b|(b+2)^2$, depending on if $a=b+2$ or $c=b+2$. If $b|b+2$, then $b$ is 1 or 2. $b$ couldn't be 1, for if it was then the triangle would be degenerate. If $b$ is 2, then $b(a^2+c^2-b^2)=42=a^2c$, but $a$ and $c$ must be 3 and 4 in some order, which means that this triangle doesn't exist. therefore $b$ cannot divide $b+2$, and so $b$ must divide $(b+2)^2$. If $b|(b+2)^2$ then $b|(b+2)^2-b^2-4b=4$, so $b$ is 1, 2, or 4. Clearly $b$ cannot be 1 or 2, so $b$ must be 4. Therefore $b(a^2+c^2-b^2)=180=a^2c$. This shows that $a=6$ and $c=5$, and the triangle has sides that measure 4, 5, and 6.
Now assume that $b$ is the greatest of the three consecutive integers. Then either $b|b-2$ or $b|(b-2)^2$, depending on if $a=b-2$ or $c=b-2$. $b|b-2$ is absurd, so $b|(b-2)^2$, and $b|(b-2)^2-b^2+4b=4$. Therefore $b$ is 1, 2, or 4. However, all of these cases are either degenerate or have been previously ruled out, so $b$ cannot be the greatest of the three consecutive integers.
This shows that there is exactly one triangle with this property - and it has side lengths of 4, 5, and 6. $\blacksquare$

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

[Incomplete, please edit]
In a given triangle $ABC$, let $A=2B$, $\implies C=180-3B$, and $\sin C=\sin 3B$.
Then
Hence, $(*)$ $a^2 = b(b+c)$ (with assumptions. This needs clearing up)
If $b$ is the shortest side, $(b+2)^2 = b^2 +b(b+1)$
$\implies (b-4)(b+1)=0$,
$\implies b=4, c=5, a=6$,
No other permutation of $a$, $b$ and $c$ in terms of size gives integral values to $(*)$ [show]. So there is only one such triangle.

NO TRIGONOMETRY!!!
Let $a, b, c$ be the side lengths of a triangle in which $\angle C = 2\angle B.$
Extend $AC$ to $D$ such that $CD = BC = a.$ Then $\angle CDB = \frac{\angle ACB}{2} = \angle ABC$, so $ABC$ and $ADB$ are similar by AA Similarity. Hence, $c^2 = b(a+b)$. Then proceed as in Solution 2, as only algebraic manipulations are left.


Prove that there are infinitely many natural numbers $a$ with the following property: the number $z = n^4 + a$ is not prime for any natural number $n$.

Solution:
Suppose that $a = 4k^4$ for some $a$. We will prove that $a$ satisfies the property outlined above.
The polynomial $n^4 + 4k^4$ can be factored as follows:

Both factors are positive, because if the left one is negative, then the right one would also negative, which is clearly false.
It is also simple to prove that $n^2 + 2k^2 - 2nk > 1$ when $k > 1$. Thus, for all $k > 2$, $4k^4$ is a valid value of $a$, completing the proof. $\square$
~mathboy100
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Let $M$ be a point on the side $AB$ of $\triangle ABC$.  Let $r_1, r_2$, and $r$ be the inscribed circles of triangles $AMC, BMC$, and $ABC$.  Let $q_1, q_2$, and $q$ be the radii of the exscribed circles of the same triangles that lie in the angle $ACB$.  Prove that

Solution:
We use the conventional triangle notations.
Let $I$ be the incenter of $ABC$, and let $I_{c}$ be its excenter to side $c$.  We observe that
and likewise,
Simplifying the quotient of these expressions, we obtain the result
Thus we wish to prove that
But this follows from the fact that the angles $AMC$ and $CBM$ are supplementary.

By similar triangles and the fact that both centers lie on the angle bisector of $\angle{C}$, we have $\frac{r}{q} = \frac{s-c}{s} = \frac{a + b - c}{a + b + c}$, where $s$ is the semi-perimeter of $ABC$. Let $ABC$ have sides $a, b, c$, and let $AM = c_1, MB = c_2, MC = d$. After simple computations, we see that the condition, whose equivalent form is

is also equivalent to Stewart's Theorem

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Prove that the following assertion is true for $n=3$ and $n=5$, and that it is false for every other natural number $n>2:$
If $a_1, a_2,\cdots, a_n$ are arbitrary real numbers, then $(a_1-a_2)(a_1-a_3)\cdots (a_1-a_n)+(a_2-a_1)(a_2-a_3)\cdots (a_2-a_n)+\cdots+(a_n-a_1)(a_n-a_2)\cdots (a_n-a_{n-1})\ge 0.$

Solution:
Take $a_1 < 0$, and the remaining $a_i = 0$. Then $E_n = a_1(n-1) < 0$ for $n$ even,
so the proposition is false for even $n$.
Suppose $n \ge 7$ and odd. Take any $c > a > b$, and let $a_1 = a$, $a_2 = a_3 = a_4= b$,
and $a_5 = a_6 = ... = a_n = c$.
Then $E_n = (a - b)^3 (a - c)^{n-4} < 0$.
So the proposition is false for odd $n \ge 7$.
Assume $a_1 \ge a_2 \ge a_3$.
Then in $E_3$ the sum of the first two terms is non-negative, because $a_1 - a_3 \ge a_2 - a3$.
The last term is also non-negative.
Hence $E_3 \ge 0$, and the proposition is true for $n = 3$.
It remains to prove $S_5$.
Suppose $a_1 \ge a_2 \ge a_3 \ge a_4 \ge a_5$.
Then the sum of the first two terms in $E_5$ is
$(a_1 - a_2){(a_1 - a_3)(a_1 - a_4)(a_1 - a_5) - (a_2 - a_3)(a_2 - a_4)(a_2 - a_5)} \ge 0$.
The third term is non-negative (the first two factors are non-positive and the last two non-negative).
The sum of the last two terms is:
$(a_4 - a_5){(a_1 - a_5)(a_2 - a_5)(a_3 - a_5) - (a_1 - a_4)(a_2 - a_4)(a_3 - a_4)} \ge 0$.
Hence $E_5 \ge 0$.
This solution was posted and copyrighted by e.lopes. The original thread can be fond here: [1]


Prove that from a set of ten distinct two-digit numbers (in the decimal system), it is possible to select two disjoint subsets whose members have the same sum.

Solution: There are $2^{10}-2=1022$ distinct subsets of our set of 10 two-digit numbers. The sum of the elements of any subset of our set of 10 two-digit numbers must be between $10$ and $90+91+92+93+94+95+96+97+98+99 < 10 \cdot 100 = 1000$. (There are fewer attainable sums.) As $1000 < 1022$, the Pigeonhole Principle implies there are two distinct subsets whose members have the same sum. Let these sets be $A$ and $B$. Now, let $A' = A - (A \cap B)$ and $B' = B - (A \cap B)$. Notice $A'$ and $B'$ are disjoint. They are also nonempty because if $A = A \cap B$ or $B = A \cap B$, then one of $A$ and $B$ is a subset of the other, so they are either not distinct or have different sums. Therefore $A'$ and $B'$ are disjoint subsets our set of 10 distinct two-digit numbers, which proves the claim. $\square$


Point $O$ lies on line $g;$ $\overrightarrow{OP_1}, \overrightarrow{OP_2},\cdots, \overrightarrow{OP_n}$ are unit vectors such that points $P_1, P_2, \cdots, P_n$ all lie in a plane containing $g$ and on one side of $g.$ Prove that if $n$ is odd,  Here $\left|\overrightarrow{OM}\right|$ denotes the length of vector $\overrightarrow{OM}.$

Solution:
We prove it by induction on the number $2n+1$ of vectors. The base step (when we have one vector) is clear, and for the induction step we use the hypothesis for the $2n-1$ vectors obtained by disregarding the outermost two vectors. We thus get a vector with norm $\ge 1$ betwen two with norm $1$. The sum of the two vectors of norm $1$ makes an angle of $\le\frac\pi 2$ with the vector of norm $\ge 1$, so their sum has norm $\ge 1$, and we're done.
The above solution was posted and copyrighted by grobber. The original thread for this problem can be found here: [1]
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Three players $A, B$ and $C$ play the following game: On each of three cards an integer is written. These three numbers $p, q, r$ satisfy $0 < p < q < r$. The three cards are shuffled and one is dealt to each player. Each then receives the number of counters indicated by the card he holds. Then the cards are shuffled again; the counters remain with the players.
This process (shuffling, dealing, giving out counters) takes place for at least two rounds. After the last round, $A$ has 20 counters in all, $B$ has 10 and $C$ has 9. At the last round $B$ received $r$ counters. Who received $q$ counters on the first round?

Solution:
Answer: player $C$.
Let $n$ be the number of rounds played, then obviously $n (p + q + r) = 20 + 10 + 9 = 39$. So $n$ must be a divisor of 39, i. e. $n \in \{ 1, 3, 13, 39 \}$. But $p \geq 1,$ $q \geq p + 1 \geq 2,$ $r \geq q + 1 \geq 3,$ so $p + q + r \geq 1 + 2 + 3 = 6$ and $n = \frac{39}{p + q + r} \leq \frac{39}{6} < 7$. Also, by condition $n \geq 2,$ so we conclude to $n = 3$ and $p + q + r = \frac{39}{n} = 13$.
As $B$ received 10 counters including $r$ counters at the last round, $10 \geq p + p + r \geq 2 + r,$ so $r \leq 8$. On the other hand, from number of counters received by $A$ we get $r > \frac{20}{3} > 6$. So $r \in \{ 7, 8 \}$.
If $r = 7,$ from number of counters received by $B$ we get $3 = 10 - r \in \{ 2p, p + q, 2q \},$ and since 3 is odd, we get $p + q = 3$. But then $p + q + r = 3 + 7 = 10 \neq 13$ - a contradiction.
So $r = 8$ and $2 = 10 - r \in \{ 2p, p + q, 2q \}$. On the other hand, $2 \leq 2p < p + q < 2q,$ so $2 = 2p,$ $p = 1$ and $q = 13 - p - r = 4$. It is easy to check that the only way to distribute the counters for players is $20 = r + r + q,$ $10 = p + p + r$ and $9 = q + q + p,$ so player $C$ received $q$ counters on the first round.


Let $x_i, y_i$ $(i=1,2,\cdots,n)$ be real numbers such that  Prove that, if $z_1, z_2,\cdots, z_n$ is any permutation of $y_1, y_2, \cdots, y_n,$ then

Solution:
We can expand and simplify the inequality a bit, and using the fact that $z$ is a permutation of $y$, we can cancel some terms.

Consider the pairing $x_1 \rightarrow y_1$, $x_2 \rightarrow y_2$, ... $x_n \rightarrow y_n$. By switching around some of the $y$ values, we have obtained the pairing $x_1 \rightarrow z_1$, $x_2 \rightarrow z_2$, ... $x_n \rightarrow z_n$. Suppose that we switch around two $y$-values, $y_m$ and $y_n$, such that $y_m > y_n$. If $x_m > x_n$, call this a type 1 move. Otherwise, call this a type 2 move.
Type 2 moves only increase the sum of the products of the pairs. The sum is increased by $x_n \cdot y_m + x_m \cdot y_n - x_m \cdot y_m - x_n \cdot y_n$. This is equivalent to $(x_n - x_m)(y_m - y_n)$, which is clearly nonnegative since $y_m > y_n$ and $x_n > x_m$.
We will now consider switching from the $x$-$z$ pairing back to the $x$-$y$ pairing. We will prove that from any pairing of $x$ and $z$ values, you can use just type 2 moves to navigate back to the pairing of $x$ and $y$ values, which will complete the proof.
Suppose that $x_a$ is the biggest $x$-value that is not paired with its $y$-value in the $x$ and $z$ pairing. Then, switch this $y$-value with the $y$-value currently paired with $x_a$. This is obviously a type 2 move. Continue this process until you reach back to the $x$-$y$ pairing. All moves are type 2 moves, so the proof is complete.
~mathboy100

We can rewrite the summation as

Since $\sum^n_{i=1} y_i^2 = \sum^n_{i=1} z_i^2$, the above inequality is equivalent to

We will now prove that the left-hand side of the inequality is the greatest sum reached out of all possible values of $\sum^n_{i=1}x_iz_i$. Obviously, if $x_1 = x_2 = \ldots = x_n$ or $y_1 = y_2 = \ldots = y_n$, the inequality is true. Now, assume, for contradiction, that neither of those conditions are true and that there exists some order of $z_i$s that are not ordered in the form $z_1 \ge z_2 \ge \ldots \ge z_n$ such that $\sum^n_{i=1}x_iz_i$ is at a maximum out of all possible permutations and is greater than the sum $\sum^n_{i=1}x_iy_i$. This necessarily means that in the sum $\sum^n_{i=1}x_iz_i$ there exists two terms $x_pz_m$ and $x_qz_n$ such that $x_p > x_q$ and $z_m < z_n$. Notice that

which means if we make the terms $x_pz_n$ and $x_qz_m$ instead of the original $x_pz_m$ and $x_qz_n$, we can achieve a higher sum. However, this is impossible, since we assumed we had the highest sum. Thus, the inequality

is proved, which is equivalent to what we wanted to prove.

~Imajinary


In a convex quadrilateral (in the plane) with the area of $32 \text{ cm}^{2}$ the sum of two opposite sides and a diagonal is $16 \text{ cm}$. Determine all the possible values that the other diagonal can have.

Solution:
Label the vertices $A$, $B$, $C$, and $D$ in such a way that $AB + BD + DC = 16$, and $\overline{BD}$ is a diagonal.
The area of the quadrilateral can be expressed as $BD \cdot ( d_1 + d_2 ) / 2$, where $d_1$ and $d_2$ are altitudes from points $A$ and $C$ onto $\overline{BD}$. Clearly, $d_1 \leq AB$ and $d_2 \leq DC$. Hence the area is at most $BD \cdot ( AB + DC ) / 2 = BD(16-BD) / 2$.
The quadratic function $f(x)=x(16-x)/2$ has its maximum for $x=8$, and its value is $f(8)=32$.
The area of our quadrilateral is $32$. This means that we must have $BD=8$. Also, equality must hold in both $d_1 \leq AB$ and $d_2 \leq DC$. Hence both $\overline{AB}$ and $\overline{DC}$ must be perpendicular to $\overline{BD}$. And in any such case it is clear from the Pythagorean theorem that $AC = 8\sqrt 2$.
Therefore the other diagonal has only one possible length: $8\sqrt 2$.


In the interior of a square $ABCD$ we construct the equilateral triangles $ABK, BCL, CDM, DAN.$ Prove that the midpoints of the four segments $KL, LM, MN, NK$ and the midpoints of the eight segments $AK, BK, BL, CL, CM, DM, DN, AN$ are the 12 vertices of a regular dodecagon.

Solution:
Just use complex numbers, with $a = 1$, $b = i$, $c = - 1$ and $d = - i$.
With some calculations, we have $k = \frac {\sqrt {3} - 1}{2}( - 1 - i)$, $l = \frac {\sqrt {3} - 1}{2}(1 - i)$, $m = \frac {\sqrt {3} - 1}{2}(1 + i)$ and $n = \frac {\sqrt {3} - 1}{2}( - 1 + i)$.
Now it's an easy job to calculate the twelve midpoints and to find out they are all of the form $\frac {\sqrt {3} - 1}{2}e^{\frac {k\pi}{6}i}$, with $k\in\mathbb{N}: 0\le k\le 11$, and the result follows.
The above solution was posted and copyrighted by Joao Pedro Santos. The original thread for this problem can be found here: [1]


Let $m$ and $n$ be positive integers such that $1 \le m < n$. In their decimal representations, the last three digits of $1978^m$ are equal, respectively, to the last three digits of $1978^n$. Find $m$ and $n$ such that $m + n$ has its least value.

Solution:
We have $1978^m\equiv 1978^n\pmod {1000}$, or $978^m-978^n=1000k$ for some positive integer $k$ (if it is not positive just do $978^n-978^m=-1000k$). Hence $978^n\mid 1000k$. So dividing through by $978^n$ we get $978^{m-n}-1=\frac{1000k}{978^n}$. Observe that $2\nmid LHS$, so $2\nmid RHS$. So since $2|| 978^n$, clearly the minimum possible value of $n$ is $3$ (and then $489^n\mid k$). We will show later that if $n$ is minimal then $m$ is minimal. We have $978^{m-3}-1\equiv 0\pmod {125}\Leftrightarrow 103^{m-3}\equiv 1\pmod {125}$. Hence, $m-3\mid \varphi(125)\Rightarrow m-3\mid 100$. Checking by hand we find that only $m-3=100$ works (this also shows that minimality of $m$ depends on $n$, as claimed above). So $m=103$. Consequently, $m+n=106$ with $\boxed{(m,n)=(103,3)}$.
The above solution was posted and copyrighted by cobbler and Andreas. The original thread for this problem can be found here: [1] and [2]


If $p$ and $q$ are natural numbers so thatprove that $p$ is divisible with $1979$.

Solution:
We first write
Now, observe that
and similarly $\frac{1}{661}+\frac{1}{1318}=\frac{1979}{661\cdot 1318}$ and $\frac{1}{662}+\frac{1}{1317}=\frac{1979}{662\cdot 1317}$, and so on. We see that the original equation becomes
where $s=660\cdot 661\cdots 1319$ and $r=\frac{s}{660\cdot 1319}+\frac{s}{661\cdot 1318}+\cdots+\frac{s}{989\cdot 990}$ are two integers. Finally consider $p=1979\cdot\frac{qr}{s}$, and observe that $s\nmid 1979$ because $1979$ is a prime, it follows that $\frac{qr}{s}\in\mathbb{Z}$. Hence we deduce that $p$ is divisible with $1979$.
The above solution was posted and copyrighted by Solumilkyu. The original thread for this problem can be found here: [1]


$P$ is a point inside a given triangle $ABC$.  $D, E, F$ are the feet of the perpendiculars from $P$ to the lines $BC, CA, AB$, respectively.  Find all $P$ for which
is least.

Solution:
We note that $BC \cdot PD + CA \cdot PE + AB \cdot PF$ is twice the triangle's area, i.e., constant.  By the Cauchy-Schwarz Inequality,
with equality exactly when $PD = PE = PF$, which occurs when $P$ is the triangle's incenter, Q.E.D.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


The function $f(n)$ is defined on the positive integers and takes non-negative integer values. $f(2)=0,f(3)>0,f(9999)=3333$ and for all $m,n:$Determine $f(1982)$.

Clearly $f(1) \ge 1 \Rightarrow f(m+1) \ge f(m)+f(1) \ge f(m)+1$ so $f(9999) \ge 9999$.Contradiction!So $f(1)=0$.This forces $f(3)=1$.Hence $f(3k+3) \ge f(3k)+f(3)>f(3k)$ so the inequality $f(3)<f(6)<\cdots<f(9999)=3333$ forces $f(3k)=k \forall k \le 3333$.Now $f(3k+2) \ge k+1 \Rightarrow f(6k+4) \ge 2k+2 \Rightarrow f(12k+8) \ge 4k+4 \le f(12k+9)=4k+3$(Note:This is valid for $12k+9 \le 9999$ or $3k+2 \le 2499$).Contradiction!Hence the non-decreasing nature of $f$ gives $f(3k+1)=k$.Hence $f(n)=\lfloor\frac{n}{3}\rfloor \forall 1\le n \le 2499$.
So $f(1982)=\lfloor\frac{1982}{3}\rfloor=660$.
This solution was posted and copyrighted by sayantanchakraborty. The original thread for this problem can be found here: [1]

First observe that
Since $f(3)$ is a positive integer, we need $f(3)=1$. Next, observe that
\begin{align*}
3333=f(9999)\geq 5f(1980)+33f(3)=5f(1980)+33\quad\Longrightarrow\quad f(1980)\leq 660
\end{align*}On the other hand, $f(1980)\geq 660f(3)=660$, so combine the two inequalities we obtain $f(1980)=660$. Finally, write
Suppose that $f(1982)=661$, then
\begin{align*}
3333=f(9999)\geq 5f(1982)+29f(3)=3305+29=3334
\end{align*}a contradiction. Hence we conclude that $f(1982)=660$.
This solution was posted and copyrighted by Solumilkyu. The original thread for this problem can be found here: [2]

We show that $f(n) = [n/3]$ for $n <= 9999$, where [ ] denotes the integral part. We show first that $f(3) = 1$. $f(1)$ must be $0$, otherwise $f(2) - f(1) - f(1)$ would be negative. Hence $f(3) = f(2) + f(1) + 0$ or $1$ = $0$ or $1$. But we are told $f(3) > 0$, so $f(3) = 1$. It follows by induction that $f(3n) >= n$. For $f(3n+3) = f(3) + f(3n)$ + $0$ or $1 = f(3n) + 1$ or $2$. Moreover if we ever get $f(3n) > n$, then the same argument shows that $f(3m) > m$ for all $m > n$. But $f(3.3333) = 3333$, so $f(3n) = n$ for all $n <= 3333$. Now $f(3n+1) = f(3n) + f(1) + 0$ or $1$ = $n$ or $n + 1$. But $3n+1 = f(9n+3) >= f(6n+2) + f(3n+1) >= 3f(3n+1)$, so $f(3n+1) < n+1$. Hence $f(3n+1) = n.$ Similarly, $4f(3n+2) = n$. In particular $f(1982) = 660$.
This solution was posted and copyrighted by Tega. The original thread for this problem can be found here: [3]

Similar to solution 3.
Proof:
Lemma 1: $f(mn)\geq nf(m)$
Let, $P(m,m)$ be assertion.
Similarly,we can induct to get $f(nm)\geq nf(m)$.
Lemma proved.
Then we see that,
Then,
Then we can easily get,by assertion $P(1980,2)$
Hence, $\boxed{f(1980)=660,661}$.And, we are done. $\blacksquare$
This solution was posted and copyrighted by IMO2019. The original thread for this problem can be found here: [4]


Find all functions $f$ defined on the set of positive reals which take positive real values and satisfy the conditions:
(i)   $f(xf(y))=yf(x)$ for all $x,y$;
(ii)  $f(x)\to0$ as $x\to \infty$.

Let $x=y=1$ and we have $f(f(1))=f(1)$.  Now, let $x=1,y=f(1)$ and we have $f(f(f(1)))=f(1)f(1)\Rightarrow f(1)=[f(1)]^2$ since $f(1)>0$ we have $f(1)=1$.
Plug in $y=x$ and we have $f(xf(x))=xf(x)$.  If $a=1$ is the only solution to $f(a)=a$ then we have $xf(x)=1\Rightarrow f(x)=\frac{1}{x}$.  We prove that this is the only function by showing that there does not exist any other $a$:
Suppose there did exist such an $a\ne1$.  Then, letting $y=a$ in the functional equation yields $f(xa)=af(x)$.  Then, letting $x=\frac{1}{a}$ yields $f(\frac{1}{a})=\frac{1}{a}$.  Notice that since $a\ne1$, one of $a,\frac{1}{a}$ is greater than $1$.  Let $b$ equal the one that is greater than $1$.  Then, we find similarly (since $f(b)=b$) that $f(xb)=bf(x)$.  Putting $x=b$ into the equation, yields $f(b^2)=b^2$.  Repeating this process we find that $f(b^{2^k})=b^{2^k}$ for all natural $k$.  But, since $b>1$, as $k\to \infty$, we have that $b^{2^k}\to\infty$ which contradicts the fact that $f(x)\to0$ as $x\to \infty$.

Let $x=1$ so   If $f(a)=f(b),$  then $af(1)=f(f(a))=f(f(b))=bf(1)\implies a=b$ because $f(1)$ goes to the real positive integers, not $0.$  Hence, $f$ is injective.  Let $x=y$ so
 so $xf(x)$ is a fixed point of $f.$ Then, let $y=1$ so $f(xf(1))=f(x)\implies f(1)=1$ as $x$ can't be $0$ so $1$ is a fixed point of $f.$  We claim $1$ is the only fixed point of $f.$ Suppose for the sake of contradiction that $a,b$ be fixed points of $f$ so $f(a)=a$ and $f(b)=b.$  Then, setting $x=a,y=b$ in (i) gives  so $ab$ is also a fixed point of $f.$ Also, let $x=\frac{1}{a},y=a$ so  so $\frac{1}{a}$ is a fixed point of $f.$ If $f(a)=a$ with $a>1,$ then $f(a^n)$ is a fixed point of $f$, contradicting (ii).  If $f(a)=a$ with $0<a<1,$ then $f(\frac{1}{a^n})=\frac{1}{a^n}$ so $\frac{1}{a^n}$ is a fixed point, contradicting (ii).  Hence, the only fixed point is $1$ so $xf(x)=1$ so $f(x)=\boxed{\frac{1}{x}}$ and we can easily check that this solution works.


Let $x$, $y$, $z$ be nonnegative real numbers with $x + y + z = 1$. Show that
$0 \leq xy+yz+zx-2xyz \leq \frac{7}{27}$

Solution:
Note that this inequality is symmetric with x,y and z.
To prove  note that $x+y+z=1$ implies that at most one of $x$, $y$, or $z$ is greater than $\frac{1}{2}$. Suppose $x \leq \frac{1}{2}$, WLOG. Then, $xy+yz+zx-2xyz=yz(1-2x)+xy+zx\geq 0$ since $(1-2x)\geq 0$, implying all terms are positive.
To prove $xy+yz+zx-2xyz \leq \frac{7}{27}$, suppose $x \leq y \leq z$. Note that $x \leq y \leq \frac{1}{2}$ since at most one of x,y,z is $\frac{1}{2}$.  Suppose not all of them equals $\frac{1}{3}$-otherwise, we would be done. This implies $x \leq \frac{1}{3}$ and $z \geq \frac{1}{3}$. Thus, define ,    Then, $x'=x+\epsilon$, $z'=z-\epsilon$, and $x'+y'+z'=1$. After some simplification,  since $1-2y>0$ and $z-x-\epsilon=z-\frac{1}{3}>0$. If we repeat the process, defining    after similar reasoning, we see that .


A circle has center on the side $AB$ of the cyclic quadrilateral $ABCD$.  The other three sides are tangent to the circle.  Prove that $AD + BC = AB$.

Let $O$ be the center of the circle mentioned in the problem.  Let $T$ be the second intersection of the circumcircle of $CDO$ with $AB$.  By measures of arcs, $\angle DTA = \angle DCO = \frac{\angle DCB}{2} = \frac{\pi}{2} - \frac{\angle DAB}{2}$.  It follows that $AT = AD$.  Likewise, $TB = BC$, so $AD + BC = AB$, as desired.

Let $O$ be the center of the circle mentioned in the problem, and let $T$ be the point on $AB$ such that $AT = AD$.  Then $\angle DTA = \frac{ \pi - \angle DAB}{2} = \angle DCO$, so $DCOT$ is a cyclic quadrilateral and $T$ is in fact the $T$ of the previous solution.  The conclusion follows.

Let the circle have center $O$ and radius $r$, and let its points of tangency with $BC, CD, DA$ be $E, F, G$, respectively.  Since $OEFC$ is clearly a cyclic quadrilateral, the angle $COE$ is equal to half the angle $GAO$.  Then
Likewise, $DG = OB - EB$.  It follows that
Q.E.D.

We use the notation of the previous solution.  Let $X$ be the point on the ray $AD$ such that $AX = AO$.  We note that $OF = OG = r$; $\angle OFC = \angle OGX = \frac{\pi}{2}$; and $\angle FCO = \angle GXO = \frac{\pi - \angle BAD}{2}$; hence the triangles $OFC, OGX$ are congruent; hence $GX = FC = CE$ and $AO = AG + GX = AG + CE$.  Similarly, $OB = EB + GD$.  Therefore $AO + OB = AG + GD + CE + EB$, Q.E.D.

This solution is incorrect. The fact that $BC$ is tangent to the circle does not necessitate that $B$ is its point of tangency. -Nitinjan06
From the fact that AD and BC are tangents to the circle mentioned in the problem, we have
$\angle{CBA}=90\deg$
and
$\angle{DAB}=90\deg$.
Now, from the fact that ABCD is cyclic, we obtain that
$\angle{BCD}=90\deg$
and
$\angle{CDA}=90\deg$,
such that ABCD is a rectangle.
Now, let E be the point of tangency between the circle and CD. It follows, if O is the center of the circle, that
$\angle{OEC}=\angle{OED}=90\deg$
Since $AO=EO=BO$, we obtain two squares, $AOED$ and $BOEC$.
From the properties of squares we now have
$AD+BC=AO+BO=AB$
as desired.

Lemma. Let $I$ be the in-center of $ABC$ and points $P$ and $Q$ be on the lines $AB$ and $BC$ respectively. Then $BP + CQ = BC$ if and only if $APIQ$ is a cyclic quadrilateral.
Solution. Assume that rays $AD$ and $BC$ intersect at point $P$. Let $S$ be the center od circle touching $AD$, $DC$ and $CB$. Obviosuly $S$ is a $P$-ex-center of $PDB$, hence $\angle DSI=\angle DSP = \frac{1}{2} \angle DCP=\frac{1}{2} \angle A=\angle DAI$ so DASI is concyclic.

https://youtu.be/Ormv0y4ZM1E
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Let $d$ be any positive integer not equal to $2, 5$ or $13$. Show that one can find distinct $a,b$ in the set $\{2,5,13,d\}$ such that $ab-1$ is not a perfect square.

We do casework with modular arithmetic.
$d\equiv 0,3 \pmod{4}: 13d-1$ is not a perfect square.
$d\equiv 2\pmod{4}: 2d-1$ is not a perfect square.
Therefore, $d\equiv 1, \pmod{4}.$ Now consider $d\pmod{16}.$
$d\equiv 1,13 \pmod{16}: 13d-1$ is not a perfect square.
$d\equiv 5,9\pmod{16}: 5d-1$ is not a perfect square.
As we have covered all possible cases, we are done.

Proof by contradiction:
Suppose $p^2=2d-1$, $q^2=5d-1$ and $r^2=13d-1$. From the first equation, $p$ is an odd integer. Let $p=2k-1$. We have $d=2k^2-2k+1$, which is an odd integer. Then $q^2$ and $r^2$ must be even integers, denoted by $4n^2$ and $4m^2$ respectively, and thus $r^2-q^2=4m^2-4n^2=8d$, from which
 can be deduced. Since $m^2-n^2$ is even, $m$ and $n$ have the same parity, so $(m+n)(m-n)$ is divisible by $4$. It follows that the odd integer $d$ must be divisible by $2$, leading to a contradiction. We are done.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Let $p_n (k)$ be the number of permutations of the set $\{ 1, \ldots , n \} , \; n \ge 1$, which have exactly $k$ fixed points.  Prove that
(Remark: A permutation $f$ of a set $S$ is a one-to-one mapping of $S$ onto itself.  An element $i$ in $S$ is called a fixed point of the permutation $f$ if $f(i) = i$.)

Solution:
The sum in question simply counts the total number of fixed points in all permutations of the set.  But for any element $i$ of the set, there are $(n-1)!$ permutations which have $i$ as a fixed point.  Therefore
as desired.
Slightly Clearer Solution
For any $k$, if there are $p_n(k)$ permutations that have $k$ fixed points, then we know that each fixed point is counted once in the product $k \cdot p_n{k}$. Therefore the given sum is simply the number of fixed points among all permutations of $\{ 1, \ldots , n \}$. However, if we take any $x$ such that $1 \le x \le n$ and $x$ is a fixed point, there are $(n-1)!$ ways to arrange the other numbers in the set. Therefore our desired sum becomes $n \cdot (n-1)! = n!$, so we are done.

The probability of any number $i$ where $1\le i\le n$ being a fixed point is $\frac{1}{n}$. Thus, the expected value of the number of fixed points is $n\times \frac{1}{n}=1$.
The expected value is also $\sum_{k=0}^{n} \frac{k \cdot p_n (k)}{n!}$.
Thus,  or


Prove that in the set $\{1,2, \ldots, 1989\}$ can be expressed as the disjoint union of subsets $A_i, \{i = 1,2, \ldots, 117\}$ such that
i.) each $A_i$ contains 17 elements
ii.) the sum of all the elements in each $A_i$ is the same.

Solution:
Let us start pairing numbers in the following fashion, where each pair sums to $1990$:
$(1, 1990-1), (2, 1990-2), \ldots (936, 1054)$
There are a total of $117*8$ pairs above. Let us start putting these pairs into each of the $117$ subsets starting with the first pair $(1, 1990-1)$ going into $A_1$, $(2, 1990-2)$ into $A_2$ and so on $\ldots$ with $(k, 1990-k)$ going into $A_{k(mod 117)}$.
Now we have $16$ numbers present in each of the $117$ subsets all of which have the same total sum. We need $1$ more number to be filled in each subset from the remaining $117$ numbers $(937, 938, ... 1053)$.
Let us arrange these $117$ numbers in the following manner:
$995-58, 995-57,  \ldots, 995-1, 995, 995+1, 995+2, \ldots, 995+57, 995+58$ $==> (1)$
Now notice that for each number that's off by $x$ from $995$, there's a counter number off by $x$ from $995$ in the opposite direction.
So we need to create similar imbalances in the Subsets $A_1$ to $A_{117}$, so that we could add the above $117$ numbers to those imbalances to keep the total sum unchanged.
Now start swapping the $1st$ number of each pair that we added to subsets $A_1$ to $A_{117}$ to create the above imbalances:
Swap $1$ from $A_1$ with $59$ from $A_{59}$ - this creates an imbalance of $+58$ and $-58$
Swap $2$ from $A_2$ with $58$ from $A_{58}$ - this creates an imbalance of $+56$ and $-56$
$\ldots$
Swap $29$ from $A_{29}$ with $31$ from $A_{31}$ - creates an imbalance of $+2$ and $-2$
Leave $30$ in $A_{30}$ as it is - $0$ imbalance.
Similarly,
Swap $60$ from $A_{60}$ with $117$ from $A_{117}$ - this creates an imbalance of $+57$ and $-57$
Swap $61$ from $A_{61}$ with $116$ from $A_{116}$ - this creates an imbalance of $+55$ and $-55$
$\ldots$
Swap $88$ from $A_{88}$ with $89$ from $A_{89}$ - this creates an imbalance of $+1$ and $-1$
Now start adding the $117$ numbers from $(1)$ to the subsets $A_1$ to $A_{117}$ to counter the imbalances $-58$ to $+58$ so that the sum remains unchanged. Notice that each subset now has $17$ elements with total sum = $8*1990 + 995 = 16915$.
$- Kris17$


Chords $AB$ and $CD$ of a circle intersect at a point $E$ inside the circle. Let $M$ be an interior point of the segment $\overline{EB}$. The tangent line at $E$ to the circle through $D, E$, and $M$ intersects the lines $\overline{BC}$ and ${AC}$ at $F$ and $G$, respectively.
If  $\frac{AM}{AB} = t$, find $\frac{EG}{EF}$ in terms of $t$.

With simple angle chasing, we find that triangles $CEG$ and $MDB$ are similar.
so, $GE/EC = MD/MB$. (*)
again with simple angle chasing, we find that triangles $CEF$ and $AMD$ are similar.
so, $EF/DM = CE/AM$. (**)
so, by (*) and (**), we have $GE/EF = MA/MB = t/(t-1)$.
This solution was posted and copyrighted by e.lopes. The original thread for this problem can be found here: [1]

This problem can be bashed with PoP and Ratio Lemma. Rewriting the given ratio gets $\frac{MA}{MB}=\frac{t}{1-t}$.
By Ratio Lemma, $\frac{FB}{FC}=\frac{BE}{CE} \cdot \frac{\sin{\angle{FEB}}}{\sin{\angle{FEC}}}=\frac{DE}{AE} \cdot \frac{\sin{\angle{EDM}}}{\sin{\angle{DME}}}=\frac{DE}{AE} \cdot \frac{EM}{DE}=\frac{ME}{EA}$. Similarly, $\frac{GA}{GC}=\frac{ME}{EB}$. We can rewrite these equalities to get $\frac{AM}{EM}=\frac{BC}{FB}$ and $\frac{BM}{EM}=\frac{AC}{GC}$.
Using Ratio Lemma, $\frac{GE}{\sin{\angle{ACD}}}=\frac{GC}{\sin{\angle{GED}}}$ and $\frac{EF}{\sin{\angle{BCD}}}=\frac{FC}{\sin{\angle{FEC}}}$. Since $\angle{GED}=\angle{FEC}$, we have $\frac{FE}{GE}=\frac{FC}{GC} \cdot \frac{\sin{\angle{BCD}}}{\sin{\angle{ACD}}}$ (eq 1). Note that by Ratio Lemma, $\frac{\sin{\angle{BCD}}}{\sin{\angle{ACD}}}=\frac{CA}{CB} \cdot \frac{EB}{EA}$. Plugging this into (eq 1), we get $\frac{EF}{GE}=\frac{FC}{GC} \cdot \frac{CA}{CB} \cdot \frac{EB}{EA}=\frac{\frac{EA}{EM} \cdot FB}{\frac{EB}{EM} \cdot GA} \cdot \frac{CA}{CB} \cdot \frac{EB}{EA}=\frac{FB}{GA} \cdot \frac{CA}{CB}=\frac{EM}{AM} \cdot \frac{MB}{EM}=\frac{MB}{MA}=\frac{1-t}{t}$. So $\frac{EG}{EF}=\boxed{\frac{t}{1-t}}$.
This solution was posted and copyrighted by AIME12345. The original thread for this problem can be found here: [2]


Find all integers $a$, $b$, $c$ satisfying $1 < a < b < c$ such that $(a - 1)(b -1)(c - 1)$ is a divisor of $abc - 1$.

Solution:
$1<\frac{abc-1}{(a-1)(b-1)(c-1)}<\frac{abc}{(a-1)(b-1)(c-1)}$
$1<\frac{abc-1}{(a-1)(b-1)(c-1)}<\left(\frac{a}{a-1}\right) \left(\frac{b}{b-1}\right) \left(\frac{c}{c-1}\right)$
With $1<a<b<c$ it implies that $a \ge 2$, $b \ge 3$, $c \ge 4$
Therefore, $\frac{a}{a-1}=1+\frac{1}{a-1}$
which for $a$ gives: $\frac{a}{a-1} \le 1+\frac{1}{2-1}$, which gives :$\frac{a}{a-1} \le 2$
for $b$ gives: $\frac{b}{b-1} \le 1+\frac{1}{3-1}$, which gives :$\frac{b}{b-1} \le \frac{3}{2}$
for $c$ gives: $\frac{c}{c-1} \le 1+\frac{1}{4-1}$, which gives :$\frac{c}{c-1} \le \frac{4}{3}$
Substituting those inequalities into the original inequality gives:
$1<\frac{abc-1}{(a-1)(b-1)(c-1)}<\left( 2 \right) \left(\frac{3}{2}\right) \left(\frac{4}{3}\right)$
$1<\frac{abc-1}{(a-1)(b-1)(c-1)}<4$
Since $\frac{abc-1}{(a-1)(b-1)(c-1)}$ needs to be integer,
then $\frac{abc-1}{(a-1)(b-1)(c-1)}=2$ or $\frac{abc-1}{(a-1)(b-1)(c-1)}=3$
Case 1: $\frac{abc-1}{(a-1)(b-1)(c-1)}=2$
$abc-1=2(a-1)(b-1)(c-1)=2abc-2(ab+bc+ac)+2(a+b+c)-2$
Case 1, subcase $a=2$:
$2bc-1=2bc-2(b+c)+2$ gives: $2(b+c)=3$ which has no solution because $2(b+c)$ is even.
Case 1, subcase $a=3$:
$3bc-1=4bc-4(b+c)+4$
$bc-4b-4c+5=0$
$(b-4)(c-4)=11$
$b-4=1$ and $c-4=11$ provides solution $(a,b,c)=(3,5,15)$
Case 2: $\frac{abc-1}{(a-1)(b-1)(c-1)}=3$
$abc-1=3(a-1)(b-1)(c-1)=3abc-3(ab+bc+ac)+3(a+b+c)-3$
Case 2, subcase $a=2$:
$2bc-1=3bc-3(b+c)+3$
$bc-3b-3c+4=0$
$(b-3)(c-3)=5$
$b-3=1$ and $c-3=5$ provides solution $(a,b,c)=(2,4,8)$
Case 2, subcase $a=3$:
$3bc-1=6bc-6(b+c)+6$
Since $(3bc-1$) mod $3 = -1$ and $(6bc-6(b+c)+6)$ mod $3 = 0$, then there is no solution for this subcase.
Now we verify our two solutions:
when $(a,b,c)=(2,4,8)$
$abc-1=(2)(4)(8)-1=63$ and $(a-1)(b-1)(c-1)=(1)(3)(7)=21$
Since $21$ is a factor of $63$, this solutions is correct.
when $(a,b,c)=(3,5,15)$
$abc-1=(3)(5)(15)-1=224$ and $(a-1)(b-1)(c-1)=(2)(4)(14)=112$
Since $112$ is a factor of $224$, this solutions is also correct.
The solutions are: $(a,b,c)=(2,4,8)$ and $(a,b,c)=(3,5,15)$
~ Tomas Diaz. orders@tomasdiaz.com
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Let $f\left(x\right)=x^n+5x^{n-1}+3$, where $n>1$ is an integer. Prove that $f\left(x\right)$ cannot be expressed as the product of two non-constant polynomials with integer coefficients.

Solution:
For the sake of contradiction, assume that $f\left(x\right)=g\left(x\right)h\left(x\right)$ for polynomials $g\left(x\right)$ and $h\left(x\right)$ in $\mathbb{R}$. Furthermore, let $g\left(x\right)=b_mx^m+b_{m-1}x^{m-1}+\ldots+b_1x+b_0$ with $b_i=0$ if $i>m$ and $h\left(x\right)=c_{n-m}x^{n-m}+c_{n-m-1}x^{n-m-1}+\ldots+c_1x+c_0$ with $c_i=0$ if $i>n-m$. This gives that $f\left(x\right)=\sum_{i=0}^{n}\left(\sum_{j=0}^{i}b_jc_{i-j}\right)x^i$.
We have that $3=b_0c_0$, or $3|b_0c_0$. WLOG, let $3|b_0$ (and thus $3\not|c_0$). Since $b_0c_1+b_1c_0=0$ and $3$ divides $b_0$ but not $c_0$, we need that $3|b_1$. We can keep on going up the chain until we get that $3|b_{n-2}$. Then, by equating coefficients once more, we get that $b_0c_{n-1}+b_1c_{n-2}+\ldots+b_{n-2}c_1+b_{n-1}c_0=5$. Taking the equation $\pmod3$ gives that $b_{n-1}c_0\equiv2\pmod3$. This implies that $b_{n-1}\neq0$. Thus, the degree of $g\left(x\right)$ is at least $n-1$. However, because $h\left(x\right)$ is a non-constant factor of $f\left(x\right)$, we have that the degree of $g\left(x\right)$ is at most $n-1$. Thus, the degree of $g\left(x\right)$ is $n-1$, implying that the degree of $h\left(x\right)$ is $1$.
From this fact, we have that there must exist a rational root of $f\left(x\right)$. The only candidates are $1$, $-1$, $3$, and $-3$, though. $f(x)\equiv x+5x+3\equiv1\pmod3$ when $x$ is an integer, so none of these work. Thus, there are no linear factors of $f\left(x\right)$.
In other words, $f\left(x\right)$ cannot be expressed as $g\left(x\right)h\left(x\right)$ for polynomials $g\left(x\right)$ and $h\left(x\right)$ in $\mathbb{R}$. This means that $f\left(x\right)$ cannot be expressed as the product of two non-constant polynomials with integer coefficients.
Q.E.D.


Let $A,B,C,D$ be four distinct points on a line, in that order. The circles with diameters $AC$ and $BD$ intersect at $X$ and $Y$. The line $XY$ meets $BC$ at $Z$. Let $P$ be a point on the line $XY$ other than $Z$. The line $CP$ intersects the circle with diameter $AC$ at $C$ and $M$, and the line $BP$ intersects the circle with diameter $BD$ at $B$ and $N$. Prove that the lines $AM,DN,XY$ are concurrent.

Solution: Since $M$ is on the circle with diameter $AC$, we have $\angle AMC=90$ and so $\angle MCA=90-A$.  We similarly find that $\angle BND=90$.  Also, notice that the line $XY$ is the radical axis of the two circles with diameters $AC$ and $BD$.  Thus, since $P$ is on $XY$, we have $PN\cdot PB=PM\cdot PC$ and so by the converse of Power of a Point, the quadrilateral $MNBC$ is cyclic.  Thus, $90-A=\angle MCA=\angle BNM$.  Thus, $\angle MND=180-A$ and so quadrilateral $AMND$ is cyclic.  Let the name of the circle $AMND$ be $O$ .  Then, the radical axis of $O$ and the circle with diameter $AC$ is line $AM$.  Also, the radical axis of $O$ and the circle with diameter $BD$ is line $DN$.  Since the pairwise radical axes of 3 circles are concurrent, we have $AM,DN,XY$ are concurrent as desired.

Let $AM$ and $PT$ (a subsegment of $XY$) intersect at $Z$. Now, assume that $Z, N, P$ are not collinear. In that case, let $ZD$ intersect the circle with diameter $BD$ at $N'$ and the circle through $D, P, T$ at $N''$.
We know that $\angle AMC = \angle BND = \angle ATP = 90^\circ$ via standard formulae, so quadrilaterals $AMPT$ and $DNPT$ are cyclic. Thus, $N'$ and $N''$ are distinct, as none of them is $N$. Hence, by Power of a Point,  However, because $Z$ lies on radical axis $TP$ of the two circles, we have  Hence, $ZN'' = ZN'$, a contradiction since $D$ and $D'$ are distinct. We therefore conclude that $Z, N, D$ are collinear, which gives the concurrency of $AM, XY$, and $DN$. This completes the problem.

Let $AM$ and $XY$ intersect at $Z$. Because $\angle AMC = \angle BND = \angle APT = 90^\circ$, we have quadrilaterals $AMPT$ and $DNPT$ cyclic. Therefore, $Z$ lies on the radical axis of the two circumcircles of these quadrilaterals. But $Z$ also lies on radical axis $XY$ of the original two circles, so the power of $Z$ with respect to each of the four circles is all equal to $ZM * ZA$. Hence, $Z$ lies on the radical axis $DN$ of the two circles passing through $D$ and $N$, as desired.
what is $T$ here?


We are given a positive integer $r$ and a rectangular board $ABCD$ with dimensions $|AB|=20$, $|BC|=12$.  The rectangle is divided into a grid of $20 \times 12$ unit squares.  The following moves are permitted on the board: one can move from one square to another only if the distance between the centers of the two squares is $\sqrt{r}$. The task is to find a sequence of moves leading from the square with $A$ as a vertex to the square with $B$ as a vertex.
(a) Show that the task cannot be done if $r$ is divisible by $2$ or $3$.
(b) Prove that the task is possible when $r=73$.
(c) Can the task be done when $r=97$?

Solution:
First we define the rectangular board in the cartesian plane with centers of the unit squares as integer coordinates and the following coordinates for the squares at the corners of $A$, $B$, $C$, $D$, as follows: $A=(1,1)$, $B=(20,1)$, $C=(20,12)$, $D=(1,12)$
Let $(x_i,y_i)$ be the coordinates of the piece after move $i$ with $(x_0,y_0)=A=(1,1)$ the initial position of the piece.
$1 \le x_i \le 20$, and also $1 \le y_i \le 12$.
Let $\Delta x_i = x_i-x_{i-1}$, $\Delta y_i = y_i-y_{i-1}$
Then, for any given $r$, we have $(\Delta x_i)^2+(\Delta y_i)^2=\left( \sqrt{r} \right)^2=r$ for all $i$

Part (a):
In order to find out the conditions for which $r$ is divisible by 2 we are going to look at the following three cases:
(1) When both $\Delta x_i$ and $\Delta y_i$ are divisible by $2$.
(2) When both $\Delta x_i$ and $\Delta y_i$ are odd.
(3) When one of $\Delta x_i$ and $\Delta y_i$ is even and the other one is odd.
Case (1): Since $\Delta x_i \equiv 0\;(mod \; 2)$ and $\Delta y_i \equiv 0\;(mod \; 2)$,
then $(\Delta x_i)^2+(\Delta y_i)^2 \equiv (0^2+0^2)\;(mod \; 2)\equiv 0\;(mod \; 2)$.
Thus, for $r\equiv 0\;(mod \; 2)$, this case is a valid one.
Case (2): Since $\Delta x_i \equiv 1\;(mod \; 2)$ and $\Delta y_i \equiv 1\;(mod \; 2)$,
then $(\Delta x_i)^2+(\Delta y_i)^2 \equiv (1^2+1^2)\;(mod \; 2)\equiv 0\;(mod \; 2)$.
Thus, for $r\equiv 0\;(mod \; 2)$, this case is a valid one.
Case (3): Since $\Delta x_i \equiv 1\;(mod \; 2)$ and $\Delta y_i \equiv 0\;(mod \; 2)$, or $\Delta x_i \equiv 0\;(mod \; 2)$ and $\Delta y_i \equiv 1\;(mod \; 2)$,
then $(\Delta x_i)^2+(\Delta y_i)^2 \equiv (1^2+0^2)\;(mod \; 2)\equiv 1\;(mod \; 2)\not\equiv 0\;(mod \; 2)$.
Thus, for $r\equiv 0\;(mod \; 2)$, this case is NOT a valid one.
Having proved that Case (1) and Case (2) are the only valid cases for $r\equiv 0\;(mod \; 2)$ we are going to see what happens for both cases when we start with a square where both coordinates are odd:
if $(x_{i-1},y_{i-1}) \equiv (1,1) \;(mod \; 2)$,
then for case (1): $(x_{i-1}+\Delta x_i,y_{i-1}+\Delta y_i) \equiv (1+0,1+0)  \;(mod \; 2) \equiv (1,1) \;(mod \; 2)$
and for case (2): $(x_{i-1}+\Delta x_i,y_{i-1}+\Delta y_i) \equiv (1+1,1+1)  \;(mod \; 2) \equiv (0,0) \;(mod \; 2)$
and $(x_{i-1}+2\Delta x_i,y_{i-1}+2\Delta y_i) \equiv (1+2,1+2)  \;(mod \; 2) \equiv (1,1) \;(mod \; 2)$
This means that when $r$ is divisible by two, when starting at $(1,1)$ no matter how many moves you make all $(x_{i},y_{i})$ will either be $\equiv (0,0) \;(mod \; 2)$ or $\equiv (1,1) \;(mod \; 2)$.
Since the ending coordinate is $(20,1) \equiv (0,1) \;(mod \; 2) \not\equiv (1,1) \;(mod \; 2)$ and $\not\equiv (0,0) \;(mod \; 2)$, then the task cannot be done if $r$ is divisible by $2$.
Now we look at the conditions for which $r$ is divisible by 3 by looking at the following three cases:
(4) When both $\Delta x_i$ and $\Delta y_i$ are divisible by $3$.
(5) When one of them is not divisible by $3$ and the other one is.
(6) When neither $\Delta x_i$ nor $\Delta y_i$ is divisible by $3$.
Case (4): Since $\Delta x_i \equiv 0\;(mod \; 3)$ and $\Delta y_i \equiv 0\;(mod \; 3)$,
then $(\Delta x_i)^2+(\Delta y_i)^2 \equiv (0^2+0^2)\;(mod \; 3)\equiv 0\;(mod \; 3)$.
Thus, for $r\equiv 0\;(mod \; 3)$, this case is a valid one.
Case (5): Since either $\Delta x_i$ or $\Delta y_i \equiv \pm 1\;(mod \; 3)$ and the other $\equiv 1\;(mod \; 3)$,
then $(\Delta x_i)^2+(\Delta y_i)^2 \equiv ((\pm 1)^2+0^2)\;(mod \; 3)\equiv 1\;(mod \; 3)$.
Thus, for $r\equiv 0\;(mod \; 3)$, this case is NOT a valid one.
Case (6): Since $\Delta x_i \equiv \pm 1\;(mod \; 3)$ and $\Delta y_i \equiv \pm1 \;(mod \; 3)$,
then $(\Delta x_i)^2+(\Delta y_i)^2 \equiv ((\pm 1)^2+(\pm 1)^2)\;(mod \; 3)\equiv 2\;(mod \; 3)\not\equiv 0\;(mod \; 3)$.
Thus, for $r\equiv 0\;(mod \; 3)$, this case is NOT a valid one.
Having proved that Case (4) is the only valid case for $r\equiv 0\;(mod \; 3)$ we are going to see what happens when we start with a square that is $\equiv (1,1)\;(mod \; 3)$
if $(x_{i-1},y_{i-1}) \equiv (1,1) \;(mod \; 3)$, then $(x_{i-1}+\Delta x_i ,y_{i-1}+\Delta y_i) \equiv (1+0,1+0) \;(mod \; 3) \equiv (1,1) \;(mod \; 3)$.
Therefore starting at any $(x_{i-1},y_{i-1}) \equiv (1,1) \;(mod \; 3)$ no matter how many moves the piece will always land at another square $\equiv (1,1) \;(mod \; 3)$.  Since we start at $(1,1)$, then the  piece will always land at squares that are $\equiv (1,1) \;(mod \; 3)$.
Since final square is $(20,1) \equiv (2,1) \;(mod \; 3) \not\equiv (1,1) \;(mod \; 3)$, then the task cannot be done if $r$ is divisible by $3$.
In summary the task cannot be done if $r$ is divisible by $2$ or $r$ is divisible by $3$.

Part (b):
When $r=73$ we have $8^2+3^2=73$
Therefore the moves can have the following values:

Since we start at $(1,1)$ and we want to end at $(20,1)$ we can write the following $11$ valid moves:

Having shown that all moves comply with the possible values for $(\Delta x_i, \Delta y_i)$ and that all $(x_i, y_i)$ are inside the rectangular grid, then the task is possible when $r=73$.

Part (c):
When $r=97$ we have $9^2+4^2=97$
Therefore the moves can have the following values:

Let $S$ be a set of the squares of the rectangle with the condition $x_i \equiv \left\lceil \frac{y_i}{4} \right\rceil  \;(mod \; 2)$ for $(x_i,y_i)$.  That is, the reminder of $x_i$ when divided by 2 is the same as the reminder of $\left\lceil \frac{y_i}{4} \right\rceil$ when divided by 2 where $\left\lceil k \right\rceil$ is the smallest integer that is not less than $k$.  If that condition is true, then $(x_i,y_i) \in S$
Now let's look at a case (c1) where $(x_i,y_i) \in S$ and $x_i \equiv 0 \;(mod \; 2)$, thus $\left\lceil \frac{y_i}{4} \right\rceil \equiv 0 \;(mod \; 2)$:
c1 subcase 1 : $(x_{i+1},y_{i+1})=(x_i \pm 9,y_i \pm 4)$:
$(x_i \pm 9) \equiv (0 \pm 9)\;(mod \; 2) \equiv 1 \;(mod \; 2)$
and $\left\lceil \frac{y_i \pm 4}{4} \right\rceil \equiv \left\lceil \frac{y_i}{4} \right\rceil \pm 1 \;(mod \; 2)\equiv (0 \pm 1) \;(mod \; 2)\equiv 1 \;(mod \; 2)$
since $x_{i+1} \equiv \left\lceil \frac{y_{i+1}}{4} \right\rceil  \;(mod \; 2)$, then $(x_{i+1},y_{i+1}) \in S$ for this subcase.
c1 subcase 2 : $(x_{i+1},y_{i+1})=(x_i \pm 4,y_i \pm 9)$:
This move is not allowed because the only values of $1 \le y_i \le 12$ such that $\left\lceil \frac{y_i}{4} \right\rceil \equiv 0 \;(mod \; 2)$ are $5,6,7,8$.  Adding or subtracting 9 from any of these numbers will either make $y_{i+1}<0$ or $y_{i+1}>12$ and will put the piece outside of the board.
In summary, for case (c1), $(x_{i+1},y_{i+1}) \in S$
Now let's look at a case (c2) where $(x_i,y_i) \in S$ and $x_i \equiv 1 \;(mod \; 2)$, thus $\left\lceil \frac{y_i}{4} \right\rceil \equiv 1 \;(mod \; 2)$:
c2 subcase 1 : $(x_{i+1},y_{i+1})=(x_i \pm 9,y_i \pm 4)$:
$(x_i \pm 9) \equiv (1 \pm 9)\;(mod \; 2) \equiv 0 \;(mod \; 2)$
and $\left\lceil \frac{y_i \pm 4}{4} \right\rceil \equiv \left\lceil \frac{y_i}{4} \right\rceil \pm 1 \;(mod \; 2)\equiv (1 \pm 1) \;(mod \; 2)\equiv 0 \;(mod \; 2)$
since $x_{i+1} \equiv \left\lceil \frac{y_{i+1}}{4} \right\rceil  \;(mod \; 2)$, then $(x_{i+1},y_{i+1}) \in S$ for this subcase.
c2 subcase 2 : $(x_{i+1},y_{i+1})=(x_i \pm 4,y_i \pm 9)$:
$(x_i \pm 4) \equiv (1 \pm 4)\;(mod \; 2) \equiv 1 \;(mod \; 2)$
Notice that the only values of $1 \le y_i \le 12$ such that $\left\lceil \frac{y_i}{4} \right\rceil \equiv 0 \;(mod \; 2)$ are $1,2,3,4,9,10,11,12$.  Adding 9 to the values of 1,2, or 3 or subtracting 9 from the values of 10, 11, or 12, will result in $\left\lceil \frac{y_{i+1}}{4} \right\rceil \equiv 1 \;(mod \; 2)$.  However, subtracting 9 from the values of 1,2, or 3, or adding 9 for the values of 10,11, or 12 will put the piece outside the board and not a valid move.  Furthermore, for the values of 4 and 9, adding or subtracting 9 from them will result in the piece being outside of the board and not a valid move.  Therefore for all valid moves in this subcase which are 9 added to 1, 2, or 3 or 9 subtracted from 10, 11, or 12, the result will be $\left\lceil \frac{y_{i+1}}{4} \right\rceil \equiv 1 \;(mod \; 2)$
since $x_{i+1} \equiv \left\lceil \frac{y_{i+1}}{4} \right\rceil  \;(mod \; 2)$, then $(x_{i+1},y_{i+1}) \in S$ for this subcase.
In summary, for case (c2), $(x_{i+1},y_{i+1}) \in S$
Therefore if $(x_{i},y_{i}) \in S$ then $(x_{i+1},y_{i+1}) \in S$
Now we look at the starting point: $(1,1)$:
Since $1 \equiv 1\;(mod \; 2)$ and $\left\lceil \frac{1}{4} \right\rceil \equiv 1\;(mod \; 2)$, then $(1,1) \in S$ and all subsequent squares after that $\in S$
Now let's look at the end point: $(20,1)$:
Since $20 \equiv 0\;(mod \; 2)$ and $\left\lceil \frac{1}{4} \right\rceil \equiv 1\;(mod \; 2)$, then $20 \not\equiv \left\lceil \frac{1}{4} \right\rceil \;(mod \; 2)$ and $(20,1) \not\in S$
Since $(20,1) \not\in S$, then there are no valid moves starting from $(1,1)$ that will end in $(20,1)$
Therefore the task cannot be done when $r=97$.
~Tomas Diaz. orders@tomasdiaz.com
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


In the plane the points with integer coordinates are the vertices of unit squares.  The squares are colored alternatively black and white (as on a chessboard).
For any pair of positive integers $m$ and $n$, consider a right-angled triangle whose vertices have integer coordinates and whose legs, of lengths $m$ and $n$, lie along edges of the squares.
Let $S_{1}$ be the total area of the black part of the triangle and $S_{2}$ be the total area of the white part.
Let $f(m,n)=|S_{1}-S_{2}|$
(a) Calculate $f(m,n)$ for all positive integers $m$ and $n$ which are either both even or both odd.
(b) Prove that $f(m,n) \le \frac{1}{2} max\left\{ m,n \right\}$ for all $m$ and $n$.
(c) Show that there is no constant $C$ such that $f(m,n)<C$ for all $m$ and $n$.

Solution:
For any pair of positive integers $m$ and $n$, consider a rectangle $ABCD$ whose vertices have integer coordinates and whose legs, of lengths $m$ and $n$, lie along edges of the squares.
Let $A$, $B$, $C$, and $D$, be the lower left vertex, lower right vertex, upper right vertex, and upper left vertex of rectangle $ABCD$ respectively.
Let $T_{1}$ be the total area of the black part of the rectangle and $T_{2}$ be the total area of the white part.
Let $g(m,n)=|T_{1}-T_{2}|$

Part (a)
case: $m$ and $n$ which are both even
Since $m$ and $n$ are both even, the total area of the rectangle $ABCD$ is $m \times n$ which is also even
Since every row has an even number of squares there are equally as many white squares than black squares for each row.
Since every column has an even number of squares there are equally as many white squares than black squares for each column.
This means that in the rectangle there are equal number of white squares and black squares.
Therefore $T_{1}=T_{2}=\frac{mn}{2}$ and $g(m,n)=|T_{1}-T_{2}|=0$
Let $M$ be the midpoint of line $AC$.  Them $M$ is at coordinate $(A_{x}+\frac{m}{2},A_{y}+\frac{n}{2})$
Since both $m$ and $n$ are even, then $M$ has integer coordinates.
Starting with vertex $A$, because the length of $AB$ is even, then the color for the square inside rectangle $ABCD$ closest to $B$ is the opposite color of the square inside rectangle $ABCD$ closest to $A$, then starting with vertex $B$, because the length of $BC$ is even, then the color of the square inside rectangle $ABCD$ closest to $C$ is the opposite color of the square inside rectangle $ABCD$ closest to $B$.  this means that the color of the square inside rectangle $ABCD$ closest to $A$ is the same as the color of the square inside rectangle $ABCD$ closest to $C$.  Likewise, the color of the square inside rectangle $ABCD$ closest to $B$ is the same as the color of the square inside rectangle $ABCD$ closest to $D$.
This color pattern and the fact that the midpoint $M$ has integer coordinates indicates that triangle $ABC$ has the same color pattern as triangle $CDA$ rotated 180 degrees.
Therefore, the white area in triangle $ABC$ is the same as the white area in triangle $CDA$ and the black area in triangle $ABC$ is the same as the black area in triangle $CDA$.
Thus $S_{1}=\frac{T_{1}}{2}$ and $S_{2}=\frac{T_{2}}{2}$, which gives $f(m,n)=\frac{g(m,n)}{2}=0$
Therefore $f(m,n)=0$ when both $m$ and $n$ are even.
case: $m$ and $n$ which are both odd
Since $m$ and $n$ are both odd, the total area of the rectangle $ABCD$ is $m \times n$ which is also odd
Since the total area is odd, then $\frac{mn}{2}$ is not an integer but $\frac{mn+1}{2}$ and $\frac{mn-1}{2}$ are.
This means that in the rectangle there are $\frac{mn+1}{2}$ squares of one color and $\frac{mn+1}{2}$ squares of the other color
$g(m,n)=|T_{1}-T_{2}|=\left| \frac{mn+1}{2}-\frac{mn-1}{2} \right|=1$
Let $M$ be the midpoint of line $AC$.  Them $M$ is at coordinate $(A_{x}+\frac{m}{2},A_{y}+\frac{n}{2})$  Since both $m$ and $n$ are odd, then $M$ has non-integer coordinates coordinates but their decimal portions are both $0.5$. This means that $M$ lies in the middle of the center square.
Starting with vertex $A$, because the length of $AB$ is odd, then the color for the square inside rectangle $ABCD$ closest to $B$ is the same color of the square inside rectangle $ABCD$ closest to $A$, then starting with vertex $B$, because the length of $BC$ is odd, then the color of the square inside rectangle $ABCD$ closest to $C$ is the same color of the square inside rectangle $ABCD$ closest to $B$.  this means that the color of the square inside rectangle $ABCD$ closest to $A$ is the same as the color of the square inside rectangle $ABCD$ closest to $C$.  Likewise, the color of the square inside rectangle $ABCD$ closest to $B$ is the same as the color of the square inside rectangle $ABCD$ closest to $D$.
This color pattern and the fact that the midpoint $M$ in in the center of the middle square that triangle $ABC$ has the same color pattern as triangle $CDA$ rotated 180 degrees.
Therefore, the white area in triangle $ABC$ is the same as the white area in triangle $CDA$ and the black area in triangle $ABC$ is the same as the black area in triangle $CDA$.
Thus $f(m,n)=\frac{g(m,n)}{2}=\frac{1}{2}$
Therefore $f(m,n)=\frac{1}{2}$ when both $m$ and $n$ are odd.
To summarize part (a),
$f(m,n)=\begin{cases} 0 & m,n\;are\;both\;even \\ \frac{1}{2} & m,n\;are\;both\;odd\\ something \; else & othwerwise\end{cases}$

Part (b)
Since $f(m,n)=\begin{cases} 0 & m,n\;are\;both\;even \\ \frac{1}{2} & m,n\;are\;both\;odd\\ something \; else & othwerwise\end{cases}$ then for these cases the minimum values that $m$ and $n$ can have are 1.  So for the cases where both are odd or both are even $f(m,n) \le \frac{1}{2} max\left\{ m,n \right\}$ with equality at $m=n=1$
Now we need to find the case were one of them is odd and the other one is even.
case $max\left\{ m,n \right\}$ is odd and $min\left\{ m,n \right\}$ is even, means that $max\left\{ m,n \right\}-1$ is even
Therefore $f\left( max\left\{ m,n \right\}-1,min\left\{ m,n \right\} \right)=0$
$f(m,n)=f\left( max\left\{ m,n \right\}-1,min\left\{ m,n \right\} \right)+h(1,min\left\{ m,n \right\})$,
where $h(1,n)$ is the absolute value of the difference between the white area and black area of a triangle with base or size 1 and height n where this triangle is not necessarily a rectangular triangle.
Therefore $h(1,n) \le$ area of such triangle.  Thus, $h(1,min\left\{ m,n \right\}) \le \frac{1}{2}min\left\{ m,n \right\}$
$f\left( max\left\{ m,n \right\}-1,min\left\{ m,n \right\} \right)+h(1,min\left\{ m,n \right\}) \le 0 +\frac{1}{2}min\left\{ m,n \right\}$
$f(m,n) \le \frac{1}{2}min\left\{ m,n \right\}$ when $max\left\{ m,n \right\}$ is odd and $min\left\{ m,n \right\}$ is even
Which also means that
$f(m,n) \le \frac{1}{2}max\left\{ m,n \right\}$ when $max\left\{ m,n \right\}$ is odd and $max\left\{ m,n \right\}$ is even
Now we look at the case where $max\left\{ m,n \right\}$ is even and $min\left\{ m,n \right\}$ is odd, means that $min\left\{ m,n \right\}-1$ is even
Therefore $f\left( min\left\{ m,n \right\}-1,max\left\{ m,n \right\} \right)=0$
$f(m,n)=f\left( min\left\{ m,n \right\}-1,max\left\{ m,n \right\} \right)+h(1,max\left\{ m,n \right\})$,
Thus, $h(1,max\left\{ m,n \right\}) \le \frac{1}{2}max\left\{ m,n \right\}$
$f\left( min\left\{ m,n \right\}-1,max\left\{ m,n \right\} \right)+h(1,max\left\{ m,n \right\}) \le 0 +\frac{1}{2}max\left\{ m,n \right\}$
$f(m,n) \le \frac{1}{2}max\left\{ m,n \right\}$ when $max\left\{ m,n \right\}$ is even and $min\left\{ m,n \right\}$ is odd
Therefore, for all four cases: $m$ and $n$ are both odd; $m$ and $n$ are both even; $max\left\{ m,n \right\}$ is odd with $min\left\{ m,n \right\}$ is even; and $max\left\{ m,n \right\}$ is even with $min\left\{ m,n \right\}$ is odd we have:
$f(m,n) \le \frac{1}{2}max\left\{ m,n \right\}$ with equality at $m=n=1$

Part (c)
Consider the case where $m=k$ and $n=k+1$ and k is even.
$f(m,n)=f(k,k+1)=f(k,k)+h(k,1)=h(k,1)$
We're going to calculate $h(k,1)$ noticing that the region for $h(k,1)$ in $f(m,n)$ will be the triangle formed by lines $y=kx$, $y=\frac{k+1}{k}x$ and $x=k$.
So, to calculate $h(k,1)$ we first calculate the total area of the black triangular regions within the triangle (assuming the first corner is white) with the following series formula:
$S_{1}=\sum_{j=1}^{k}\frac{1}{2}\left( \frac{k+1}{k}j-j \right)\left(j- \frac{k}{k+1}j \right)=\sum_{j=1}^{k}\frac{1}{2}\left( \frac{k+1-k}{k} \right)\left( \frac{k+1-k}{k+1} \right)j^{2}$
$S_{1}=\frac{1}{2k(k+1)}\sum_{j=1}^{k}j^{2}=\frac{1}{2k(k+1)}\frac{k(k+1)(2k+1)}{6}=\frac{2k+1}{12}$
Then, $S_{2}=\frac{k}{2}-S_{1}=\frac{k}{2}-\frac{2k+1}{12}=\frac{4k-1}{12}$
$h(k,1)=|S_{2}-S_{1}|=\left| \frac{4k-1}{12}-\frac{2k+1}{12}  \right|=\frac{k-1}{6}$
Thus for even $k$ we have $f(k,k+1)=h(k,1)=\frac{k-1}{6}$
Since for this case, $C=\lim_{k \to \infty} f(k,k+1)=\lim_{k \to \infty} \frac{k-1}{6}=\infty$, then there is no upper bound for this case.  Since part (c) describes an upper bound for all $m$ and $n$, then having found one case where there is no upper bound means that there is no upper bound when considering all $m$ and $n$
Therefore, there is no constant $C$ such that $f(m,n)<C$ for all $m$ and $n$ because $C \to \infty\;$ on some cases.
~ Tomas Diaz. orders@tomasdiaz.com
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


In the convex quadrilateral $ABCD$, the diagonals $AC$ and $BD$ are perpendicular and the opposite sides $AB$ and $DC$ are not parallel. Suppose that the point $P$, where the perpendicular bisectors of $AB$ and $DC$ meet, is inside $ABCD$. Prove that $ABCD$ is a cyclic quadrilateral if and only if the triangles $ABP$ and $CDP$ have equal areas.

Solution: This problem needs a solution. If you have a solution for it, please help us out by adding it.


Determine all finite sets $S$ of at least three points in the plane which satisfy the following condition:
For any two distinct points $A$ and $B$ in $S$, the perpendicular bisector of the line segment $AB$ is an axis of symmetry of $S$.

Solution:
Upon reading this problem and drawing some points, one quickly realizes that the set $S$ consists of all the vertices of any regular polygon.
Now to prove it with some numbers:
Let $S=\left\{ P_{0},P_{1},P_{2},...,P_{n-1} \right\}$, with $n\ge 3$, where $P_{i}$ is a vertex of a polygon which we can define their $xy$ coordinates as: $P_{i}=\left\langle Rcos\left( \frac{2\pi}{n}i \right),Rsin\left( \frac{2\pi}{n}i \right) \right\rangle$ for $i=0,1,2,...,(n-1)$.
That defines the vertices of any regular polygon with $R$ being the radius of the circumcircle of the regular $n$-sided polygon.
Now we can pick any points $A$ and $B$ of the set as:
$A=P_{a}$ and $B=P_{b}$, where $a=0,1,2,...,(n-1)$; $b=0,1,2,...,(n-1)$; and $a\ne b$
Then,
$A=\left\langle Rcos\left( \frac{2\pi}{n}a \right),Rsin\left( \frac{2\pi}{n}a \right) \right\rangle$
and $B=\left\langle Rcos\left( \frac{2\pi}{n}b \right),Rsin\left( \frac{2\pi}{n}b \right) \right\rangle$
Let $O$ be point $(0,0)$ which is not part of $S$
Then, $\angle P_{0}OA = \frac{2\pi}{n}a$, and $\angle P_{0}OB = \frac{2\pi}{n}b$
The perpendicular bisector of $AB$ passes through $O$.
Let point $M_{AB}$, not in $S$ be a point that passes through the perpendicular bisector of $AB$ at a distance $R$ from $O$
Then, $\angle P_{0}OM_{AB} =\frac{2\pi}{n}\frac{a+b}{2}$ and $M_{AB}=\left\langle Rcos\left( \frac{2\pi}{n}\frac{a+b}{2} \right),Rsin\left( \frac{2\pi}{n}\frac{a+b}{2} \right) \right\rangle$
CASE I: $a+b$ is even
$k=\frac{a+b}{2}$ and $k$ is integer
Then $M_{AB}=\left\langle Rcos\left( \frac{2\pi}{n}k \right),Rsin\left( \frac{2\pi}{n}k \right) \right\rangle=P_{k}$
This means that the perpendicular bisector also passes through a point $P_{k}$ of $S$
Let $c$ be any positive integer
$\angle P_{k}OP_{(k+c)\; mod\; n}=\frac{2\pi}{n}\left( (k+c-k)\; mod\; n \right)=\frac{2\pi}{n}\left( c\; mod\; n \right)$
and
$\angle P_{k}OP_{(k-c)\; mod\; n}=\frac{2\pi}{n}\left( (k-(k-c))\; mod\; n \right)=\frac{2\pi}{n}\left( c\; mod\; n \right)$
Therefore, $\angle P_{k}OP_{(k+c)\; mod\; n}=\angle P_{k}OP_{(k-c)\; mod\; n}$ for any integer $c$.
Also, since $\left| OP_{(k+c)\; mod\; n} \right|=\left| OP_{(k-c)\; mod\; n} \right|=R$ for any integer $c$
then this proves that the bisector of any points $A$ and $B$ is an axis of symmetry for this case.
CASE II: $a+b$ is odd
$k=\frac{a+b+1}{2}$ and $k$ is integer
$m=\frac{a+b-1}{2}$ and $m$ is integer
Then $M_{AB}=\left\langle Rcos\left( \frac{2\pi}{n}\frac{a+b}{2} \right),Rsin\left( \frac{2\pi}{n}\frac{a+b}{2} \right) \right\rangle$
This means that the perpendicular bisector does not pass through any point of $S$, but their closest points are $P_{k}$ and $P_{m}$ and that $\angle MOP_{k}=\angle MOP_{m}=\frac{\pi}{n}$
Let $c$ be any positive integer
$\angle P_{k}OP_{(k+c)\; mod\; n}=\frac{2\pi}{n}\left( (k+c-k)\; mod\; n \right)=\frac{2\pi}{n}\left( c\; mod\; n \right)$
$\angle MOP_{(k+c)\; mod\; n}=\angle MOP_{k}+\angle P_{k}OP_{(k+c)\; mod\; n}=\frac{\pi}{n}+\frac{2\pi}{n}\left( c\; mod\; n \right)$
and
$\angle P_{m}OP_{(m-c)\; mod\; n}=\frac{2\pi}{n}\left( (m-(m-c))\; mod\; n \right)=\frac{2\pi}{n}\left( c\; mod\; n \right)$
$\angle MOP_{(m-c)\; mod\; n}=\angle MOP_{m}+\angle P_{m}OP_{(m-c)\; mod\; n}=\frac{\pi}{n}+\frac{2\pi}{n}\left( c\; mod\; n \right)$
Therefore, $\angle MOP_{(k+c)\; mod\; n}=\angle MOP_{(m-c)\; mod\; n}$ for any integer $c$.
Since $m=k-1$, $\angle MOP_{(k+c)\; mod\; n}=\angle MOP_{(k-1-c)\; mod\; n}$
Also, since $\left| OP_{(k+c)\; mod\; n} \right|=\left| OP_{(m-c)\; mod\; n} \right|=R$ for any integer $c$
then this proves that the bisector of any points $A$ and $B$ is an axis of symmetry for this case.
Having proven both cases, then the set $S$ of points that comply with the given condition is the set of the vertices of any regular polygon of any number of sides.
~Tomas Diaz. orders@tomasdiaz.com
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Two circles $G_1$ and $G_2$ intersect at two points $M$ and $N$. Let $AB$ be the line tangent to these circles at $A$ and $B$, respectively, so that $M$ lies closer to $AB$ than $N$. Let $CD$ be the line parallel to $AB$ and passing through the point $M$, with $C$ on $G_1$ and $D$ on $G_2$. Lines $AC$ and $BD$ meet at $E$; lines $AN$ and $CD$ meet at $P$; lines $BN$ and $CD$ meet at $Q$. Show that $EP=EQ$.

Solution:
$\textbf{Proof of problem:}$ Let ray $NM$ intersect $AB$ at $X$. By our lemma, $\textit{(the two circles are tangent to AB)}$, $X$ bisects $AB$. Since $\triangle{NAX}$ and $\triangle{NPM}$ are similar, and $\triangle{NBX}$ and $\triangle{NQM}$ are similar implies $M$ bisects $PQ$.
By simple parallel line rules, $\angle{ABM}=\angle{EBA}$. Similarly, $\angle{BAM}=\angle{EAB}$, so by $\textit{ASA}$ criterion, $\triangle{ABM}$ and $\triangle{EAB}$ are congruent.
Now, $\angle{EBA} = \angle{ABM} = \angle{BDM}$ and $\angle{ABM} = \angle{BMD}$ since $CD$ is parallel to $AB$. But $AB$ is tangent to the circumcircle of $\triangle{BMD}$ hence $\angle{ABM} = \angle{BDM}$ and that implies $\angle{BMD} = \angle{BDM} .$So$\triangle{BMD}$ is isosceles and $\angle{BMD}=\angle{BDM}$ .
Join points $E$ and $M$, $EM$ is perpendicular on $PQ$ (why?), previously we proved $MP = MQ$, hence $\triangle{EPQ}$ is isoscles and $EP = EQ$ .


Consider an acute triangle $\triangle ABC$. Let $P$ be the foot of the altitude of triangle $\triangle ABC$ issuing from the vertex $A$, and let $O$ be the circumcenter of triangle $\triangle ABC$. Assume that $\angle C \geq \angle B+30^{\circ}$. Prove that $\angle A+\angle COP < 90^{\circ}$.

Solution:
Take $D$ on the circumcircle with $AD \parallel  BC$. Notice that $\angle CBD = \angle BCA$, so $\angle ABD \ge 30^\circ$. Hence $\angle AOD \ge 60^\circ$. Let $Z$ be the midpoint of $AD$ and $Y$ the midpoint of $BC$. Then $AZ \ge R/2$, where $R$ is the radius of the circumcircle. But $AZ = YP$ (since $AZYP$ is a rectangle).
Now $O$ cannot coincide with $Y$ (otherwise $\angle A$ would be $90^\circ$ and the triangle would not be acute-angled). So $OP > YP \ge R/2$. But $PC = YC - YP < R - YP \le R/2$. So $OP > PC$.
Hence $\angle COP < \angle OCP$. Let $CE$ be a diameter of the circle, so that $\angle OCP = \angle ECB$. But $\angle ECB = \angle EAB$ and $\angle EAB + \angle BAC = \angle EAC = 90^\circ$, since $EC$ is a diameter. Hence $\angle COP + \angle BAC < 90^\circ$.

Notice that because $\angle{PCO} = 90^\circ - \angle{A}$, it suffices to prove that $\angle{POC} < \angle{PCO}$, or equivalently $PC < PO.$
Suppose on the contrary that $PC > PO$. By the triangle inequality, $2 PC = PC + PC > PC + PO > CO = R$, where $R$ is the circumradius of $ABC$. But the Law of Sines and basic trigonometry gives us that $PC = 2R \sin B \cos C$, so we have $4 \sin B \cos C > 1$. But we also have $4 \sin B \cos C \le 4 \sin B \cos (B + 30^\circ) = 2 (\sin (2B + 30^\circ) - \sin 30^\circ) \le 2 (1 - \frac{1}{2}) = 1$ because $\angle{C} \ge \angle{B} + 30^\circ$, and so we have a contradiction. Hence $PC < PO$ and so $\angle{PCO} + \angle{A} < 90^\circ$, as desired.


$S$ is the set of all $(h,k)$ with $h,k$ non-negative integers such that $h + k < n$. Each element of $S$ is colored red or blue, so that if $(h,k)$ is red and $h' \le h,k' \le k$, then $(h',k')$ is also red. A type $1$ subset of $S$ has $n$ blue elements with different first member and a type $2$ subset of $S$ has $n$ blue elements with different second member. Show that there are the same number of type $1$ and type $2$ subsets.


Let $ABC$ be an acute-angled triangle with $AB\neq AC$. The circle with diameter $BC$ intersects the sides $AB$ and $AC$ at $M$ and $N$ respectively. Denote by $O$ the midpoint of the side $BC$. The bisectors of the angles $\angle BAC$ and $\angle MON$ intersect at $R$. Prove that the circumcircles of the triangles $BMR$ and $CNR$ have a common point lying on the side $BC$.

Solution:
Let $\angle{ACB} = a$, $\angle{CBA} = b$, and $\angle{ONR} = k$. Call $\omega$ the circle with diameter $BC$ and $\odot{AMN}$ the circumcircle of $\triangle{AMN}$.
Our ultimate goal is to show that $\angle{CNR} + \angle{RMB} = 180^\circ$. To show why this solves the problem, assume this statement holds true. Call $K$ the intersection point of the circumcircle of $\triangle{CNR}$ with side $BC$. Then, $\angle{RKC} = 180^\circ - \angle{CNR}$, and $\angle{RKB} = \angle{CNR}$. Since $\angle{RMB} = 180^\circ - \angle{CNR}$, $\angle{RKB} + \angle{RMB}  = 180^\circ$, implying $K$ also lies on the circumcircle of $\triangle{BMR}$, thereby solving the problem.
We now prove that $\angle{CNR} + \angle{RMB} = 180^\circ$. Note that $ON$ and $OM$ are radii of $\omega$, so $\triangle{MON}$ is isosceles. The bisector of $\angle{MON}$ is thus the perpendicular bisector of $MN$. Since $R$ lies on the bisector of $\angle{MON}$, $\angle{ONR} = \angle{RMO} = k$. Angle computations yield that   from $\angle{AMN} = 180^\circ - \angle{BMN} = 180^\circ - (180^\circ - \angle{ACB}) = \angle{ACB}$ and from $\angle{BMO} = \angle{MBO} =$ $\angle{ABC}$.
The bisector of $\angle{BAC}$ hits $\odot{AMN}$ at the midpoint of the arc $MN$ not containing $A$. This point must lie on the perpendicular bisector of segment $MN$, which is the bisector of $\angle{MON}$. It follows that $R$ is indeed the midpoint of arc $MN$, so $A$, $M$, $R$, $N$, are concyclic. Since $\angle{RAN}$ and $\angle{RMN}$ subtend the same arc $NR$, $\angle{RAN}$ = $\angle{RMN}$. With $AR$ being the bisector of $\angle{BAC}$, we have  We know that $\angle{RMN} = 180^\circ - b - k - a$. so we have $180^\circ - b - k - a = 90^\circ - \tfrac{a}{2} - \tfrac{b}{2}$. Since $\angle{CNR} = \angle{CNO} + \angle{ONR} = a + k$, and $\angle{RMB} = \angle{OMB} + \angle{RMO} = b + k$, we have
The problem is solved.
$\textbf{NOTE:}$ We have $\angle{RKB} + \angle{KBA} + \angle{BAK} = 180^\circ \implies \angle{BAK} = 180^\circ - (180^\circ - \angle{RMB})  - \angle{KBA}$. Noting that $180^\circ - \angle{RMB} = 180^\circ - b - k = 180^\circ - (90^\circ - \tfrac{a}{2} + \tfrac{b}{2}) = 90^\circ + \tfrac{a}{2} - \tfrac{b}{2}$, we then have  which is indeed the measure of $\angle{BAR}$. This implies that $K$ lies on the bisector of $\angle{BAC}$, and from this, it is clear that $K$ must lie on the interior of segment $BC$. Not proving that $K$ had to lie in the interior of $BC$ was a reason that a large portion of students who submitted a solution received a 1-point deduction.


Six points are chosen on the sides of an equilateral triangle $ABC$: $A_1, A_2$ on $BC$, $B_1$, $B_2$ on $CA$ and $C_1$, $C_2$ on $AB$, such that they are the vertices of a convex hexagon $A_1A_2B_1B_2C_1C_2$ with equal side lengths. Prove that the lines $A_1B_2, B_1C_2$ and $C_1A_2$ are concurrent.


Let $ABC$ be triangle with incenter $I$. A point $P$ in the interior of the triangle satisfies $\angle PBA+\angle PCA = \angle PBC+\angle PCB$. Show that $AP \geq AI$, and that equality holds if and only if $P=I.$

Solution:
We have
and similarly
Since $\angle PBA + \angle PCA = \angle PBC + \angle PCB$, we have $\angle PCB - \angle PCA = \angle PBA - \angle PBC.$
It follows that  Hence, $B,P,I,$ and $C$ are concyclic.
Let ray $AI$ meet the circumcircle of $\triangle  ABC\,$ at point $J$. Then, by the Incenter-Excenter Lemma, $JB=JC=JI=JP$.
Finally, $AP+JP \geq AJ = AI+IJ$ (since triangle APJ can be degenerate, which happens only when $P=I$), but $JI=JP$; hence $AP \geq AI$ and we are done.
By Mengsay LOEM  , Cambodia IMO Team 2015
latexed by tluo5458 :)
minor edits by lpieleanu


Real numbers $a_1, a_2, \dots , a_n$ are given. For each $i$ ($1\le i\le n$) define

and let
.
(a) Prove that, for any real numbers $x_1\le x_2\le \cdots\le x_n$,

(b) Show that there are real numbers $x_1\le x_2\le x_n$ such that equality holds in (*)

Solution:
Since $d_i=\max\{a_j:1\le j\le i\}-\min\{a_j:i\le j\le n\}$, all $d_i$ can be expressed as $a_p-a_q$, where $1\le p\le i\le q \le n$.
Thus, $d$ can be expressed as $a_p-a_q$ for some $p$ and $q$, $1\le p\le q\le n$

Lemma)  $d\ge 0$
Assume for contradiction that $d<0$, then for all $i$, $a_i \le \max\{a_j:1\le j\le i\}\le \min\{a_j:i\le j\le n\}\le a_{i+1}$
$a_i\le a_{i+1}$
Then, ${a_i}$ is a non-decreasing function, which means, $\max\{a_j:1\le j\le i\}=a_i$, and $\min\{a_j:i\le j\le n\}\le a_{i+1}=a_i$, which means, ${d_i}={0}$.
Then, $d=0$ and contradiction.

a)
Case 1) $d=0$
If $d=0$, $\max\{|x_i-a_i|:1\le i\le n\}$ is the maximum of a set of non-negative number, which must be at least $0$.

Case 2) $d>0$ (We can ignore $d<0$ because of lemma)
Using the fact that $d$ can be expressed as $a_p-a_q$ for some $p$ and $q$, $1\le p\le q\le n$. $x_p\le x_q$
Assume for contradiction that $\max\{|x_i-a_i|:1\le i\le n\}<\dfrac{d}{2}$.
Then, $\forall x_i$, $|x_i-a_i|<\dfrac{d}{2}$.
$|x_p-a_p|<\dfrac{d}{2}$, and $|x_q-a_q|<\dfrac{d}{2}$
Thus, $x_p>a_p-\dfrac{d}{2}$ and $x_q<a_q+\dfrac{d}{2}$.
Subtracting the two inequality, we will obtain:

$x_p>x_q$ --- contradiction ($p\le q \rightarrow x_p\le x_q$).
Thus, $\max\{|x_i-a_i|:1\le i\le n\}\ge\dfrac{d}{2}$

(b)
A set of ${x_i}$ where the equality in (*) holds is:

Since $\max\{a_j:1\le j\le i\}$ is a non-decreasing function, $x_i$ is non-decreasing.

$\forall x_i$ :
Let $a_m=\max\{a_j:1\le j\le i\}$, $a_m-a_i<a_m-\min\{a_j:i\le j\le n\}=d_i$.
Thus, $0\le a_m-a_i \le d$ ($0\le a_m-a_i$ because $a_m$ is the max of a set including $a_i$)

$|x_i-a_i|=\left|a_m-\dfrac{d}{2}-a_i\right|=\left|(a_m-a_i)\dfrac{d}{2}\right|$
$0\le a_m-a_i\le d$
$-\dfrac{d}{2} \le (a_m-a_i)\dfrac{d}{2} \le \dfrac{d}{2}$
$\left|(a_m-a_i)-\dfrac{d}{2}\right|=|x_i-a_i|\le \frac{d}{2}$

Since $\max\{|x_i-a_i|:1\le i\le n\}\ge\dfrac{d}{2}$ and $|x_i-a_i|\le \frac{d}{2}$ $\forall x_i$, $\max\{|x_i-a_i|:1\le i\le n\}=\dfrac{d}{2}$

This is written by Mo Lam--- who is a horrible proof writer, so please fix the proof for me. Thank you. O, also the formatting.
-->
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


An acute-angled triangle $ABC$ has orthocentre $H$. The circle passing through $H$ with centre the midpoint of $BC$ intersects the line $BC$ at $A_1$ and $A_2$. Similarly, the circle passing through $H$ with centre the midpoint of $CA$ intersects the line $CA$ at $B_1$ and $B_2$, and the circle passing through $H$ with centre the midpoint of $AB$ intersects the line $AB$ at $C_1$ and $C_2$. Show that $A_1$, $A_2$, $B_1$, $B_2$, $C_1$, $C_2$ lie on a circle.

Solution: Let $M_A$, $M_B$, and $M_C$ be the midpoints of sides $BC$, $CA$, and $AB$, respectively. It's not hard to see that $M_BM_C\parallel BC$. We also have that $AH\perp BC$, so $AH \perp M_BM_C$. Now note that the radical axis of two circles is perpendicular to the line connecting their centers. We know that $H$ is on the radical axis of the circles centered at $M_B$ and $M_C$, so $A$ is too. We then have $AC_1\cdot AC_2=AB_2\cdot AB_1\Rightarrow \frac{AB_2}{AC_1}=\frac{AC_2}{AB_1}$. This implies that $\triangle AB_2C_1\sim \triangle AC_2B_1$, so $\angle AB_2C_1=\angle AC_2B_1$. Therefore $\angle C_1B_2B_1=180^{\circ}-\angle AB_2C_1=180^{\circ}-\angle AC_2B_1$. This shows that quadrilateral $C_1C_2B_1B_2$ is cyclic. Note that the center of its circumcircle is at the intersection of the perpendicular bisectors of the segments $C_1C_2$ and $B_1B_2$. However, these are just the perpendicular bisectors of $AB$ and $CA$, which meet at the circumcenter of $ABC$, so the circumcenter of $C_1C_2B_1B_2$ is the circumcenter of triangle $ABC$. Similarly, the circumcenters of $A_1A_2B_1B_2$ and $C_1C_2A_1A_2$ are coincident with the circumcenter of $ABC$. The desired result follows.


Let $n$ be a positive integer and let $a_1,\ldots,a_k (k\ge2)$ be distinct integers in the set $\{1,\ldots,n\}$ such that $n$ divides $a_i(a_{i+1}-1)$ for $i=1,\ldots,k-1$. Prove that $n$ doesn't divide $a_k(a_1-1)$.
Author: Ross Atkins, Australia

Solution:
Let $n=pq$ such that $p\mid a_1$ and $q\mid a_2-1$. Suppose $n$ divides $a_k(a_1-1)$.
Note $q\mid a_2-1$ implies $(q,a_2)=1$ and hence $q\mid a_3-1$. Similarly one has $q\mid a_i-1$ for all $i$'s, in particular, $p\mid a_1$ and $q\mid a_1-1$ force $(p,q)=1$. Now $(p,a_1-1)=1$ gives $p\mid a_k$, similarly one has $p\mid a_i$ for all $i$'s, that is $a_i$'s satisfy $p\mid a_i$ and $q\mid a_i-1$, but there should be at most one such integer satisfies them within the range of $1,2,\ldots,n$ for $n=pq$ and $(p,q)=1$. A contradiction!!!

Let $n = p_1^{b_1}p_2^{b_2} \cdots p_s^{b_s}$. Then after toying around with the $p_i^{b_i}$ and what they divide, we have that $p_i^{b_i} \nmid a_k$, and so in particular, $n \nmid a_k$.
Assume by way of contradiction that $n \mid a_k(a_1 - 1)$. Then $n \mid a_1 - 1$. Now we shift our view towards the $a_i(a_{i + 1} - 1)$. Here each $p_i^{b_i}$ divides $a_i(a_{i + 1} - 1) \implies a_ia_{i + 1} \equiv a_i \pmod{p_i^{b_i}}$. Hence we have the chain of equivalences $a_1a_2 \equiv a_1 \pmod{p_i^{b_i}}, a_2a_3 \equiv a_2 \pmod{p_i^{b_i}}, \dots, a_{k - 1}a_k \equiv a_{k - 1} \pmod {p_i^{b_i}}$. Now we also have that $p_i^{b_i} \mid n \mid a_1 - 1$. Thus $a_1 \equiv 1 \pmod{p_i^{b_i}}$. Now plugging this value of $a_1$ modulo $p_i^{b_i}$, we obtain that $a_1 \equiv a_2 \equiv a_3 \equiv \cdots a_k \equiv 1 \pmod{p_i^{b_i}}$. Hence this chain of congruences is also true for $n$ as $p_i$ was arbitrary. However as all the $a_i \in \{1, 2, \dots, n\}$ we have that not all the $a_i$ are distinct, and so this is a contradiction.


Find all function $f:\mathbb{R}\rightarrow\mathbb{R}$ such that for all $x,y\in\mathbb{R}$ the following equality holds
$f(\left\lfloor x\right\rfloor y)=f(x)\left\lfloor f(y)\right\rfloor$
where $\left\lfloor a\right\rfloor$ is greatest integer not greater than $a.$
Author: Pierre Bornsztein, France

Put $x=y=0$. Then $f(0)=0$ or $\lfloor f(0) \rfloor=1$.
$\bullet$ If $\lfloor f(0) \rfloor=1$, putting $y=0$ we get $f(x)=f(0)$, that is f is constant.
Substituing in the original equation we find $f(x)=0, \ \forall x \in \mathbb{R}$ or $f(x)=a, \ \forall x \in \mathbb{R}$, where $a \in [1,2)$.
$\bullet$ If $f(0)=0$, putting $x=y=1$ we get $f(1)=0$ or $\lfloor f(1) \rfloor=1$.
For $f(1)=0$, we set $x=1$ to find $f(y)=0 \ \forall y$, which is a solution.
For $\lfloor f(1) \rfloor=1$, setting $y=1$ yields $f(\lfloor x \rfloor)=f(x), \ (*)$.
Putting $x=2, y=\frac{1}{2}$ to the original we get $f(1)=f(2)\lfloor f(\frac{1}{2}) \rfloor$.
However, from $(*)$ we have $f(\frac{1}{2})=f(0)=0$, so $f(1)=0$ which contradicts the fact $\lfloor f(1) \rfloor=1$.
So, $f(x)=0, \ \forall x$ or $f(x)=a, \ \forall x, \ a \in [1,2)$. ( By socrates[1])

Substituting $y=0$ we have    $f(0) = f(x) [f(0)]$.
If $[f0)] \ne 0$ then $f(x) = \frac{f(0)}{[f(0)]}$. Then $f(x)$ is constant. Let $f(x)=c$. Then substituting that in (1) we have $c=c[c] \Rightarrow c(1-[c])=0 \Rightarrow c=0$, or $[c]=1$. Therefore $f(x)=c$ where $c=0$ or $c \in [1,2)$
If $[f(0)] = 0$ then $f(0)=0$.
Now substituting $x=1$ we have   $f(y)=f(1)[f(y)]$.
If $f(1) \ne 0$ then $[f(y)] = \frac{f(y)}{f(1)}$  and substituting this in (1) we have   $f([x]y)=\frac{f(x)f(y)}{f(1)}$.
Then $f([x]y)=f(x[y])$.
Substituting $x=1/2, y=2$ we get $f(0)=f(1)$. Then $f(1)=0$, which is a contradiction
Therefore $f(1)=0$. and then $f(y)=0$ for all $R$
Then the only solutions are $f(x)=0$ or $f(x)=c$ where $c \in [1,2)$.( By m.candales [2])

Let $y=0$, then $f(0)=f(x)\left\lfloor f(0)\right\rfloor$.
Case 1: $\left\lfloor f(0)\right\rfloor\neq 0$
Then $f(x)=\frac{f(0)}{\left\lfloor f(0)\right\rfloor}$ is a constant. Let $f(x)=k$, then $k=k\left\lfloor k \right\rfloor \Leftrightarrow k=0 \vee 1\leq k<2$. It is easy to check that this are solutions.
Case 2: $\left\lfloor f(0)\right\rfloor= 0$
In this case we conclude that $\left\lfloor f(0)\right\rfloor= 0\Rightarrow f(0)=0$
Lemma:If $y$ is such that $0\leq f(y)<1$, $f(y)=0$
Proof of the Lemma: If $x=1$ we have that $f(\left\lfloor x\right\rfloor y)=f(y)=f(x)\left\lfloor f(y)\right\rfloor =0$, as desired.
Let $0\leq x<1$, so that we have:
$0=f(0)=f(\left\lfloor x\right\rfloor y)=f(x)\left\lfloor f(y)\right\rfloor\Rightarrow$
$\Rightarrow f(x)=0 \vee 0\leq f(y)<1 \Rightarrow f(x)=0 \vee f(y)=0$, using the lemma.
If $f$ is not constant and equal to $0$, letting $y$ be such that $f(y)\neq 0$ implies that $f(x)=0, \forall 0\leq x<1$.
Now it's enough to notice that any real number $x$ is equal to $ky$, where $k\in \mathbb{Z}$ and $0\leq y< 1$, so that $f(x)=f(ky)=f(\left\lfloor k\right\rfloor y)=f(k)\left\lfloor f(y)\right\rfloor=0$. Since $x$ was arbitrary, we have that $f$ is constant and equal to $0$.
We conclude that the solutions are $f(x)=k$, where $k=0 \vee 1\leq k<2$.( By Jorge Miranda [3]
)

Clearly $f(\left\lfloor x\right\rfloor y) = f(\left\lfloor \lfloor x \rfloor \right\rfloor y) = f(\lfloor x \rfloor)\left\lfloor f(y)\right\rfloor$, so $(f(x) - f(\lfloor x \rfloor))\left\lfloor f(y)\right\rfloor = 0$ for all $x,y\in\mathbb{R}$.
If $\left\lfloor f(y)\right\rfloor = 0$ for all $y \in \mathbb{R}$, then by taking $x=1$ we get $f(y)=f(1)\left\lfloor f(y)\right\rfloor = 0$, so $f$ is identically null (which checks).
If, contrariwise, $\left\lfloor f(y_0)\right\rfloor \neq 0$ for some $y_0 \in \mathbb{R}$, it follows $f(x) = f(\lfloor x \rfloor)$ for all $x \in \mathbb{R}$.
Now it immediately follows $f(x) = f(\lfloor x \rfloor  \cdot 1) = f(x)\lfloor f(1) \rfloor$, hence $f(x)(1 - \lfloor f(1) \rfloor) = 0$.
For $x=y_0$ this implies $\lfloor f(1) \rfloor = 1$.
Assume $\lfloor f(0) \rfloor=0$; then $1 \leq f(1) = f\left ( 2\cdot \dfrac {1} {2} \right ) = f(2)\left \lfloor f \left ( \dfrac {1} {2} \right ) \right \rfloor = f(2)\left \lfloor f \left ( \left \lfloor \dfrac {1} {2} \right \rfloor \right ) \right \rfloor = f(2)\left \lfloor f(0) \right \rfloor = 0$, absurd.
Therefore $\lfloor f(0) \rfloor \neq 0$, and now $y=0$ in the given functional equation yields $f(0) = f(x)\lfloor f(0) \rfloor$ for all $x \in \mathbb{R}$, therefore $f(x) = c \neq 0$ constant, with $\lfloor c \rfloor = \lfloor f(1) \rfloor = 1$, i.e. $c \in [1,2)$ (which obviously checks).( By mavropnevma [4])


Given any set $A = \{a_1, a_2, a_3, a_4\}$ of four distinct positive integers, we denote the sum $a_1 +a_2 +a_3 +a_4$ by $s_A$. Let $n_A$ denote the number of pairs $(i, j)$ with $1 \leq  i < j \leq 4$ for which $a_i +a_j$ divides $s_A$. Find all sets $A$ of four distinct positive integers which achieve the largest possible value of $n_A$.
Author: Fernando Campos, Mexico

Firstly, if we order $a_1 \ge a_2 \ge a_3 \ge a_4$, we see $2(a_3 + a_4) \ge (a_1+a_2)+(a_3+a_4)  = s_A \geq 0$, so $(a_3, a_4)$ isn't a couple that satisfies the conditions of the problem. Also, $2(a_4 + a_2) = (a_4 + a_4) + (a_2 + a_2) \ge (a_4+a_3)+(a_2+a_1) = s_A \ge 0$, so again $(a_2, a_4)$ isn't a good couple. We have in total 6 couples. So $n_A \leq 6-2=4$.
We now find all sets $A$ with $n_A = 4$. If $(a,b)$ and $(c,d)$ are both good couples, and $A=\{a, b, c, d\}$, we have $a+b=c+d=s_A/2$.
So WLOG $A=\{a,b,a+x,b-x\}$ with $x > 0$ and $a < b, b-x, a+x$. It's easy to see $a=a_1$ and since $(a_2, a_4),(a_3,a_4)$ are bad, all couples containing $a$ must be good. Obviously $(a,b)$ and $(a+x,b-x)$ are good ($s_A=2(a+b)$). So we have $2a+x | 2a+2b$ and $a+b-x|2a+2b \Rightarrow a+b-x|2x$.
Using the second equation, we see that if $y=a+b$, $y-x|2x \Rightarrow yk_1-xk_1=2x \Rightarrow yk_1 = x(2+k_1) \Rightarrow y=x((2+k_1)/k_1)$, for some $k_1$ a positive integer.
So now we use the first equation to get $2ak_2 + xk_2 = 2y = 2x(2+k_1)/k_1 \Rightarrow 2ak_2 = x(\frac{4+2k_1}{k_1}-k_2) \Rightarrow 2a=x(\frac{4+2k_1}{k_1k_2} - 1)$, for a natural $k_2$.
Finally, we obtain $k_1 | 4+2k-1 \Rightarrow k_1 | 4  \Rightarrow k_1=$ 1, 2 or 4. We divide in cases:
CASE I: $k_1=1$.
So $y=3x$ and $2a=x((\frac{6}{k_2}) -1)$. But $a < b-x \Rightarrow 2a < y-x=2x \Rightarrow (6/k_2) - 1 < 2 \Rightarrow k_2 > 2 \Rightarrow k_2 =$3, 4,5 or 6. $k_2=6$ implies $a=0$, impossible. $a=x$ when $k_2=3$. We easily  see $b=3x=3x$ and $A=\{x, 3x, 3x-x, 2x\}$, impossible since $3x-x=2x$. When $k_2=4$, $a=x/4=y/12$, and we get  $\{11a, a, 5a, 7a\}$.Uf $k_2=5$, $a=x/5=y/15$ and we get $\{a, 14a, 6a, 9a\}$.
CASE II and III:$k_1=$2, 4. Left to the reader.
ANSWER: $\{11a, a, 5a, 7a\}$,$\{a, 11a, 19a, 29a\}$, for any positive integer $a$.
(Note: The above solution looks generally correct, but the actual answer should be $\{11a, a, 5a, 7a\}$,$\{a, 11a, 19a, 29a\}$. You can check that $\{a, 14a, 6a, 9a\}$ doesn't actually work. -Someone who didn't write up the above solution but solved the problem in a similar way)

Similarly to the first solution, let us order the terms in set $A$ by $0 < a_1 < a_2 < a_3 < a_4$ since it is given that these four integers must be distinct and positive. Obviously, $s_a > 0$ from this. We know that pair $(a_3, a_4)$ cannot work because $2(a_3 + a_4) > a_1 + a_2 + a_3 + a_4 = s_A.$ Additionally, pair $(a_2, a_4)$ cannot work for the same reason: $2(a_2 + a_4) = a_4 + a_4 + a_2 + a_2 > s_A.$
Hence, since there were only ${4 \choose 2} = 6$ pairs $(i, j)$ in total, and two pairs are guaranteed not to work, we are to find sets $A$ satisfying $n_A = 6 - 2 = 4.$ Due to our making $a_4$ the largest term of set $A$, the only way to have a pair $(a_i, a_4)$ that exists such that $a_i + a_4 | s_A$ is to make $i$ equal to 1 and find an $a_1$ such that $\frac{s_A}{a_1 + a_4} = 2.$ When this happens, we know that $\frac{s_A}{a_2 + a_3} = 2$, as well. It clearly follows that we need pairs $(a_1, a_2)$ and $(a_1, a_3)$ that exist such that both $a_1 + a_2$ and $a_1 + a_3$ divide $s_A.$
To satisfy conditions $\frac{s_A}{a_1 + a_4} = 2$ and $\frac{s_A}{a_2 + a_3} = 2$, choose a set $A$ with four distinct positive integer elements $a - x, a, b, b + x$ with $0 < a - x < a < b < b + x.$ Obviously, $x < a < b$ for our set to consist solely of positive integers. The problem becomes to find $x, a,$ and $b$ such that $2a - x | 2(a + b)$ and $(a + b) - x | 2a + 2b.$
We realize that $x$ can be any positive even integer. This allows $2a - x$ and $2(a + b)$ to have a common factor of 2, simplifying our problem a bit. Hence, $a - \frac{x}{2}$ must divide $(a + b).$ Now, we can look at the other condition, $(a + b) - x | 2a + 2b$, to solve this problem. To find $a, b, x$ satisfying $(a + b) - x | 2a + 2b$, it suffices to define a positive integer $n$ that makes $n(a + b - x) = 2(a + b) \Rightarrow 0 = (n - 2)a + (n - 2)b - nx \Rightarrow (n - 2)(a + b) = nx.$ Note that $x$ must be less than $\frac{a + b}{2}.$ If $x \ge \frac{a + b}{2}$, $(n - 2)(a + b) = nx$ would have solutions $x, a,$ and $b$ that will make $a - x < 0$, since $a < \frac{a + b}{2}$ due to $a < b.$ This is a contradiction with the condition that each element in set $A$ has to be positive. Despite this, We move on to some cases.

Thus, the only possible sets $A$ we have for satisfying the maximum $n_A$, which is 4, are $A = \{p, 5p, 7p, 11p\}$ and $\{p, 11p, 19p, 29p\}$, with $p$ being any positive integer since it is obvious that any $a$ that is a positive multiple of 5 or 11 makes $\frac{a}{5}$ and $\frac{a}{11}$ positive integers, respectively.