A permutation of the set of positive integers $[n] = \{1, 2, \ldots, n\}$ is a sequence $(a_1, a_2, \ldots, a_n)$ such that each element of $[n]$ appears precisely one time as a term of the sequence. For example, $(3, 5, 1, 2, 4)$ is a permutation of $[5]$. Let $P(n)$ be the number of permutations of $[n]$ for which $ka_k$ is a perfect square for all $1\leq k\leq n$. Find with proof the smallest $n$ such that $P(n)$ is a multiple of $2010$.

We claim that the smallest $n$ is $67^2 = \boxed{4489}$.

Let $S = \{1, 4, 9, \ldots\}$ be the set of positive perfect squares. We claim that the relation $R = \{(j, k)\in [n]\times[n]\mid jk\in S\}$ is an equivalence relation on $[n]$.
We are restricted to permutations for which $ka_k \in S$, in other words to permutations that send each element of $[n]$ into its equivalence class. Suppose there are $N$ equivalence classes: $C_1, \ldots, C_N$. Let $n_i$ be the number of elements of $C_i$, then $P(n) = \prod_{i=1}^{N} n_i!$.
Now $2010 = 2\cdot 3\cdot 5\cdot 67$. In order that $2010\mid P(n)$, we must have $67\mid n_m!$ for the class $C_m$ with the most elements. This means $n_m\geq 67$, since no smaller factorial will have $67$ as a factor. This condition is sufficient, since $n_m!$ will be divisible by $30$ for $n_m\geq 5$, and even more so $n_m\geq 67$.
The smallest element $g_m$ of the equivalence class $C_m$ is square-free, since if it were divisible by the square of a prime, the quotient would be a smaller element of $C_m$. Also, each prime $p$ that divides $g_m$ divides all the other elements $k$ of $C_m$, since $p^2\mid kg_m$ and thus $p\mid k$. Therefore $g_m\mid k$ for all $k\in C_m$. The primes that are not in $g_m$ occur an even number of times in each $k\in C_m$.
Thus the equivalence class $C_m = \{g_mk^2\leq n\}$. With $g_m = 1$, we get the largest possible $n_m$. This is just the set of squares in $[n]$, of which we need at least $67$, so $n\geq 67^2$. This condition is necessary and sufficient.

This proof can also be rephrased as follows, in a longer way, but with fewer highly technical words such as "equivalence relation":
It is possible to write all positive integers $n$ in the form $p\cdot m^2$, where $m^2$ is the largest perfect square dividing $n$, so $p$ is not divisible by the square of any prime. Obviously, one working permutation of $[n]$ is simply $(1, 2, \ldots, n)$; this is acceptable, as $ka_k$ is always $k^2$ in this sequence.
Lemma 1. We can permute any numbers that, when each divided by the largest perfect square that divides it, yield equal quantities $p$.
Proof. Let $p_k$ and $m_k$ be the values of $p$ and $m$, respectively, for a given $k$ as defined above, such that $p$ is not divisible by the square of any prime. We can obviously permute two numbers which have the same $p$, since if $p_j = p_w$ where $j$ and $w$ are 2 values of $k$, then $j\cdot w = p_j^2\cdot m_j^2\cdot m_w^2$, which is a perfect square. This proves that we can permute any numbers with the same value of $p$.
End Lemma
Lemma 2. We will prove the converse of Lemma 1: Let one number have a $p$ value of $\phi$ and another, $\gamma$. $\phi\cdot f$ and $\gamma\cdot g$ are both perfect squares.
Proof. $\phi\cdot f$ and $\gamma\cdot g$ are both perfect squares, so for $\phi\cdot \gamma$ to be a perfect square, if $g$ is greater than or equal to $f$, $g/f$ must be a perfect square, too. Thus $g$ is $f$ times a square, but $g$ cannot divide any squares besides $1$, so $g = 1f$; $g = f$. Similarly, if $f\geq g$, then $f = g$ for our rules to keep working.
End Lemma
We can permute $l$ numbers with the same $p$ in $l!$ ways. We must have at least 67 numbers with a certain $p$ so our product will be divisible by 67. Obviously, then it will also be divisible by 2, 3, and 5, and thus 2010, as well. Toms as $h$, in general, we need numbers all the way up to $h\cdot 67^2$, so obviously, $67^2$ is the smallest such number such that we can get a $67!$ term; here 67 $p$ terms are 1. Thus we need the integers $1, 2, \ldots, 67^2$, so $67^2$, or $\boxed{4489}$, is the answer.

We claim the smallest $n$ is $67^2 = \boxed{4489}$
Looking at small cases we see that $P(n)$ changes every time n increases to a perfect square. We find that we can not permute the non squares around because $n$ (not a perfect square) $*a_w$ where $w \neq n$ will not give a perfect square. But we can permute the perfect squares around to other perfect squares since a square times a square makes another square we can do this (# of squares below $n$)! times. So now we need to find $n = a^2$ such that $a!$ is divisible by $2010$ which largest prime factor is $67$ so, $n$ is $n$ is $67^2 = \boxed{4489}$
~bjump

We have to somehow calculate the number of permutations for a given $n$. How in the world do we do this? Because we want squares, why not call a number $k=m*s^2$, where $s$ is the largest square that allows $m$ to be non-square?  $m=1$ is the only square $m$ can be, which only happens if $k$ is a perfect square.
For example, $126 = 14 * 3^2$, therefore in this case $k=126, m = 14, s = 3$.
I will call a permutation of the numbers $P$, while the original $1, 2, 3, 4, ...$ I will call $S$.
Note that essentially we are looking at "pairing up" elements between $P$ and $S$ such that the product of $P_k$ and $S_k$ is a perfect square. How do we do this? Using the representation above.
Each square has to have an even exponent of every prime represented in its prime factorization. Therefore, we can just take all exponents of the primes $mod 2$ and if there are any odd numbers, those are the ones we have to match- in effect, they are the $m$ numbers mentioned at the beginning.
By listing the $m$ values, in my search for "dumb" or "obvious" ideas I am pretty confident that only values with identical $m$s can be matched together. With such a solid idea let me prove it.
If we were to "pair up" numbers with different $m$s, take for example $S_{18}$ with an $m$ of $2$ and $P_{18}=26$ with an $m$ of $26$, note that their product gives a supposed $m$ of $13$ because the $2$ values cancel out. But then, what happens to the extra $13$ left? It doesn't make a square, contradiction. To finish up this easy proof, note that if a "pair" has different $m$ values, and the smaller one is $m_1$, in order for the product to leave a square, the larger $m$ value has to have not just $m_1$ but another square inside it, which is absurd because we stipulated at the beginning that $m$ was square-free except for the trivial multiplication identity, 1.
Now, how many ways are there to do this? If there are $c_1$ numbers with $m=1$, there are clearly $(c_1)!$ ways of sorting them. The same goes for $m=2, 3, etc.$ by this logic. Note that the $P(n)$ as stated by the problem requires a $67$ thrown in there because $2010=2*3*5*67$, so there has to be a $S_n$ with 67 elements with the same $m$. It is evident that the smallest $n$ will occur when $m=1$, because if $m$ is bigger we would have to expand $n$ to get the same number of $m$ values. Finally, realize that the only numbers with $m=1$ are square numbers! So our smallest $n=67^2=4489$, and we are done.
I relied on looking for patterns a lot in this problem. When faced with combo/number theory, it is always good to draw a sketch. Never be scared to try a problem on the USAJMO. It takes about 45 minutes. Well, it's 2010 and a number 1. Cheers!
-expiLnCalc

It's well known that there exists $f(n)$ and $g(n)$ such that $n = f(n) \cdot g(n)$, no square divides $f(n)$ other than 1, and $g(n)$ is a perfect square.
We prove first: If $f(k) = f(a_k)$, $k \cdot a_k$ is a perfect square.
$k \cdot a_k = f(k) \cdot g(k) \cdot f(a_k) \cdot g(a_k) = f(k)^2 \cdot g(k) \cdot g(a_k)$, which is a perfect square.
We will now prove: If $k \cdot a_k$ is a perfect square, $f(k) = f(a_k)$.
We do proof by contrapositive: If $f(k) \neq f(a_k)$, $k \cdot a_k$ is not a perfect square.
$v_p(k)$ is the p-adic valuation of k. (Basically how many factors of p you can take out of k)
Note that if $f(k) \neq f(a_k)$, By the Fundamental Theorem of Arithmetic, $f(k)$ and $f(a_k)$'s prime factorization are different, and thus there exists a prime p, such that $v_p(f(k)) \neq v_p(f(a_k))$. Also, since $f(k)$ and $f(a_k)$ is squarefree, $v_p(k), v_p(a_k) \leq 1$. Thus, $v_p(k \cdot a_k) = 1$, making $k \cdot a_k$ not a square.
Thus, we can only match k with $a_k$ if they have the same f value. Thus, to find P(k), we can do it by f value, permuting the $a_k$ with f value 1, then 2, ... Thus, our answer is:
$P(n) = \prod_{1 \leq i \leq n, g(i) = 1} \left\lfloor \sqrt{\frac{n}{i}} \right \rfloor !$
For all $n < 67^2$, $P(n)$ doesn't have a factor of 67. However, if $n = 67^2$, the first term will be a multiple of 2010, and thus the answer is $67^2 = \boxed{4489}$
-Alexlikemath
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

The answer is 4489.(67 squared)
Proof
We start with trying to fulfill ways to do $P(n)$. When n is 1 there is one way to do it and fulfill $ka_k$ as a perfect square. Same with the numbers 2 and 3. The order for both of these number are all in increasing order   Now when it comes to 4 we could do  and  This means when n is a perfect square it increases where $k$ and $a_k$ are perfect squares. The prime factorization of 2010 is:  Because we only care about 67, the biggest divisor we do 67 squared because $n$ has to be a square.
-Multpi12


Let $n > 1$ be an integer. Find, with proof, all sequences
$x_1, x_2, \ldots, x_{n-1}$ of positive integers with the following
three properties:

Solution: The sequence is $2, 4, 6, \ldots, 2n-2$.

The claim is that in this sequence, if there are $2$ elements $a,b$ where $a,b<n$, such that $\gcd(a,b)=1$, then the sequence contains every number less than $2n$.
Proof: Let $a$ and $b$ be the numbers less than $n$ such that $\gcd(a,b)=1$.
We take this sequence modulo $n$. This means that if $x_i$ is an element in this sequence then $-x_i$ is as well.
$a,b,2n-a,2n-b$ are all elements in the sequence. Clearly, one of $2n-a+b$ and $2n-b+a$ is less than $2n$, which means that $\pm (a-b)$ are in this sequence modulo $n$.
Now we want to show every number is achievable. We have already established that $a$ and $b$ are relatively prime, so by euclidean algorithm, if we take the positive difference of $a'$ and $b'$ every time, we will get that $1$ is in our sequence. Then, we can simply add or subtract $1$ as many times from $a$ as desired to get every single number.
We have proved that there are no two numbers that can be relatively prime in our sequence, implying that no two consecutive numbers can be in this sequence. Because our sequence has $n-1$ terms, our sequence must be one of $2,4,6,..,2(n-1)$ or $1,3,5,...$, the latter obviously fails, so $2,4,6...2(n-1)$ is our only possible sequence.

We can add $x_1$ to every expression in property (a) to get  Therefore, we have $n-2$ distinct (because all the $x_i$ are distinct) expressions of the form $x_1+x_i$ for $i = 1, 2, \dots n-1$ that are all less than $2n$, which means these $n-2$ expressions are also equal to some $x_k$.
Now, we have that the $x_i$ are all positive, so $x_1>0$. Adding $x_1$ to both sides, $2x_1>x_1$. Therefore, since the $n-2$ expressions are all at least $2x_1$, they have to be equal to $x_2, x_3, \dots, x_{n-1}$.
Since there are $n-2$ distinct expressions $x_1+x_i$ equal to $n-2$ distinct expressions $x_j$, we have that each $x_1+x_i$ is equal to one $x_j$. Using the orders of the $x_1+x_i$ and the $x_j$, we find that

This gives us

Now, we can use property (b) with $i=1$, so $x_1 + x_{n-1} = 2n$, which means $x_1 = 2$. This gives the sequence
-sixeoneeight


Let $AXYZB$ be a convex pentagon inscribed in a semicircle of diameter
$AB$. Denote by $P, Q, R, S$ the feet of the perpendiculars from $Y$ onto
lines $AX, BX, AZ, BZ$, respectively. Prove that the acute angle
formed by lines $PQ$ and $RS$ is half the size of $\angle XOZ$, where
$O$ is the midpoint of segment $AB$.

Let $\alpha = \angle BAZ$, $\beta = \angle ABX$.
Since $XY$ is a chord of the circle with diameter $AB$,
$\angle XAY = \angle XBY = \gamma$. From the chord $YZ$,
we conclude $\angle YAZ = \angle YBZ = \delta$.
Triangles $BQY$ and $APY$ are both right-triangles, and share the
angle $\gamma$, therefore they are similar, and so the ratio $PY : YQ = AY : YB$. Now by Thales' theorem the angles $\angle AXB = \angle AYB = \angle AZB$ are all right-angles. Also, $\angle PYQ$,
being the fourth angle in a quadrilateral with 3 right-angles is
again a right-angle.  Therefore $\triangle PYQ \sim \triangle AYB$ and
$\angle YQP = \angle YBA = \gamma + \beta$.
Similarly, $RY : YS = AY : YB$, and so $\angle YRS = \angle YAB = \alpha + \delta$.
Now $RY$ is perpendicular to $AZ$ so the direction $RY$ is $\alpha$ counterclockwise from the vertical, and since $\angle YRS = \alpha + \delta$ we see that $SR$ is $\delta$ clockwise from the vertical. (Draw an actual vertical line segment if necessary.)
Similarly, $QY$ is perpendicular to $BX$ so the direction $QY$ is $\beta$ clockwise from the vertical, and since $\angle YQP$ is $\gamma + \beta$ we see that $QY$ is $\gamma$ counterclockwise from the vertical.
Therefore the lines $PQ$ and $RS$ intersect at an angle $\chi = \gamma + \delta$. Now by the central angle theorem $2\gamma = \angle XOY$
and $2\delta = \angle YOZ$, and so $2(\gamma + \delta) = \angle XOZ$,
and we are done.
Note that $RTQY$ is a quadrilateral whose angles sum to 360°; can you find a faster approach using this fact?

Let $T$ be the foot of the perpendicular from $Y$ to $\overline{AB}$, let $O$ be the center of the semi-circle.
Since we have a semi-circle, if we were to reflect it over $\overline {AB}$, we would have a full circle, with $\triangle{AXB}$ and $\triangle{AZB}$ inscribed in it. Now, notice that $Y$ is a point on that full circle, so we can say that $T$ lies on the Simson Line $\overline{PQ}$ from $Y$ to $\triangle AXB$ and that it also lies on the Simson line $\overline {RS}$ from $Y$ to $\triangle AZB$. Thus, $T$ lies on two distinct lines in a plane, which means that $T=\overline{PQ}\cap\overline{RS}$. Therefore, it suffices to show that $\angle PTS=\tfrac{1}{2}\angle XOZ$.
Since $m\angle YTA + m\angle YPA = 90^\circ + 90^\circ = 180^\circ$ and $m \angle YTB + m \angle YSB = 90^\circ + 90^\circ = 180^\circ$, we know that $TAPY$ and $TBSY$ are cyclic quadrilaterals.
We use this fact to get  \\
Now note that $\angle XAY$ is the inscribed angle of minor arc $\overset{\huge\frown}{PY}$, and $\angle XOY$ is the central angle of minor arc $\overset{\huge\frown}{AB}$, so $\angle XAY = \frac{\overset{\huge\frown}{PY}}{2} = \frac{\angle XOY}{2}$. Similarly, $\angle YBZ = \frac{\overset{\huge\frown}{YZ}}{2}=\frac{\angle YOZ}{2}$. Thus we can say
Combining statements $(1)$ and $(2)$, we can say that $\angle PTS = \frac{\angle XOZ}{2}$, as desired. $\square$
~thinker123


A triangle is called a parabolic triangle if its vertices lie on a
parabola $y = x^2$. Prove that for every nonnegative integer $n$, there
is an odd number $m$ and a parabolic triangle with vertices at three
distinct points with integer coordinates with area $(2^nm)^2$.

Solution:
Let the vertices of the triangle be $(a, a^2), (b, b^2), (c, c^2)$.
The area of the triangle is the absolute value of $A$ in the equation:
If we choose $a < b < c$, $A > 0$ and gives the actual area. Furthermore,
we clearly see that the area does not change when we subtract the same
constant value from each of $a$, $b$ and $c$. Thus, all possible areas
can be obtained with $a = 0$, in which case $A = \frac{1}{2}bc(c-b)$.
If a particular choice of $b$ and $c$ gives an area $A = (2^nm)^2$,
with $n$ a positive integer and $m$ a positive odd integer, then setting
$b' = 4b$, $c' = 4c$ gives an area $A' = 4^3 A = 8^2 A = (2^{n+3}m)^2$.
Therefore, if we can find solutions for $n = 0$, $n = 1$ and $n = 2$,
all other solutions can be generated by repeated multiplication
of $b$ and $c$ by a factor of $4$.
Setting $b=1$ and $c=2$, we get $A=1 = (2^0\cdot1)^2$, which yields
the $n=0$ case.
Setting $b=1$ and $c=9$, we get $A = 9\cdot4 = (2^1\cdot3)^2$, which yields
the $n=1$ case.
Setting $b=1$ and $c=5$, we get $A=1\cdot2\cdot5 = 10$. Multiplying these
values of $b$ and $c$ by $10$, we get $b'=10$, $c'=50$,
$A'=10\cdot20\cdot50 = 100^2 = (2^2\cdot5^2)^2$,
which yields the $n=2$ case. This completes the construction.

We proceed via induction on n. Notice that we prove instead a stronger result: there exists a parabolic triangle with area $(2^nm)^2$ with two of the vertices sharing the same y-coordinate.
BASE CASE:
If $n = 0$, consider the parabolic triangle $ABC$ with $A(0, 0), B(1, 1), C(-1, 1)$ that has area $1/2 \cdot 1 \cdot 2 = 1$, so that $n = 0$ and $m = 1$.
If $n = 1$, let $ABC = A(5, 25), B(4, 16), C(-4, 16)$. Because $ABC$ has area $1/2 \cdot 8 \cdot 9 = 36$, we set $n = 1$ and $m = 3$.
If $n = 2$, consider the triangle formed by $A(21, 441), B(3, 9), C(-3, 9)$. It is parabolic and has area $1/2 \cdot 6 \cdot 432 = 1296 = 36^2$, so $n = 2$ and $m = 9$.
INDUCTIVE STEP:
If $n = k$ produces parabolic triangle $ABC$ with $A(a, a^2), B(b, b^2),$ and $C(-b, b^2)$, consider $A$'$B$'$C$' with vertices $A(4a, 16a^2)$, $B(4b, 16b^2)$, and $C(-4b, 16b^2)$. If $ABC$ has area $(2^km)^2$, then $A$'$B$'$C$' has area $(2^{k+3}m)^2$, which is easily verified using the $1/2 \cdot\text{base} \cdot \text{height}$ formula for triangle area. This completes the inductive step for $k \implies k+3$.
Hence, for every nonnegative integer $n$, there exists an odd $m$ and a parabolic triangle with area $(2^nm)^2$ with two vertices sharing the same ordinate. The problem statement is a direct result of this result.         -MathGenius_

First, consider triangle with vertices $(0,0)$, $(1,1)$, $(-1,1)$. This has area $1$ so $n=0$ case is satisfied.
Then, consider triangle with vertices $(a,a^2), (-a,a^2), (b,b^2)$, and set $a=2^{2n}$ and $b=2^{4n-2}+1$.
The area of this triangle is $\frac{1}{2} \cdot base \cdot height=a(b^2-a^2)$.
We have that $b^2-a^2=2^{8n-4}+2^{4n-1}+1-2^{4n}=2^{8n-4}-2^{4n-1}+1=(2^{4n-2}-1)^2$
We desire $A=a(b^2-a^2)=2^{2n}m^2$, or $2^{4n-2}-1=m$, and $m$ is clearly always odd for positive $n$, completing the proof.

We simply need to provide an example for all $n$ that satisfies the condition, and we do so.
Let $a = 2^{2n+1}+1$. Then consider the triangle with coordinates $(0,0), (a,a^2), (a^2,a^4) = (x_1, y_1), (x_2, y_2), (x_3, y_3)$.
By the shoelace formula, this triangle has area which clearly can be written in the form $(2^n \times m)^2 = 2^{2n} \times m^2$, where $m^2 = (2^{2n+1}+1)^4$ or $m=(2^{2n+1}+1)^2$. Now, we just have to prove that $(2^{2n+1}+1)^2$ is always odd. This is true because $2^{2n+1}$ is even (because it's a power of $2$), so $2^{2n+1}+1$ is odd, and since an odd number squared is odd, the whole thing is odd as well. And we are done, since we have proved that for all $n$, we can show that there exists such a triangle by merely providing an example. $\square$
~thinker123


Two permutations $a_1, a_2, \ldots, a_{2010}$ and
$b_1, b_2, \ldots, b_{2010}$ of the numbers $1, 2, \ldots, 2010$
are said to intersect if $a_k = b_k$ for some value of $k$ in the
range $1 \le k\le 2010$.  Show that there exist $1006$ permutations
of the numbers $1, 2, \ldots, 2010$ such that any other such
permutation is guaranteed to intersect at least one of these $1006$
permutations.

Let $n$ be a positive integer. Let $m$ be the smallest positive integer with
$m > n - m$.  Since $n > n - n = 0$, $m \le n$. Let $N = \{1, \ldots, n\}$
be the set of positive integers from $1$ to $n$.  Let $M \subset N$,
be $M = \{1, \ldots, m\}$.
Let $P_n$ be the set of of permutations of $N$.
Let $C_m$ be the set of cyclic permutations of $M$, there are $m$
cyclic permutations in all, and $C_m$ acts transitively on $M$, i.e.
for every pair of elements $a,b \in M$, there is an element of $C_m$
that maps $a$ to $b$.
Let $C'_m \subset P_n$ be the permutations in $P_n$ that leave $N\setminus M$
fixed, and restricted to $M$ yield one of the permutations in $C_m$.
There is a natural one-to-one correspondence between $C'_m$ and $C_m$.
We claim that the $m$ permutations $C'_m$ intersect every permutation in
$P_n$.
Suppose, to the contrary, that there exists a permutation $p \in P_n$
that does not intersect any permutation in $C'_m$. Since $C'_m$ acts
transitively on $M \subset N$ the permutation $p$ cannot send any element of
$M$ to any other element of $M$, therefore it must send all the
elements of $M$ to $N\setminus M$, but since $N\setminus M$ has $n - m$ elements and $m > n - m$, this is impossible
by the pigeonhole principle. Therefore such a permutation cannot
exist, and the permutations in $C'_m$ intersect every permutation in
$P_n$.
For $n = 2010$ we get $m = 1006$, which is the required special
case of the general result above.

I construct the following permutations by continuously rotating the first 1006 numbers):
(1, 2, 3 ... 1005, 1006, 1007 ... 2009, 2010)
(2, 3, 4 ... 1006, 1, 1007 ... 2009, 2010)
...
...
...
(1006, 1, 2 ... 1005, 1007, ... 2009, 2010)

I claim that these permutations above satisfy the property that any other permutation will intersect with at least one of them.
Proof:
Assume for the sake of contradiction that there exists a permutation that won't intersect with these, say $(a_1, a_2, a_3 ... a_{2010})$.
Lemma:
If there exists a k such that $1 \leq k \leq 1006$ $a_k \leq 1006$, we will get an intersection with the permutations.
Note that for any 2 distinct permutations in our list, the numbers in kth index must be different, since each permutation is a rotation of an previous permutation. Also, the numbers can't exceed 1006, so, each number must occur exactly once in the kth index.
End Lemma
Using the lemma, in order to avoid intersections, we need $1007 \leq a_k \leq 2010$, for all $1 \leq k \leq 1006$.
But, there are 1004 numbers such that $1007 \leq n \leq 2010$, but we need to have 1004 numbers to fill in 1006 spots, and thus, by pigeonhole principle(the numbers are the holes, the spots are the pigeons), there must be 2 spots that have the same number! However, in a permutation, all numbers must be distinct, so we have a contradiction.
So, we have shown such a set of permutations exists satisfying that any permutation is guaranteed to intersect one of them, and the proof is complete. $\blacksquare$
-Alexlikemath


Let $ABC$ be a triangle with $\angle A = 90^{\circ}$. Points $D$
and $E$ lie on sides $AC$ and $AB$, respectively, such that $\angle ABD = \angle DBC$ and $\angle ACE = \angle ECB$. Segments $BD$ and
$CE$ meet at $I$.  Determine whether or not it is possible for
segments $AB, AC, BI, ID, CI, IE$ to all have integer lengths.

Solution:
We know that angle $BIC = 135^{\circ}$, as the other two angles in triangle $BIC$ add to $45^{\circ}$. Assume that only $AB, AC, BI$, and $CI$ are integers. Using the Law of Cosines on triangle BIC,
$BC^2 = BI^2 + CI^2 - 2BI\cdot CI \cdot \cos 135^{\circ}$. Observing that $BC^2 = AB^2 + AC^2$ is an integer and that $\cos 135^{\circ} = -\frac{\sqrt{2}}{2},$ we have
and therefore,
The LHS ($\sqrt{2}$) is irrational, while the RHS is the quotient of the division of two integers and thus is rational. Clearly, there is a contradiction. Therefore, it is impossible for $AB, AC, BI$, and $CI$ to all be integers, which invalidates the original claim that all six lengths are integers, and we are done.

The answer is no.
Suppose otherwise. It is easy to see (through simple angle chasing) that $\angle DIC=45^{\circ}$. Also, since $I$ is the incenter, we have $\angle IAC = 45^{\circ}$. Using the Law of Cosines, we have  so that $CD$ is irrational. But $\triangle IAC \sim \triangle DIC$, thus $IC^2=CD\cdot AC$, implying that $CD$ is rational, contradiction. $\blacksquare$

The result can be also proved without direct appeal to trigonometry,
via just the angle bisector theorem and the structure of Pythagorean
triples. (This is a lot more work).
A triangle in which all the required lengths are integers exists if and
only if there exists a triangle in which $AB$ and $AC$ are
relatively-prime integers and the lengths of the segments $BI, ID, CI, IE$ are all rational
(we divide all the lengths by the $\gcd(AB, AC)$ or
conversely multiply all the lengths by the least common multiple
of the denominators of the rational lengths).
Suppose there exists a triangle in which the lengths $AB$ and $AC$ are
relatively-prime integers and the lengths $IB, ID, CI, IE$ are all rational.
Since $CE$ is the bisector of $\angle ACB$, by the angle bisector
theorem, the ratio $IB : ID = CB : CD$, and since $BD$ is the
bisector of $\angle ABC$, $CB : CD = (AB + BC) : AC$. Therefore,
$IB : ID = (AB + BC) : AC$. Now $IB : ID$ is by assumption rational,
so $(AB + BC) : AC$ is rational, but $AB$ and $AC$ are assumed integers
so $BC : AC$ must also be rational. Since $BC$ is the hypotenuse of
a right-triangle, its length is the square root of an integer,
and thus either an integer or irrational, so $BC$ must be an integer.
With $AB$ and $AC$ relatively-prime, we conclude that the side
lengths of $\triangle ABC$ must be a Pythagorean triple: $(2pq, p^2 - q^2, p^2 + q^2)$, with $p > q$ relatively-prime positive integers
and $p+q$ odd.
Without loss of generality, $AC = 2pq, AB = p^2 - q^2, BC = p^2+q^2$.
By the angle bisector theorem,
Since $\triangle CAE$ is a right-triangle, we have:
and so $CE$ is rational if and only if $2p^2 + 2q^2$ is a perfect square.
Also by the angle bisector theorem,
and therefore, since $\triangle DAB$ is a right-triangle, we have:
and so $BD$ is rational if and only if $p^2 + q^2$ is a perfect square.
Combining the conditions on $CE$ and $BD$, we see that
$2p^2+2q^2$ and $p^2+q^2$ must both be perfect squares. If it were so,
their ratio, which is $2$, would be the square of a rational number,
but $\sqrt{2}$ is irrational, and so the assumed triangle cannot exist.

We proceed by contradiction.
FTSOC, let $AB, BI, ID$ have integer lengths. Then $BD = BI + ID \in \mathbb{Z}$ as well. By trigonometry,
Rearranging we find $\cos{(\frac{\angle ABC}{2})} = \frac{AB}{BD} \in \mathbb{Q}$. As $0 < \angle ABC < \frac{\pi}{2}$ so $0 < \frac{\angle ABC}{2} < \frac{\pi}{4}$ but there are no possible angles in the interval that result in a rational cosine by Niven's theorem. So we have contradiction.
~Aaryabhatta1.


Find, with proof, all positive integers $n$ for which $2^n + 12^n + 2011^n$ is a perfect square.

Solution:
The answer is $n=1$, which is easily verified to be a valid integer $n$.
Notice that  Then for $n\geq 2$, we have $2^n+7^n\equiv 3,5 \pmod{12}$ depending on the parity of $n$. But perfect squares can only be $0,1,4,9\pmod{12}$, contradiction. Therefore, we are done. $\blacksquare$

Let $2^n + 12^n + 2011^n = x^2$.
Then $(-1)^n + 1 \equiv x^2 \pmod {3}$.
Since all perfect squares are congruent to 0 or 1 modulo 3, this means that n must be odd.
Proof by Contradiction:
We wish to show that the only value of $n$ that satisfies is $n = 1$.
Assume that $n \ge 2$.
Then consider the equation
$2^n + 12^n = x^2 - 2011^n$.
From modulo 2, we easily know x is odd. Let $x = 2a + 1$, where a is an integer.
$2^n + 12^n = 4a^2 + 4a + 1 - 2011^n$.
Dividing by 4,
$2^{n-2} + 3^n \cdot 4^{n-1} = a^2 + a + \dfrac {1}{4} (1 - 2011^n)$.
Since $n \ge 2$, $n-2 \ge 0$, so $2^{n-2}$ similarly, the entire LHS is an integer, and so are $a^2$ and $a$.
Thus, $\dfrac {1}{4} (1 - 2011^n)$ must be an integer.
Let $\dfrac {1}{4} (1 - 2011^n) = k$.
Then we have $1- 2011^n = 4k$.
$1- 2011^n \equiv 0 \pmod {4}$.
$(-1)^n \equiv 1 \pmod {4}$.
Thus, n is even.
However, it has already been shown that $n$ must be odd.  This is a contradiction.  Therefore, $n$ is not greater than or equal to 2, and must hence be less than 2.  The only positive integer less than 2 is 1.

If $n = 1$, then $2^n + 12^n + 2011^n = 2025 = 45^2$, a perfect square.
If $n > 1$ is odd, then $2^n + 12^n + 2011^n \equiv 0 + 0 + (-1)^n \equiv 3 \pmod{4}$.
Since all perfect squares are congruent to $0,1 \pmod{4}$, we have that $2^n+12^n+2011^n$ is not a perfect square for odd $n > 1$.
If $n = 2k$ is even, then $(2011^k)^2 < 2^{2k}+12^{2k}+2011^{2k}$ $= 4^k + 144^k + 2011^{2k} <$ $2011^k + 2011^k + 2011^{2k} < (2011^k+1)^2$.
Since $(2011^k)^2 < 2^n+12^n+2011^n < (2011^k+1)^2$, we have that $2^n+12^n+2011^n$ is not a perfect square for even $n$.
Thus, $n = 1$ is the only positive integer for which $2^n + 12^n + 2011^n$ is a perfect square.

Looking at residues mod 3, we see that $n$ must be odd, since even values of $n$ leads to $2^n + 12^n + 2011^n = 2 \pmod{3}$.  Also as shown in solution 2, for $n>1$, $n$ must be even.  Hence, for $n>1$, $n$ can neither be odd nor even.  The only possible solution is then $n=1$, which indeed works.

Take the whole expression mod 12. Note that the perfect squares can only be of the form 0, 1, 4 or 9 (mod 12). Note that since the problem is asking for positive integers, $12^n$ is always divisible by 12, so this will be disregarded in this process. If $n$ is even, then $2^n \equiv 4 \pmod{12}$ and $2011^n \equiv 7^n \equiv 1 \pmod {12}$. Therefore, the sum in the problem is congruent to $5 \pmod {12}$, which cannot be a perfect square. Now we check the case for which $n$ is an odd number greater than 1. Then $2^n \equiv 8 \pmod{12}$ and $2011^n \equiv 7^n \equiv 7 \pmod {12}$. Therefore, this sum would be congruent to $3 \pmod {12}$, which cannot be a perfect square. The only case we have not checked is $n=1$. If $n=1$, then the sum in the problem is equal to $2+12+2011=2025=45^2$. Therefore the only possible value of $n$ such that $2^n+12^n+2011^n$ is a perfect square is $n=1$.

We will first take the expression modulo $3$. We get $2^n+12^n+2011^n \equiv -1^n+1^n \pmod 3$.
Lemma 1: All perfect squares are equal to $0$ or $1$ modulo $3$.
We can prove this by testing the residues modulo $3$. We have $0^2 \equiv 0 \pmod 3$, $1^2 \equiv 1 \pmod 3$, and $2^2 \equiv 1 \pmod 3$, so the lemma is true.
We know that if $n$ is odd, $-1^n+1^n \equiv 0 \pmod 3$, which satisfies the lemma's conditions. However, if $n$ is even, we get $2 \pmod 3$, which does not satisfy the lemma's conditions. So, we can conclude that $n$ is odd.
Now, we take the original expression modulo $4$. For right now, we will assume that $n>1$, and test $n=1$ later. For $n>1$, $2^n \equiv 0 \pmod 4$, so $2^n+12^n+2011^n=-1^n \pmod 4$.
Lemma 2: All perfect squares are equal to $0$ or $1$ modulo $4$.
We can prove this by testing the residues modulo $4$. We have $0^2 \equiv 0 \pmod 4$, $1^2 \equiv 1 \pmod 4$, $2^2 \equiv 0 \pmod 4$, and $3^2 \equiv 1 \pmod 4$, so the lemma is true.
We know that if $n$ is even, $-1^n \equiv 0 \pmod 4$, which satisfies the lemma's conditions. However, if $n$ is odd, $-1^n \equiv -1 \equiv 3 \pmod 4$, which does not satisfy the lemma's conditions. Therefore, $n$ must be even.
However, a number cannot be even and odd at the same time, so this is impossible. Now, we only have to test $n=1$. We know that $2^1+12^1+2011^1=45^2$, so the only integer is $\boxed{n=1}$.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Let $a$, $b$, $c$ be positive real numbers such that $a^2 + b^2 + c^2 + (a + b + c)^2 \le 4$.  Prove that

Since

it is natural to consider a change of variables:

with the inverse mapping given by:

With this change of variables, the constraint becomes

while the left side of the inequality we need to prove is now
Therefore it remains to prove that
We note that the product of the three (positive) terms is 1/8, therefore by AM-GM their mean is at least 1/2, and thus their sum is at least 3/2 and we are done.

Rearranging the condition yields that
Now note that
Summing this for all pairs of $\{ a,b,c \}$ gives that
By AM-GM. Dividing by $2$ gives the desired inequality.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


For a point $P = (a, a^2)$ in the coordinate plane, let $\ell(P)$ denote the line passing through $P$ with slope $2a$. Consider the set of triangles with vertices of the form $P_1 = (a_1,  a_1^2)$, $P_2 = (a_2, a_2^2)$, $P_3 = (a_3, a_3^2)$, such that the intersections of the lines $\ell(P_1)$, $\ell(P_2)$, $\ell(P_3)$ form an equilateral triangle $\triangle$. Find the locus of the center of $\triangle$ as $P_1P_2P_3$ ranges over all such triangles.

Note that the lines $l(P_1), l(P_2), l(P_3)$ are  respectively. It is easy to deduce that the three points of intersection are  The slopes of each side of this equilateral triangle are  and we want to find the locus of  Define the three complex numbers $w_n = 1+2a_ni$ for $n=1,2,3$. Then note that the slope - that is, the imaginary part divided by the real part - of all $w_n^3$ is constant, say it is $k$. Then for $n=1,2,3$,

Rearranging, we get thatorNote that this is a cubic, and the roots are $a_1,a_2$ and $a_3$ which are all distinct, and so there are no other roots. Using Vieta's, we get that
and
Obviously all values of $k$ are possible, and so our answer is the line  $\blacksquare$
~ cocohearts

Note that all the points $P=(a,a^2)$ belong to the parabola $y=x^2$ which we will denote $p$. This parabola has a focus $F=\left(0,\frac{1}{4}\right)$ and directrix $y=-\frac{1}{4}$ which we will denote $d$. We will prove that the desired locus is $d$.
First note that for any point $P$ on $p$, the line $\ell(P)$ is the tangent line to $p$ at $P$. This is because $\ell(P)$ contains $P$ and because $[\frac{d}{dx}] x^2=2x$. If you don't like calculus, you can also verify that $\ell(P)$ has equation $y=2a(x-a)+a^2$ and does not intersect $y=x^2$ at any point besides $P$. Now for any point $P$ on $p$ let $P'$ be the foot of the perpendicular from $P$ onto $d$. Then by the definition of parabolas, $PP'=PF$. Let $q$ be the perpendicular bisector of $\overline{P'F}$. Since $PP'=PF$, $q$ passes through $P$. Suppose $K$ is any other point on $q$ and let $K'$ be the foot of the perpendicular from $K$ to $d$. Then in right $\Delta KK'P'$, $KK'$ is a leg and so $KK'<KP'=KF$. Therefore $K$ cannot be on $p$. This implies that $q$ is exactly the tangent line to $p$ at $P$, that is $q=\ell(P)$. So we have proved Lemma 1: If $P$ is a point on $p$ then $\ell(P)$ is the perpendicular bisector of $\overline{P'F}$.
We need another lemma before we proceed. Lemma 2: If $F$ is on the circumcircle of $\Delta XYZ$ with orthocenter $H$, then the reflections of $F$ across $\overleftrightarrow{XY}$, $\overleftrightarrow{XZ}$, and $\overleftrightarrow{YZ}$ are collinear with $H$.
Proof of Lemma 2: Say the reflections of $F$ and $H$ across $\overleftrightarrow{YZ}$ are $C'$ and $J$, and the reflections of $F$ and $H$ across $\overleftrightarrow{XY}$ are $A'$ and $I$. Then we angle chase $\angle JYZ=\angle HYZ=\angle HXZ=\angle JXZ=m(JZ)/2$ where $m(JZ)$ is the measure of minor arc $JZ$ on the circumcircle of $\Delta XYZ$. This implies that $J$ is on the circumcircle of $\Delta XYZ$, and similarly $I$ is on the circumcircle of $\Delta XYZ$. Therefore $\angle C'HJ=\angle FJH=m(XF)/2$, and $\angle A'HX=\angle FIX=m(FX)/2$. So $\angle C'HJ = \angle A'HX$. Since $J$, $H$, and $X$ are collinear it follows that $C'$, $H$ and $A'$ are collinear. Similarly, the reflection of $F$ over $\overleftrightarrow{XZ}$ also lies on this line, and so the claim is proved.
Now suppose $A$, $B$, and $C$ are three points of $p$ and let $\ell(A)\cap\ell(B)=X$, $\ell(A)\cap\ell(C)=Y$, and $\ell(B)\cap\ell(C)=Z$. Also let $A''$, $B''$, and $C''$ be the midpoints of $\overline{A'F}$, $\overline{B'F}$, and $\overline{C'F}$ respectively. Then since $\overleftrightarrow{A''B''}\parallel \overline{A'B'}=d$ and $\overleftrightarrow{B''C''}\parallel \overline{B'C'}=d$, it follows that $A''$, $B''$, and $C''$ are collinear. By Lemma 1, we know that $A''$, $B''$, and $C''$ are the feet of the altitudes from $F$ to $\overline{XY}$, $\overline{XZ}$, and $\overline{YZ}$. Therefore by the Simson Line Theorem, $F$ is on the circumcircle of $\Delta XYZ$. If $H$ is the orthocenter of $\Delta XYZ$, then by Lemma 2, it follows that $H$ is on $\overleftrightarrow{A'C'}=d$. It follows that the locus described in the problem is a subset of $d$.
Since we claim that the locus described in the problem is $d$, we still need to show that for any choice of $H$ on $d$ there exists an equilateral triangle with center $H$ such that the lines containing the sides of the triangle are tangent to $p$. So suppose $H$ is any point on $d$ and let the circle centered at $H$ through $F$ be $O$. Then suppose $A$ is one of the intersections of $d$ with $O$. Let $\angle HFA=3\theta$, and construct the ray through $F$ on the same halfplane of $\overleftrightarrow{HF}$ as $A$ that makes an angle of $2\theta$ with $\overleftrightarrow{HF}$. Say this ray intersects $O$ in a point $B$ besides $F$, and let $q$ be the perpendicular bisector of $\overline{HB}$. Since $\angle HFB=2\theta$ and $\angle HFA=3\theta$, we have $\angle BFA=\theta$. By the inscribed angles theorem, it follows that $\angle AHB=2\theta$. Also since $HF$ and $HB$ are both radii, $\Delta HFB$ is isosceles and $\angle HBF=\angle HFB=2\theta$. Let $P_1'$ be the reflection of $F$ across $q$. Then $2\theta=\angle FBH=\angle C'HB$, and so $\angle C'HB=\angle AHB$. It follows that $P_1'$ is on $\overleftrightarrow{AH}=d$, which means $q$ is the perpendicular bisector of $\overline{FP_1'}$.
Let $q$ intersect $O$ in points $Y$ and $Z$ and let $X$ be the point diametrically opposite to $B$ on $O$. Also let $\overline{HB}$ intersect $q$ at $M$. Then $HM=HB/2=HZ/2$. Therefore $\Delta HMZ$ is a $30-60-90$ right triangle and so $\angle ZHB=60^{\circ}$. So $\angle ZHY=120^{\circ}$ and by the inscribed angles theorem, $\angle ZXY=60^{\circ}$. Since $ZX=ZY$ it follows that $\Delta ZXY$ is and equilateral triangle with center $H$.
By Lemma 2, it follows that the reflections of $F$ across $\overleftrightarrow{XY}$ and $\overleftrightarrow{XZ}$, call them $P_2'$ and $P_3'$, lie on $d$. Let the intersection of $\overleftrightarrow{YZ}$ and the perpendicular to $d$ through $P_1'$ be $P_1$, the intersection of $\overleftrightarrow{XY}$ and the perpendicular to $d$ through $P_2'$ be $P_2$, and the intersection of $\overleftrightarrow{XZ}$ and the perpendicular to $d$ through $P_3'$ be $P_3$. Then by the definitions of $P_1'$, $P_2'$, and $P_3'$ it follows that $FP_i=P_iP_i'$ for $i=1,2,3$ and so $P_1$, $P_2$, and $P_3$ are on $p$. By lemma 1, $\ell(P_1)=\overleftrightarrow{YZ}$, $\ell(P_2)=\overleftrightarrow{XY}$, and $\ell(P_3)=\overleftrightarrow{XZ}$. Therefore the intersections of $\ell(P_1)$, $\ell(P_2)$, and $\ell(P_3)$ form an equilateral triangle with center $H$, which finishes the proof.
--Killbilledtoucan

Note that the lines $l(P_1), l(P_2), l(P_3)$ are  respectively. It is easy to deduce that the three points of intersection are  The slopes of each side of this equilateral triangle are  and we want to find the locus of  We know that  for some $\theta.$ Therefore, we can use the tangent addition formula to deduce  and  Now we show that $\frac{a_1+a_2+a_3}{3}$ can be any real number. Let's say  for some real number $k.$ Multiplying both sides by $2-\tan^2\theta$ and rearranging yields a cubic in $\tan\theta.$ Clearly this cubic has at least one real solution. As $\tan \theta$ can take on any real number, all values of $k$ are possible, and our answer is the line  Of course, as the denominator could equal 0, we must check $\tan \theta=\pm \frac{1}{\sqrt{3}}.$  The left side is nonzero, while the right side is zero, so these values of $\theta$ do not contribute to any values of $k.$ So, our answer remains the same. $\blacksquare$ ~ Benq


A word is defined as any finite string of letters.  A word is a palindrome if it reads the same backwards as forwards.  Let a sequence of words $W_0$, $W_1$, $W_2$, $\dots$ be defined as follows: $W_0 = a$, $W_1 = b$, and for $n \ge 2$, $W_n$ is the word formed by writing $W_{n - 2}$ followed by $W_{n - 1}$.  Prove that for any $n \ge 1$, the word formed by writing $W_1$, $W_2$, $\dots$, $W_n$ in succession is a palindrome.

Solution:
Let $r$ be the reflection function on the set of words, namely $r(a_1\dots a_n) = a_n \dots a_1$ for all words $a_1 \dots a_n$, $n\ge 1$. Then the following property is evident (e.g. by mathematical induction):
$r(w_1 \dots w_k) = r(w_k) \dots r(w_1)$, for any words $w_1, \dots, w_k$, $k \ge 1$.
We use mathematical induction to prove the statement of the problem. First, $W_1 = b$, $W_1W_2 = bab$, $W_1W_2W_3 = babbab$  are palindromes. Second, suppose $n\ge 3$, and that the words $W_1 W_2 \dots W_k$  ($k = 1$, $2$, $\dots$, $n$) are all palindromes, i.e. $r(W_1W_2\dots W_k) = W_1W_2\dots W_k$. Now, consider the word $W_1 W_2 \dots W_{n+1}$:

By the principle of mathematical induction, the statement of the problem is proved. Lightest 21:54, 1 April 2012 (EDT)
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Points $A$, $B$, $C$, $D$, $E$ lie on a circle $\omega$ and point $P$ lies outside the circle.  The given points are such that (i) lines $PB$ and $PD$ are tangent to $\omega$, (ii) $P$, $A$, $C$ are collinear, and (iii) $\overline{DE} \parallel \overline{AC}$.  Prove that $\overline{BE}$ bisects $\overline{AC}$.

Solution: Since $\overline{DE} \parallel \overline{AC}$, we have that $AD=CE\rightarrow \angle ABD=\angle CBE$. But it is well known that $ABCD$ is a harmonic quadrilateral, thus $\overline{BD}$ is a symmedian of triangle $ABC$, from which it follows that $\overline{BE}$ is a median of $\triangle ABC$. $\blacksquare$

Connect segment PO, and name the interaction of PO and the circle as point M.
Since PB and PD are tangent to the circle, it's easy to see that M is the midpoint of arc BD.
∠ BOA = 1/2 arc AB + 1/2 arc CE
Since AC // DE, arc AD = arc CE,
thus, ∠ BOA = 1/2 arc AB + 1/2 arc AD = 1/2 arc BD = arc BM = ∠ BOM
Therefore, PBOM is cyclic, ∠ PFO = ∠ OBP = 90°, AF = AC (F is the interaction of BE and AC)
BE bisects AC, proof completed!
~ MVP Harry

Let $O$ be the center of the circle, and let $X$ be the intersection of $AC$ and $BE$. Let $\angle OPA$ be $x$ and $\angle OPD$ be $y$.
$\angle OPB = \angle OPD = y$, $\angle BED = \frac{\angle DOB}{2} = 90-y$,
$\angle ODE = \angle PDE - 90 = 90-x-y$
$\angle OBE = \angle PBE - 90 = x = \angle OPA$
Thus $PBXO$ is a cyclic quadrilateral and $\angle OXP = \angle OBP = 90$ and so $X$ is the midpoint of chord $AC$.
~pandadude

This is the solution from EGMO Problem 1.43 page 242
Let $O$ be the center of the circle, and let $M$ be the midpoint of $AC$.  Let $\theta$ denote the circle with diameter $OP$.  Since $\angle OBP = \angle OMP = \angle ODP = 90^\circ$, $B$, $D$, and $M$ all lie on $\theta$.

Since quadrilateral $BOMP$ is cyclic, $\angle BMP = \angle BOP$.  Triangles $BOP$ and $DOP$ are congruent, so $\angle BOP = \angle BOD/2 = \angle BED$, so $\angle BMP = \angle BED$. Because $AC$ and $DE$ are parallel, $M$ lies on $BE$ (using Euclid's Parallel Postulate).
-Evan Chen (vEnhance)

Note that by Lemma 9.9 of EGMO, $(A,C;B,D)$ is a harmonic bundle. We project through $E$ onto $\overline{AC}$,

Where $P_{\infty}$ is the point at infinity for parallel lines $\overline{DE}$ and $\overline{AC}$. Thus, we get $\frac{MA}{MC}=-1$, and $M$ is the midpoint of $AC$. ~novus677
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Consider the assertion that for each positive integer $n \ge 2$, the remainder upon dividing $2^{2^n}$ by $2^n-1$ is a power of 4. Either prove the assertion or find (with proof) a counter-example.

Solution:
We will show that $n = 25$ is a counter-example.
Since $\textstyle 2^n \equiv 1 \pmod{2^n - 1}$, we see that for any integer $k$, $\textstyle 2^{2^n} \equiv 2^{(2^n - kn)} \pmod{2^n-1}$. Let $0 \le m < n$ be the residue of $2^n \pmod n$. Note that since $\textstyle m < n$ and $\textstyle n \ge 2$, necessarily $\textstyle 2^m < 2^n -1$, and thus the remainder in question is $\textstyle 2^m$. We want to show that $\textstyle 2^m \pmod {2^n-1}$ is an odd power of 2 for some $\textstyle n$, and thus not a power of 4.
Let $\textstyle n=p^2$ for some odd prime $\textstyle p$. Then $\textstyle \varphi(p^2) = p^2 - p$. Since 2 is co-prime to $\textstyle p^2$, we have

and thus
Therefore, for a counter-example, it suffices that $\textstyle 2^p \pmod{p^2}$ be odd. Choosing $\textstyle p=5$, we have $\textstyle 2^5 = 32 \equiv 7 \pmod{25}$. Therefore, $\textstyle 2^{25} \equiv 7 \pmod{25}$ and thus

Since $\textstyle 2^7$ is not a power of 4, we are done.

Lemma (useful for all situations): If $x$ and $y$ are positive integers such that $2^x - 1$ divides $2^y - 1$, then $x$ divides $y$.
Proof: $2^y \equiv 1 \pmod{2^x - 1}$. Replacing the $1$ with a $2^x$ and dividing out the powers of two should create an easy induction proof which will be left to the reader as an Exercise.
Consider $n = 25$. We will prove that this case is a counterexample via contradiction.
Because $4 = 2^2$, we will assume there exists a positive integer $k$ such that $2^{2^n} - 2^{2k}$ divides $2^n - 1$ and $2^{2k} < 2^n - 1$. Dividing the powers of $2$ from LHS gives $2^{2^n - 2k} - 1$ divides $2^n - 1$. Hence, $2^n - 2k$ divides $n$. Because $n = 25$ is odd, $2^{24} - k$ divides $25$. Euler's theorem gives $2^{24} \equiv 2^4 \equiv 16 \pmod{25}$ and so $k \ge 16$. However, $2^{2k} \geq 2^{32} > 2^{25} - 1$, a contradiction. Thus, $n = 25$ is a valid counterexample.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Given a triangle $ABC$, let $P$ and $Q$ be points on segments $\overline{AB}$ and $\overline{AC}$, respectively, such that $AP = AQ$.  Let $S$ and $R$ be distinct points on segment $\overline{BC}$ such that $S$ lies between $B$ and $R$, $\angle{BPS} = \angle{PRS}$, and $\angle{CQR} = \angle{QSR}$.  Prove that $P$, $Q$, $R$, $S$ are concyclic (in other words, these four points lie on a circle).

Solution:
Since $\angle BPS = \angle PRS$, the circumcircle of triangle $PRS$ is tangent to $AB$ at $P$.  Similarly, since $\angle CQR = \angle QSR$, the circumcircle of triangle $QRS$ is tangent to $AC$ at $Q$.

For the sake of contradiction, suppose that the circumcircles of triangles $PRS$ and $QRS$ are not the same circle.  Since $AP = AQ$, $AP^2 = AQ^2$, so the power of A with respect to both circumcircles is the same. Thus, $A$ lies on the radical axis of both circles.  However, both circles pass through $R$ and $S$, so the radical axis of both circles is $RS$.  Hence, $A$ lies on $RS$, which is a contradiction.
Therefore, the two circumcircles are the same circle.  In other words, $P$, $Q$, $R$, and $S$ all lie on the same circle.

Note that (as in the first solution) the circumcircle of triangle $PRS$ is tangent to $AB$ at $P$.  Similarly, since $\angle CQR = \angle QSR$, the circumcircle of triangle $QRS$ is tangent to $AC$ at $Q$.
Now, suppose these circumcircles are not the same circle. They already intersect at $R$ and $S$, so they cannot intersect anymore. Thus, AS must touch the two circumcircles at points $M$ and $N$, with $M$ on the circumcircle of triangle $PRS$. By Power of a Point, $AQ^2 = AM \cdot AS$ and $AP^2 = AN \cdot AS$. Hence, because $AP = AQ$, $AM = AN$, a contradiction because then, as they lie on the same line segment, M and N must be the same point! (Note line segment, not line.) Hence, the two circumcircles are the same circle.


Find all integers $n \ge 3$ such that among any $n$ positive real numbers $a_1$, $a_2$, $\dots$, $a_n$ with

there exist three that are the side lengths of an acute triangle.

Solution:
Without loss of generality, assume that the set $\{a\}$ is ordered from least to greatest so that the bounding condition becomes $a_n \le n \cdot a_1.$ Now set $b_i \equiv \frac{a_i}{a_1},$ and since a triangle with sidelengths from $\{a\}$ will be similar to the corresponding triangle from $\{b\},$ we simply have to show the existence of acute triangles in $\{b\}.$ Note that $b_1 = 1$ and for all $i$, $b_i \le n.$
Now three arbitrary sidelengths $x$, $y$, and $z$, with $x \le y \le z,$ will form a valid triangle if and only if $x+y>z.$ Furthermore, this triangle will be acute if and only if $x^2 + y^2 > z^2.$ However, the first inequality can actually be inferred from the second, since $x+y>z \longrightarrow x^2 + y^2 +2xy > z^2$ and $2xy$ is trivially greater than $0.$ So we just need to find all $n$ such that there is necessarily a triplet of $b$'s for which $b_i^2 + b_j^2 > b_k^2$ (where $b_i < b_j < b_k$).
We now make another substitution: $c_i \equiv b_i ^2.$ So $c_1 = 1$ and for all $i$, $c_i \le n^2.$ Now we examine the smallest possible sets $\{c\}$ for small $n$ for which the conditions of the problem are not met. Note that by smallest, we mean the set whose greatest element is as small as possible. If $n=3$, then the smallest possible set, call it $\{s_3\},$ is trivially $\{1,1,2\}$, since $c_1$ and $c_2$ are obviously minimized and $c_3$ follows as minimal. Using this as the base case, we see inductively that in general $\{s_n\}$ is the set of the first $n$ Fibonacci numbers. To show this note that if $\{s_n\} = \{F_0, F_1, ... F_n\}$, then $\{s_{n+1}\} = \{F_0, F_1, ... F_n, c_{n+1}\}.$ The smallest possible value for $c_{n+1}$ is the sum of the two greatest values of $\{s_n\}$ which are $F_{n-1}$ and $F_n$. But these sum to $F_{n+1}$ so $\{s_{n+1}\} = \{F_0, F_1, ... F_{n+1}\}$ and our induction is complete.
Now since we know that the Fibonacci set is the smallest possible set which does not satisfy the conditions of the problem, then any set $\{c\}$ whose greatest term is less than $F_{n-1}$ must satisfy the conditions. And since $\{c\}$ is bounded between $1$ and $n^2$, then the conditions of the problem are met if and only if $F_{n-1} > n^2$. The first $n$ for which this restriction is satisfied is $n=13$ and the exponential behavior of the Fibonacci numbers ensure that every $n$ greater than $13$ will also satisfy this restriction. So the final solution set is $\boxed{\{n \ge 13\}}$.

Outline:
1. Define the Fibonacci numbers to be $F_1 = F_2 = 1$ and $F_k = F_{k-1} + F_{k-2}$ for $k \ge 3$.
2. If the chosen $n$ is such that $F_n \le n^2$, then choose the sequence $a_n$ such that $a_k = \sqrt{F_k}$ for $1 \le k \le n$. It is easy to verify that such a sequence satisfies the condition that the largest term is less than or equal to $n$ times the smallest term. Also, because for any three terms $x = \sqrt{F_a}, y = \sqrt{F_b}, z = \sqrt{F_c}$ with $a<b<c$, $x^2 + y^2 = F_a + F_b \le F_{b-1} + F_b = F_{b+1} \le F_c = z^2$, x, y, z do not form an acute triangle. Thus, all $n$ such that $F_n \le n^2$ do not work.
3. It is easy to observe via a contradiction argument that all $n$ such that $F_n > n^2$ produce an acute triangle. (If, without loss of generality, $a_n$ is an increasing sequence, such that no three (in particular, consecutive) terms form an acute triangle, then $a_2^2 \ge F_1a_1^2, a_3^2 \ge a_2^2 + a_1^2 \ge F_2a^2$, and by induction $a_n^2 > F_na_1^2$, a contradiction to the condition's inequality.)
4. Note that $F_{12} = 144 = 12^2$ and $F_{13} = 233 > 169 = 13^2$. It is easily to verify through strong induction that all $n$ greater than 12 make $F_n > n^2$. Thus, $\boxed{n \ge 13}$ is the desired solution set.


Let $a$, $b$, $c$ be positive real numbers.  Prove that

Solution:
By the Cauchy-Schwarz inequality,

so

Since $a^2 + b^2 + c^2 \ge ab + ac + bc$,

Hence,
Again by the Cauchy-Schwarz inequality,

so

Since $a^2 + b^2 + c^2 \ge ab + ac + bc$,

Hence,
Therefore,

Titu's Lemma: The sum of multiple fractions in the form $\frac{a_n^2}{b_n}$ where $a_n$ and $b_n$ are sequences of real numbers is greater than of equal to the square of the sum of all $a_i$ divided by the sum of all $b_i$, where i is a whole number less than n+1. Titu's Lemma can be proved using the Cauchy-Schwarz Inequality after multiplying out the denominator of the RHS.
Consider the LHS of the proposed inequality. Split up the numerators and multiply both sides of the fraction by either a or 3a to make the LHS

(Cyclic notation is a special notation in which all permutations of (a,b,c) is the summation command.)
Then use Titu's Lemma on all terms:  owing to the fact that $a^2+b^2+c^2 \ge ab+bc+ca$, which is actually equivalent to $(a-b)^2 + (b-c)^2 + (c-a)^2 \ge 0$!

We proceed to prove that
(then the inequality in question is just the cyclic sum of both sides, since
)
Indeed, by AP-GP, we have

and

Summing up, we have

which is equivalent to:

Dividing $36(5a+b)$ from both sides, the desired inequality is proved.
--Lightest 15:31, 7 May 2012 (EDT)

By Cauchy-Schwarz,

(by AM-GM)  as desired.

We note that if we can prove that there exists a real number $x$ such that  for all positive reals $a$ and $b$, then we are done since both sides are a cyclic sum of $a,b$, and $c$. Note that if we multiply both $a$ and $b$ by a constant $r$, the left and right sides will both multiply by $r^2$ (since the numerator on the left will multiply by $r^3$ and the denominator will multiply by $r$. This means that if the inequality is satisfied for an ordered pair $(a,b)$, then it is also satisfied for $(ar,br)$ for any positive real $r$. Thus, without loss of generality we can let $b=1$,and our inequality becomes  Expanding this and rearranging we get $a^3(1-5x)+a^2(-x)+a(5x-\frac{10}{3})+x+\frac{7}{3}\geq0$. Since $1$ is a root of the left side, we can factor this as  Note that for this to always be nonnegative, we must have $a^2(1-5x)+a(1-6x)-x-\frac{7}{3}$ be positive when $a>1$ and negative when $a<1$. Thus, it must have a root at $a=1$, so we plug in $a=1$ is a root and find that we must have $x=-\frac{1}{36}$. When $x=-\frac{1}{36}$, the expression factors as $(a-1)^2(\frac{41}{36}a+\frac{83}{36})\geq0$ which obviously is nonnegative for all positive reals $a$, so we are done.
~john0512, bronzetruck2016


Let $\alpha$ be an irrational number with $0 < \alpha < 1$, and draw a circle in the plane whose circumference has length 1.  Given any integer $n \ge 3$, define a sequence of points $P_1$, $P_2$, $\dots$, $P_n$ as follows.  First select any point $P_1$ on the circle, and for $2 \le k \le n$ define $P_k$ as the point on the circle for which the length of arc $P_{k - 1} P_k$ is $\alpha$, when travelling counterclockwise around the circle from $P_{k - 1}$ to $P_k$.  Supose that $P_a$ and $P_b$ are the nearest adjacent points on either side of $P_n$.  Prove that $a + b \le n$.

Solution:
Use mathematical induction. For $n=3$ it is true because one point can't be closest to $P_3$ in both ways, and that $1+2\le 3$. Suppose that for some $n$, the nearest adjacent points $P_a$ and $P_b$ on either side of $P_n$ satisfy  $a+b \le n$. Then consider the nearest adjacent points $P_c$ and $P_d$ on either side of $P_{n+1}$. It is by the assumption of the nearness we can see that either $(c,d)=(a+1,b+1)$ still holds, or $P_1$ jumps into the interior of the arc $P_{a+1}P_{n}P_{b+1}$, so that $c$ or $d$ equals to $1$. Let's consider the following two cases.
(i) Suppose $a+b=n$.
Since the length of the arc $P_nP_a$ is $\{(a-n)\alpha\}$ (where $\{x\}$ equals to $x$ subtracted by the greatest integer not exceeding $x$) and length of the arc $P_bP_n$ is $\{(n-b)\alpha\} = \{a\alpha\}$, we now consider a point $P_0$ which is defined by $P_1$ traveling clockwise on the circle such that the length of arc $P_0P_1$ is $\alpha$. We claim that $P_0$ is in the interior of the arc $P_bP_nP_a$. Algebraically, it is equivalent to either $\{0-n\alpha\} < \{a\alpha-n\alpha\}$ or $\{n\alpha -0 \} < \{n\alpha - b\alpha\} = \{a\alpha\}$.
Suppose the latter fails, i.e. $\{n\alpha\} \ge \{a\alpha\}$. Then suppose $n\alpha = m_1 + r_1$ and $a\alpha = m_2 + r_2$, where $m_1$, $m_2$ are integers and $0< r_2\le r_1 <1$ ($r_2$ is not zero because $a\alpha$ is irrational). We now have
 and
Therefore $P_0$ is either closer to $P_n$ than $P_a$ on the $P_a$ side, or closer to $P_n$ than $P_b$ on the $P_b$ side. In other words, $P_1$ is the closest adjacent point of $P_{n+1}$ on the $P_{a+1}$ side, or the closest adjacent point of $P_{n+1}$ on the $P_{b+1}$ side. Hence $P_c$ or $P_d$ is $P_1$, therefore $c+d \le n+1$.
(ii) Suppose $a+b\le n-1$
Then either $c+d = (a+1)+(b+1) \le n+1$ when $c=a+1$ and $d=b+1$, or $c+d \le 1+n$ when one of $P_c$ or $P_d$ is $P_1$.
In either case, $c+d\le n+1$ is true.
--Lightest 20:27, 6 May 2012 (EDT)


For distinct positive integers $a$, $b < 2012$, define $f(a,b)$ to be the number of integers $k$ with $1 \le k < 2012$ such that the remainder when $ak$ divided by 2012 is greater than that of $bk$ divided by 2012.  Let $S$ be the minimum value of $f(a,b)$, where $a$ and $b$ range over all pairs of distinct positive integers less than 2012.  Determine $S$.

First we'll show that $S \geq 502$, then we'll find an example $(a, b)$ that have $f(a, b)=502$.
Let $x_k$ be the remainder when $ak$ is divided by 2012, and let $y_k$ be defined similarly for $bk$. First, we know that, if $x_k > y_k >0$, then $x_{2012-k} \equiv a(2012-k) \equiv 2012-ak \equiv 2012-x_k \pmod {2012}$ and $y_{2012-k} \equiv 2012-y_k \pmod {2012}$. This implies that, since $2012 - x_k \neq 0$ and $2012 -y_k \neq 0$, $x_{2012-k} < y_{2012-k}$. Similarly, if $0< x_k < y_k$ then $x_{2012-k} > y_{2012-k}$, establishing a one-to-one correspondence between the number of $k$ such that $x_k < y_k$. Thus, if $n$ is the number of $k$ such that $x_k \neq y_k$ and $y_k \neq 0 \neq x_k$, then $S \geq \frac{1}{2}n$. Now I'll show that $n \geq 1004$.
If $gcd(k, 2012)=1$, then I'll show you that $x_k \neq y_k$. This is actually pretty clear; assume that's not true and set up a congruence relation:

Since $k$ is relatively prime to 2012, it is invertible mod 2012, so we must have $a \equiv b \pmod {2012}$. Since $0 < a, b <2012$, this means $a=b$, which the problem doesn't allow, thus contradiction, and $x_k \neq y_k$. Additionally, if $gcd(k, 2012)=1$, then $x_k \neq 0 \neq y_k$, then based on what we know about $n$ from the previous paragraph, $n$ is at least as large as the number of k relatively prime to 2012. Thus, $n \geq \phi(2012) = \phi(503*4) = 1004$. Thus, $S \geq 502$.
To show 502 works, consider $(a, b)=(1006, 2)$. For all even $k$ we have $x_k=0$, so it doesn't count towards $f(1006, 2)$. Additionally, if $k = 503, 503*3$ then $x_k = y_k = 1006$, so the only number that count towards $f(1006, 2)$ are the odd numbers not divisible by 503. There are 1004 such numbers. However, for all such odd k not divisible by 503 (so numbers relatively prime to 2012), we have $x_k \neq 0 \neq y_k$ and $2012-k$ is also relatively prime to 2012. Since under those conditions exactly one of $x_k > y_k$ and $x_{2012-k} > y_{2012-k}$ is true, we have at most 1/2 of the 1004 possible k actually count to $f(1006, 2)$, so $\frac{1004}{2} = 502 \geq f(1006, 2) \geq S \geq 502$, so $S=502$.

Let $ak \equiv r_{a} \pmod{2012}$ and $bk \equiv r_{b} \pmod{2012}$. Notice that this means $a(2012 - k) \equiv 2012 - r_{a} \pmod{2012}$ and $b(2012 - k) \equiv 2012 - r_{b} \pmod{2012}$. Thus, for every value of $k$ where $r_{a} > r_{b}$, there is a value of $k$ where $r_{b} > r_{a}$. Therefore, we merely have to calculate $\frac{1}{2}$ times the number of values of $k$ for which $r_{a} \neq r_{b}$ and $r_{a} \neq 0$.
However, the answer is NOT $\frac{1}{2}(2012) = 1006$! This is because we must count the cases where the value of $k$ makes $r_{a} = r_{b}$ or where $r_{a} = 0$.
So, let's start counting.
If $k$ is even, we have either $a \equiv 0 \pmod{1006}$ or $a - b \equiv 0 \pmod{1006}$. So, $a = 1006$ or $a = b + 1006$. We have $1005$ even values of $k$ (which is all the possible even values of $k$, since the two above requirements don't put any bounds on $k$ at all).
If $k$ is odd, if $k = 503$ or $k = 503 \cdot 3$, then $a \equiv 0 \pmod{4}$ or $a \equiv b \pmod{4}$. Otherwise, $ak \equiv 0 \pmod{2012}$ or $ak \equiv bk \pmod{2012}$, which is impossible to satisfy, given the domain $a, b < 2012$. So, we have $2$ values of $k$.
In total, we have $2 + 1005 = 1007$ values of $k$ which makes $r_{a} = r_{b}$ or $r_{a} = 0$, so there are $2011 - 1007 = 1004$ values of $k$ for which $r_{a} \neq r_{b}$ and $r_{a} \neq 0$. Thus, by our reasoning above, our solution is $\frac{1}{2} \cdot 1004 = \boxed{502}$.
Solution by $\textbf{\underline{Invoker}}$

The key insight in this problem is noticing that when $ak$ is higher than $bk$, $a(2012-k)$ is lower than $b(2012-k)$, except at $2 \pmod{4}$ residues*. Also, they must be equal many times. $2012=2^2*503$. We should have multiples of $503$. After trying all three pairs and getting $503$ as our answer, we win. But look at the $2\pmod{4}$ idea. What if we just took $2$ and plugged it in with $1006$?
We get $502$.

Say that the problem is a race track with $2012$ spots. To intersect the most, we should get next to each other a lot so the negation is high. As $2012=2^2*503$, we intersect at a lot of multiples of $503$.


Let $P$ be a point in the plane of triangle $ABC$, and $\gamma$ a line passing through $P$.  Let $A'$, $B'$, $C'$ be the points where the reflections of lines $PA$, $PB$, $PC$ with respect to $\gamma$ intersect lines $BC$, $AC$, $AB$, respectively.  Prove that $A'$, $B'$, $C'$ are collinear.

Solution:
By the sine law on triangle $AB'P$,

so

Similarly,

Hence,
Since angles $\angle AB'P$ and $\angle CB'P$ are supplementary or equal, depending on the position of $B'$ on $AC$,

Similarly,
By the reflective property, $\angle APB'$ and $\angle BPA'$ are supplementary or equal, so

Similarly,

Therefore,

so by Menelaus's theorem, $A'$, $B'$, and $C'$ are collinear.

We will perform barycentric coordinates on the triangle $PCC'$, with $P=(1,0,0)$, $C'=(0,1,0)$, and $C=(0,0,1)$. Set $a = CC'$, $b = CP$, $c = C'P$ as usual. Since $A$, $B$, $C'$ are collinear, we will define $A = (p : k : q)$ and $B = (p : \ell : q)$.
Claim: Line $\gamma$ is the angle bisector of $\angle APA'$, $\angle BPB'$, and $\angle CPC'$.
This is proved by observing that since $A'P$ is the reflection of $AP$ across $\gamma$, etc.
Thus $B'$ is the intersection of the isogonal of $B$ with respect to $\angle P$
with the line $CA$; that is,

Analogously, $A'$ is the intersection of the isogonal of $A$ with respect to $\angle P$
with the line $CB$; that is,

The ratio of the first to third coordinate in these two points
is both $b^2pq : c^2k\ell$, so it follows $A'$, $B'$, and $C'$ are collinear.
~peppapig_


Are there integers $a$ and $b$ such that $a^5b+3$ and $ab^5+3$ are both perfect cubes of integers?

Solution:
No, such integers do not exist.  This shall be proven by contradiction, by showing that if $a^5b+3$ is a perfect cube then $ab^5+3$ cannot be.
Remark that perfect cubes are always congruent to $0$, $1$, or $-1$ modulo $9$.  Therefore, if $a^5b+3\equiv 0,1,\text{ or} -1\pmod{9}$, then $a^5b\equiv 5,6,\text{ or }7\pmod{9}$.
If $a^5b\equiv 6\pmod 9$, then note that $3|b$.  (This is because if $3|a$ then $a^5b\equiv 0\pmod 9$.)  Therefore $ab^5\equiv 0\pmod 9$ and $ab^5+3\equiv 3\pmod 9$, contradiction.
Otherwise, either $a^5b\equiv 5\pmod 9$ or $a^5b\equiv 7\pmod 9$.  Note that since $a^6b^6$ is a perfect sixth power, and since neither $a$ nor $b$ contains a factor of $3$, $a^6b^6\equiv 1\pmod 9$.  If $a^5b\equiv 5\pmod 9$, then   Similarly, if $a^5b\equiv 7\pmod 9$, then   Therefore $ab^5+3\equiv 5,7\pmod 9$, contradiction.
Therefore no such integers exist.
Amkan2022

We shall prove that such integers do not exist via contradiction.
Suppose that $a^5b + 3 = x^3$ and $ab^5 + 3 = y^3$ for integers x and y. Rearranging terms gives $a^5b = x^3 - 3$ and $ab^5 = y^3 - 3$. Solving for a and b (by first multiplying the equations together and taking the sixth root) gives a = $(x^3 - 3)^\frac{5}{24} (y^3 - 3)^\frac{-1}{24}$ and b = $(y^3 - 3)^\frac{5}{24} (x^3 - 3)^\frac{-1}{24}$. Consider a prime p in the prime factorization of $x^3 - 3$ and $y^3 - 3$. If it has power $r_1$ in $x^3 - 3$ and power $r_2$ in $y^3 - 3$, then $5r_1$ - $r_2$ is a multiple of 24 and $5r_2$ - $r_1$ also is a multiple of 24.
Adding and subtracting the divisions gives that $r_1$ - $r_2$ divides 12. (actually, $r_1 - r_2$ is a multiple of 4, as you can verify if $\{^{5r_1 - r_2 = 24}_{5r_2 - r_1 = 48}$. So the rest of the proof is invalid.) Because $5r_1$ - $r_2$ also divides 12, $4r_1$ divides 12 and thus $r_1$ divides 3. Repeating this trick for all primes in $x^3 - 3$, we see that $x^3 - 3$ is a perfect cube, say $q^3$. Then $x^3 - q^3 = 3,$ and $(x-q)(x^2 + xq + q^2) = 3$, so that $x - q = 1$ and $x^2 + xq + q^2 = 3$. Clearly, this system of equations has no integer solutions for $x$ or $q$, a contradiction, hence completing the proof.
Therefore no such integers exist.

Let $a^5b+3=x^3$ and $ab^5+3=y^3$. Then, $a^5b=x^3-3$, $ab^5=y^3-3$, and
Now take $\text{mod }9$ (recall that perfect cubes $\equiv -1,0,1\pmod{9}$ and perfect sixth powers $\equiv 0,1\pmod{9}$) on both sides. There are $3\times 3=9$ cases to consider on what values $\text{mod }9$ that $x^3$ and $y^3$ take. Checking these $9$ cases, we see that only $x^3\equiv y^3\equiv 0\pmod{9}$ or $x\equiv y\equiv 0\pmod{3}$ yield a valid residue $\text{mod }9$ (specifically, $(x^3-3)(y^3-3)\equiv 0\pmod{9}$). But this means that $3\mid ab$, so $729\mid (ab)^6$ so  contradiction.

If $a^5b+3$ is a perfect cube, then $a^5b$ can be one of $5,6,7 \pmod 9$, so $(a^5b)^5 = a^{25} b^5$ can be one of $5^5 \equiv 2$, $6^5 \equiv 0$, or $7^5 \equiv 4 \pmod 9$. If $a$ were divisible by $3$, we'd have $a^5 b \equiv 0 \pmod 9$, which we've ruled out. So $\gcd(a,9) = 1$, which means $a^6 \equiv 1 \pmod 9$, and therefore $a^{25} b^5 \equiv ab^5 \pmod 9$.
We've shown that $a b^5$ can be one of $0, 2, 4 \pmod 9$, so $ab^5 + 3$ can be one of $3, 5, 7 \pmod 9$. None of these are possibilities for a perfect cube, so if $a^5b+3$ is a perfect cube, $ab^5+3$ cannot be.

As in previous solutions, notice $ab^5,a^5b \equiv 5,6,7 \pmod 9$. Now multiplying gives $a^6b^6$, which is only $0,1 \pmod 9$, so after testing all cases we find that $ab^5\equiv a^5b \equiv 6 \mod 9$. Then since $\phi (9) = 6$, $ab^5\equiv \frac{a}{b}\pmod 9$ and $a^5b \equiv \frac{b}{a}\pmod 9$ (Note that $a,b$ cannot be $0\pmod 9$). Thus we find that the inverse of $6$ is itself under modulo $9$, a contradiction.

I claim there are no such a or b such that both expressions are cubes.
Assume to the contrary $a^5b +3$ and $ab^5 + 3$ are cubes.
Lemma 1: If $a^5b +3$ and $ab^5 + 3$ are cubes, then $ab^5, a^5b \equiv 5,7 \pmod 9$
Proof Since cubes are congruent to any of $0, 1, -1 \pmod 9$, $ab^5,a^5b \equiv 5,6,7 \pmod 9$. But if $ab^5 \equiv 6 \pmod 9$, $3|a$, so $a^5b \equiv 0 \pmod 9$, contradiction. A similar argument can be made for $ab^5 \neq 6 \pmod 9$.
Lemma 2: If k is a perfect 6th power, then $k \equiv 0,1 \pmod 9$
Proof: Since cubes are congruent to $0, 1,  -1 \pmod 9$, we can square, and get 6th powers are congruent to $0, 1 \pmod 9$.
Since $ab^5 \cdot a^5b = a^6 b^6 = (ab)^6$, which is a perfect 6th power, by lemma 2, $ab^5 \cdot a^5b \equiv 0,1 \pmod 9$.
But, by lemma 1, $ab^5 \cdot a^5b \equiv 5 \cdot 5, 5 \cdot 7, 7 \cdot 7 \equiv 7, 8, 4 \pmod 9$.
So, $ab^5 \cdot a^5b$, which is an integer, can't go into any of the possible residue classes modulo 9, without breaking one of these lemmas. This is a contradiction, and the proof is complete. $\blacksquare$
-AlexLikeMath


Each cell of an $m\times n$ board is filled with some nonnegative integer. Two numbers in the filling are said to be adjacent if their cells share a common side. (Note that two numbers in cells that share only a corner are not adjacent). The filling is called a garden if it satisfies the following two conditions:
(i) The difference between any two adjacent numbers is either $0$ or $1$.
(ii) If a number is less than or equal to all of its adjacent numbers, then it is equal to  $0$ .
Determine the number of distinct gardens in terms of $m$ and $n$ .

Solution:
We claim that any configuration of $0$'s produces a distinct garden.  To verify this claim, we show that, for any cell that is nonzero, the value of that cell is its distance away from the nearest zero, where distance means the shortest chain of adjacent cells connecting two cells.  Now, since we know that any cell with a nonzero value must have a cell adjacent to it that is less than its value, there is a path that goes from this cell to the $0$ that is decreasing, which means that the value of the cell must be its distance from the $0 \rightarrow$ as the path must end.  From this, we realize that, for any configuration of $0$'s, the value of each of the cells is simply its distance from the nearest $0$, and therefore one garden is produced for every configuration of $0$'s.
However, we also note that there must be at least one $0$ in the garden, as otherwise the smallest number in the garden, which is less than or equal to all of its neighbors, is $>0$, which violates condition $(ii)$.  There are $2^{mn}$ possible configurations of $0$ and not $0$ in the garden, one of which has no $0$'s, so our total amount of configurations is $\boxed{2^{mn} -1}$


In triangle $ABC$, points $P,Q,R$ lie on sides $BC,CA,AB$ respectively.  Let $\omega_A$, $\omega_B$, $\omega_C$ denote the circumcircles of triangles $AQR$, $BRP$, $CPQ$, respectively.  Given the fact that segment $AP$ intersects $\omega_A$, $\omega_B$, $\omega_C$ again at $X,Y,Z$ respectively, prove that $YX/XZ=BP/PC$.

In this solution, all lengths and angles are directed.
Firstly, it is easy to see by that $\omega_A, \omega_B, \omega_C$ concur at a point $M$ (the Miquel point). Let $XM$ meet $\omega_B, \omega_C$ again at $D$ and $E$, respectively. Then by Power of a Point, we have  Thusly  But we claim that $\triangle XDP \sim \triangle PBM$. Indeed,  and
Therefore, $\frac{XD}{XP} = \frac{PB}{PM}$. Analogously we find that $\frac{XE}{XP} = \frac{PC}{PM}$ and we are done.
courtesy v_enhance, minor clarification by integralarefun

Diagram
Refer to the Diagram link.
By Miquel's Theorem, there exists a point at which $\omega_A, \omega_B, \omega_C$ intersect. We denote this point by $M.$ Now, we angle chase:

In addition, we have

Now, by the Ratio Lemma, we have
 (by the Law of Sines in $\triangle MZY$) (by the Law of Sines in $\triangle MBC$) by the Ratio Lemma.
The proof is complete.

Use directed angles modulo $\pi$.
Lemma. $\angle{XRY} \equiv \angle{XQZ}.$
Proof.
Now, it follows that (now not using directed angles)

using the facts that $ARY$ and $APB$, $AQZ$ and $APC$ are similar triangles, and that $\frac{RA}{\sin \angle{RXA}} = \frac{QA}{\sin \angle{QXA}}$ equals twice the circumradius of the circumcircle of $AQR$.

We will use some construction arguments to solve the problem. Let $\angle BAC=\alpha,$ $\angle ABC=\beta,$ $\angle ACB=\gamma,$ and let $\angle APB=\theta.$ We construct lines through the points $Q,$ and $R$ that intersect with $\triangle ABC$ at the points $Q$ and $R,$ respectively, and that intersect each other at $T.$ We will construct these lines such that $\angle CQV=\angle ARV=\theta.$
Now we let the intersections of $AP$ with $RV$ and $QU$ be $Y'$ and $Z',$ respectively. This construction is as follows.
We know that $\angle BRY'=180^\circ-\angle ARY'=180^\circ-\theta.$ Hence, we have,
Since the opposite angles of quadrilateral $RY'PB$ add up to $180^\circ,$ it must be cyclic. Similarly, we can also show that quadrilaterals $CQZ'P,$ and $AQTR$ are also cyclic.
Since points $Y'$ and $Z'$ lie on $AP,$ we know that,

and that
Hence, the points $Y'$ and $Z'$ coincide with the given points $Y$ and $Z,$ respectively.
Since quadrilateral $AQTR$ is also cyclic, we have,
Similarly, since quadrilaterals $CQZ'P,$ and $AQTR$ are also cyclic, we have,

and,
Since these three angles are of $\triangle TY'Z',$ and they are equal to corresponding angles of $\triangle ABC,$ by AA similarity, we know that $\triangle TY'Z'\sim \triangle ABC.$
We now consider the point $X=\omega_c\cap AC.$ We know that the points $A,$ $Q,$ $T,$ and $R$ are concyclic. Hence, the points $A,$ $T,$ $X,$ and $R$ must also be concyclic.
Hence, quadrilateral $AQTX$ is cyclic.

Since the angles $\angle ART$ and $\angle AXT$ are inscribed in the same arc $\overarc{AT},$ we have,
Consider by this result, we can deduce that the homothety that maps $ABC$ to $TY'Z'$ will map $P$ to $X.$ Hence, we have that,
Since $Y'=Y$ and $Z'=Z$ hence,
as required.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Let $f(n)$ be the number of ways to write $n$ as a sum of powers of $2$, where we keep track of the order of the summation.  For example, $f(4)=6$ because $4$ can be written as $4$, $2+2$, $2+1+1$, $1+2+1$, $1+1+2$, and $1+1+1+1$.  Find the smallest $n$ greater than $2013$ for which $f(n)$ is odd.

Solution:
First of all, note that $f(n)$ = $\sum_{i=0}^{k} f(n-2^{i})$ where $k$ is the largest integer such that $2^k \le n$.  We let $f(0) = 1$ for convenience.
From here, we proceed by induction, with our claim being that the only $n$ such that $f(n)$ is odd are $n$ representable of the form $2^{a} - 1, a \in \mathbb{Z}$
We induct on $a$.  It is trivially true for $a = 0$ and $a = 1$.  From here, we show that, if the only numbers $n \le 2^{a-1} - 1$ where $f(n)$ is odd are of the form described above, then the only numbers $n \le 2^{a} -1$ that are odd are of that form.  We first consider all numbers $b$, such that $2^{a-1} \le b \le 2^{a} - 2$, going from the lower bound to the upper bound (a mini induction, you might say).  We know that $f(b) = \sum_{i=0}^{a-1} f(b-2^{i})$.  For a number in this summation to be odd, $b - 2^i = 2^m -1 \rightarrow b = 2^i + 2^m - 1$.  However, we know that $b > 2^{a-1}$, so $m$ must be equal to $a-1$, or else $b$ cannot be in that interval.  Now, from this, we know that $i < a-1$, as $b<2^{a} - 1$.  Therefore, $i$ and $m$ are distinct, and thus $f(b - 2^i)$ and $f(b- 2^{a-1})$ are odd; since there are just two odd numbers, the ending sum for any $b$ is even.  Finally, considering $2^{a} - 1$, the only odd number is $f(2^{a} - 1 - 2^{a-1})$, so the ending sum is odd.  $\Box$
The smallest $n$ greater than $2013$ expressible as $2^d - 1, d \in \mathbb{N}$ is $2^{11} -1 = \boxed{2047}$

Of course, as with any number theory problem, use actual numbers to start, not variables! By plotting out the first few sums (do it!) and looking for patterns, we observe that $f(n)=\sum_{\textrm{power}=0}^{\textrm{pow}_{\textrm{larg}}} f(n-2^{\textrm{power}})$, where $\textrm{pow}_{\textrm{larg}}$ represents the largest power of $2$ that is smaller than $n$. I will call this sum the Divine Sign, or DS.
But wait a minute... we are trying to determine odd/even of $f(n)$. Why not call all the evens 0 and odds 1, basically using mod 2? Sounds so simple. Draw a small table for the values: as $n$ goes up from $0$, you get: $1,1,0,1,0,0,0,1,0...$. We have to set $f(0)=1$ for this to work. Already it looks like $f(n)$ is only odd if $n=2^{\textrm{power}}-1$.
The only tool here is induction. The base case is clearly established. Then let's assume we successfully made our claim up to $2^n-1$. We need to visit numbers from $2^n$ to $2^{n+1}-1$. Realize that $2^n$ has $0$ for $f$ because there will be two numbers in DS that give a $f$ of one: $2^{n-1}$ and $1$.
But to look at whether a value of $f(\textrm{number})$ is 1 or 0, we need to revisit our first equation. We can answer this rather natural question: When will a number to be inducted upon, say $2^n+k$, ever have a 1 as $f(\textrm{number})$ in the DS equation? Well- because by our assumption of the claim up to $2^n-1$, we know that the only way for that to happen is if $2^n+k-2^{\textrm{power}}$ in the DS is equal to $2^{\textrm{Some power}} - 1$. Clearly $1 \leq k \leq 2^n - 1$.
Finally, we can simplify. Using our last equation, $2^n+k-2^{\textrm{power}}=2^{\textrm{Some power}}-1$, regrouping gives $2^n+k=2^{\textrm{power}}+2^{\textrm{Some power}}-1$.
Most importantly, realize that $\textrm{power}$ can be from $0$ to $n$, because of the restraints on $k$ mentioned earlier. Same with $\textrm{Some power}$. Immediately at least one of $\textrm{power}$ and $\textrm{Some power}$ has to be $n$. If both were smaller, LHS is greater, contradiction. If both were greater, RHS is greater, contradiction.
Therefore, by setting one of $\textrm{power}$ or $\textrm{Some power}$ to $n$, we realize $k=2^{\textrm{A certain power}}-1$.
The conclusion is clear, right? Each $k$ from $1$ to $2^{n-1}-1$ yields two distinct cases: one of $\textrm{power}$ and $\textrm{Some power}$ is equal to $n$, while the other is LESS THAN $n$. But for $k=2^n-1$, there is ONE CASE: BOTH values have to equal $n$. Therefore, the only $k$ that has $f(2^n+k)$ as odd must only be $2^n-1$, because the other ones yield a $f$ of 1+1=0 in our mod. That proves our induction for a new power of 2, namely $n+1$, meaning that $f(\textrm{number})$ is only odd if $\textrm{number} = 2^{\textrm{Power of two}} - 1$, and we are almost done...
Thus, the answer is $2^{11}-1=\boxed{2047}$.
This was pretty intuitive, and realizing quite $elementary$ steps about how powers of 2 work gave us the solution! Estimated time: ~50 minutes.
~expiLnCalc.
minor edits ~mathboy100
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Quadrilateral $XABY$ is inscribed in the semicircle $\omega$ with diameter $XY$.  Segments $AY$ and $BX$ meet at $P$.  Point $Z$ is the foot of the perpendicular from $P$ to line $XY$.  Point $C$ lies on $\omega$ such that line $XC$ is perpendicular to line $AZ$.  Let $Q$ be the intersection of segments $AY$ and $XC$.  Prove that

Solution:
Using the Law of Sines and simplifying, we have
It is easy to see that $APZX$ is cyclic. Also, we are given $XQ\perp AZ$. Then we have
 and we are done.

Let us use coordinates. Let O, the center of the circle, be (0,0). WLOG the radius of the circle is 1, so set Y (1,0) and X (-1,0). Also, for arbitrary constants $a$ and $b$ set A $(\cos a, \sin a)$ and B $(\cos b, \sin b)$. Now, let's use our coordinate tools. It is easily derived that the equation of $BX$ is $y = \frac{\sin b}{1 + \cos b}(x + 1) = v(x+1)$ and the equation of $AY$ is $y = \frac{\sin a}{1 - \cos a}(x - 1) = u(x-1)$, where $u$ and $v$ are defined appropriately. Thus, by equating the y's in the equation we find the intersection of these lines, $P$, is $\left(\frac{u-v}{u+v}\right), \frac{2uv}{u+v})$. Also, $Z\left(\frac{u-v}{u+v}\right), 0)$. It shall be left to the reader to find the slope of $AZ$, the coordinates of Q and C, and use the distance formula to verify that $\frac{BY}{XP} + \frac{CY}{XQ} = \frac{AY}{AX}$.

First of all
since the quadrilateral $APZX$ is cyclic, and triangle $AXQ$ is rectangle, and $CX$ is orthogonal to $AZ$. Now
because $XABY$ is cyclic and we have proved that
so $BC$ is parallel to $AY$, and  Now by Ptolomey's theorem on $APZX$ we have  we see that triangles $PXZ$ and $QXA$ are similar since  and  is already proven, so  Substituting yields  dividing by $(PX)(XZ)$ We get  Now triangles $AYZ$, and $XYP$ are similar so  but also triangles $XPY$ and $XZB$ are similar and we get  Comparing we have,  Substituting,  Dividing the new relation by $AX$ and multiplying by $XB$ we get  but  since triangles $AXB$ and $QXY$ are similar, because  and  since $CY=AB$ Substituting again we get  Now since triangles $ACQ$ and $XYQ$ are similar we have  and by the similarity of $APB$ and $XPY$, we get  so substituting, and separating terms we get  In the beginning we prove that $AC=BY$ and $AB=CY$ so
$\blacksquare$

It is obvious that

for some value $\alpha$. Also, note that $\angle BYA=\alpha$. Set

We have

and

This gives

Similarly, we can deduce that

Adding gives

First, since $XY$ is the diameter and $A$, $B$, and $C$ lie on the circle, . Next, because $AZ$ and $CY$ are both perpendicular to $CX$, we have $AZ$ to be parallel to $CY$.
Now looking at quadrilateral $APZX$, we see that this is cyclic because  Set $\alpha = \angle{BXA} = \angle{BYA}$, and $\beta = \angle{BXC} = \angle{BYC}$.
Now,  since $AZ$ and $CY$ are parallel.
Also,
That means  so  This means $\angle{QXZ} = \angle{YBC} = \alpha$, so $BC$ and $AY$ are parallel.
Finally, we can look at the equation.
We know  so $XP = \frac{AX}{\cos{\alpha}}.$
We also know  so $XQ = \frac{AX}{\cos(\alpha+\beta)}.$
Plugging this into the LHS of the equation, we get
Now, let $H$ be the point on $AY$ such that $BH$ is perpendicular to $AY$. Also, since $\angle{AYB} = \angle{CXY}$, their arcs have equal length, and $AB=CY$.
Now, the LHS is simplified even more to  which is equal to  which is equal to  This completes the proof.
~jeteagle
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Find all real numbers $x,y,z\geq 1$ satisfying

Without loss of generality, let $1 \le x \le y \le z$. Then $\sqrt{x + xyz} = \sqrt{x - 1} + \sqrt{y - 1} + \sqrt{z - 1}$.
Suppose x = y = z. Then $\sqrt{x + x^3} = 3\sqrt{x-1}$, so $x + x^3 = 9x - 9$. It is easily verified that $x^3 - 8x + 9 = 0$ has no solution in positive numbers greater than 1. Thus, $\sqrt{x + xyz} \ge \sqrt{x - 1} + \sqrt{y - 1} + \sqrt{z - 1}$ for x = y = z. We suspect if the inequality always holds.
Let x = 1. Then we have $\sqrt{1 + yz} \ge \sqrt{y-1} + \sqrt{z-1}$, which simplifies to  and hence  Let us try a few examples: if y = z = 2, we have $3 > 2$; if y = z, we have $y^2 - 2y + 3 \ge 2(y-1)$, which reduces to $y^2 - 4y + 5 \ge 0$. The discriminant (16 - 20) is negative, so in fact the inequality is strict. Now notice that yz - y - z + 3 = (y-1)(z-1) + 2. Now we see we can let $u = \sqrt{(y-1)(z-1)}$! Thus,  and the claim holds for x = 1.
If x > 1, we see the $\sqrt{x - 1}$ will provide a huge obstacle when squaring. But, using the identity $(x+y+z)^2 = x^2 + y^2 + z^2 + xy + yz + xz$:

which leads to

Again, we experiment. If x = 2, y = 3, and z = 3, then $18 > 7 + 4\sqrt{6}$.
Now, we see the finish: setting $u = \sqrt{x-1}$ gives $x = u^2 + 1$. We can solve a quadratic in u! Because this problem is a #6, the crown jewel of USAJMO problems, we do not hesitate in computing the messy computations:
Because the coefficient of $u^2$ is positive, all we need to do is to verify that the discriminant is nonpositive:
Let us try a few examples. If y = z, then the discriminant D = $8(y-1) - 8(y-1) - yz(12 + 4y^2 - 8y - 8(y-1)) = -yz(4y^2 - 16y + 20) = -4yz(y^2 - 4y + 5) < 0$.
We are almost done, but we need to find the correct argument. (How frustrating!)
Success! The discriminant is negative. Thus, we can replace our claim with a strict one, and there are no real solutions to the original equation in the hypothesis.
--Thinking Process by suli


Let $a$, $b$, $c$ be real numbers greater than or equal to $1$. Prove that

Solution:
Since $(a-1)^5\ge 0$,

or

Since $a^2-5a+10=\left( a-\dfrac{5}{2}\right)^2 +\dfrac{15}{4}>0$,

Also note that $10a^2-5a+1=10\left( a-\dfrac{1}{4}\right)^2+\dfrac{3}{8}> 0$,
We conclude

Similarly,

So
or

Therefore,


Let $\triangle{ABC}$ be a non-equilateral, acute triangle with $\angle A=60^{\circ}$, and let $O$ and $H$ denote the circumcenter and orthocenter of $\triangle{ABC}$, respectively.
(a) Prove that line $OH$ intersects both segments $AB$ and $AC$.
(b) Line $OH$ intersects segments $AB$ and $AC$ at $P$ and $Q$, respectively. Denote by $s$ and $t$ the respective areas of triangle $APQ$ and quadrilateral $BPQC$. Determine the range of possible values for $s/t$.

Solution:
Lemma: $H$ is the reflection of $O$ over the angle bisector of $\angle BAC$ (henceforth 'the' reflection)
Proof: Let $H'$ be the reflection of $O$, and let $B'$ be the reflection of $B$.
Then reflection takes $\angle ABH'$ to $\angle AB'O$.
$\Delta ABB'$ is equilateral, and $O$ lies on the perpendicular bisector of $\overline{AB}$
It's well known that $O$ lies strictly inside $\Delta ABC$ (since it's acute), meaning that $\angle ABH' = \angle AB'O = 30^{\circ},$ from which it follows that $\overline{BH'} \perp \overline{AC}$ . Similarly,  $\overline{CH'} \perp \overline{AB}$. Since $H'$ lies on two altitudes, $H'$ is the orthocenter, as desired.
End Lemma
So $\overline{OH}$ is perpendicular to the angle bisector of $\angle OAH$, which is the same line as the angle bisector of $\angle BAC$, meaning that $\Delta APQ$ is equilateral.
Let its side length be $s$, and let $PH=t$, where $0 < t < s, t \neq s/2$ because $O$ lies strictly within $\angle BAC$, as must $H$, the reflection of $O$. Also, it's easy to show that if $O=H$ in a general triangle, it's equilateral, and we know $\Delta ABC$ is not equilateral. Hence H is not on the bisector of $\angle BAC \implies t \neq s/2$. Let $\overrightarrow{BH}$ intersect $\overline{AC}$ at $P_B$.
Since $\Delta HP_BQ$ and $BP_BA$ are 30-60-90 triangles, $AB=2AP_B=2(s-QP_B)=2(s-HQ/2)=2s-HQ=2s-(s-t)=s+t$
Similarly, $AC=2s-t$
The ratio $\frac{[APQ]}{[ABC]-[APQ]}$ is $\frac{AP \cdot AQ}{AB \cdot AC - AP \cdot AQ} = \frac{s^2}{(s+t)(2s-t)-s^2}$
The denominator equals $(1.5s)^2-(.5s-t)^2-s^2$ where $.5s-t$ can equal any value in $(-.5s, .5s)$ except $0$. Therefore, the denominator can equal any value in $(s^2, 5s^2/4)$, and the ratio is any value in $\boxed{\left(\frac{4}{5},1\right)}.$
Note: It's easy to show that for any point $H$ on $\overline{PQ}$ except the midpoint, Points B and C can be validly defined to make an acute, non-equilateral triangle.

Let $J$ be the farthest point on the circumcircle of $\triangle{ABC}$ from line $BC$.
Lemma: Line $AJ$||Line $OH$
Proof: Set $b=-\dfrac{1}{2}+i\dfrac{\sqrt{3}}{2}$ and $c=-\dfrac{1}{2}-i\dfrac{\sqrt{3}}{2}$, and $a$ on the unit circle. It is well known that $o=0$ and $h=a+b+c$, so we have $h-o=a+b+c=a-1=a-j$, so $\dfrac{a-j}{h-o}$ is real and thus the 2 lines are parallel.
WLOG let $A$ be in the first quadrant. Clearly by the above lemma $OH$ must intersect line $BC$ closer to $B$ than to $C$. Intersect $AJ$ and $BC$ at $D$ and $OH$ and $BC$ at $E$. We clearly have $0 < \dfrac{\overarc{JC}-\overarc{AB}}{2} = \dfrac{120-\overarc{AC}}{2} = \angle{ADB} = \angle{OEC} < 30 = \angle{OBC}$, $OH$ must intersect $AB$. We also have, letting the intersection of line $OH$ and line $AC$ be $Q$, and letting intersection of $OH$ and $AB$ be $P$, $\angle{OQA} = \angle{JAB} = \dfrac{\overarc{JB}}{2} = 60$. Since $\angle{OCA}=\angle{BCA}-\angle{BCO} < 90-30 =\angle{OQA}$, and $\angle{OQC} = 120>\angle{OAC}$, $OH$ also intersects $AC$. We have $\angle{OPA}=\angle{PAJ}=60$, so $\triangle{APQ}$ is equilateral. Letting $AJ=2x$, and letting the foot of the perpendicular from $O$ to $AJ$ be $L$, we have $OL=\sqrt{1-x^{2}}$, and since $OL$ is an altitude of $\triangle{APQ}$, we have $[APQ]=\dfrac{OL^{2}\sqrt{3}}{3} = \dfrac{\sqrt{3}(1-x^{2})}{3}$. Letting the foot of the perpendicular from $A$ to $OJ$ be $K$, we have $\triangle{JKA}\sim \triangle{JLO}$ by AA with ratio $\dfrac{JA}{JO} = 2x$. Therefore, $JK = 2x(JL) = 2x^{2}$. Letting $D$ be the foot of the altitude from $J$ to $BC$, we have $KD=JD-JK=\dfrac{3}{2}-2x^{2}$, since $re(B)=re(C) \implies JD=re(j)-(-\dfrac{1}{2})=\dfrac{3}{2}$. Thus, since $BC=\sqrt{3}$ we have $[ABC]=\dfrac{(\dfrac{3}{2}-2x^{2})(\sqrt{3})}{2} = \dfrac{(3-4x^{2})(\sqrt{3})}{2}$, so $[PQCB]=[ABC]-[APQ]=\dfrac{(5-8x^{2})(\sqrt{3})}{12}$, so $\dfrac{[APQ]}{[PQCB]} = \dfrac{4-4x^{2}}{5-8x^{2}} = \dfrac{1}{2}+\dfrac{3}{10-16x^{2}}$. We have $x=\sin(\dfrac{JOA}{2})$, with $0<120-2\angle{ACB}=\angle{JOA}<60$, so $x$ can be anything in the interval $(0, \dfrac{1}{2})$. Therefore, the desired range is $(\dfrac{4}{5}, 1)$.
Solution by Shaddoll


Let $\mathbb{Z}$ be the set of integers. Find all functions $f : \mathbb{Z} \rightarrow \mathbb{Z}$ such that  for all $x, y \in \mathbb{Z}$ with $x \neq 0$.

Solution:
Note: This solution is kind of rough. I didn't want to put my 7-page solution all over again. It would be nice if someone could edit in the details of the expansions.
Lemma 1: $f(0) = 0$.
Proof: Assume the opposite for a contradiction. Plug in $x = 2f(0)$ (because we assumed that $f(0) \neq 0$), $y = 0$. What you get eventually reduces to:

which is a contradiction since the LHS is divisible by 2 but not 4.
Then plug in $y = 0$ into the original equation and simplify by Lemma 1. We get:

Then:

Therefore, $f(x)$ must be 0 or $x^2$.
Now either $f(x)$ is $x^2$ for all $x$ or there exists $a \neq 0$ such that $f(a)=0$. The first case gives a valid solution. In the second case, we let $y = a$ in the original equation and simplify to get:

But we know that $xf(-x) = \frac{f(x)^2}{x}$, so:

Since $a$ is not 0, $f(2x)$ is 0 for all $x$ (including 0). Now either $f(x)$ is 0 for all $x$, or there exists some $m \neq 0$ such that $f(m) = m^2$. Then $m$ must be odd. We can let $x = 2k$ in the original equation, and since $f(2x)$ is 0 for all $x$, stuff cancels and we get:

for $\mathbf{k \neq 0}$.
Now, let $y = m$ and we get:

Now, either both sides are 0 or both are equal to $m^6$. If both are $m^6$ then:

which simplifies to:

Since $k \neq 0$ and $m$ is odd, both cases are impossible, so we must have:

Then we can let $k$ be anything except 0, and get $f(x)$ is 0 for all $x \equiv 3 \pmod{4}$ except $-m^2$.  Also since $x^2f(-x) = f(x)^2$, we have $f(x) = 0 \Rightarrow f(-x) = 0$, so $f(x)$ is 0 for all $x \equiv 1 \pmod{4}$ except $m^2$. So $f(x)$ is 0 for all $x$ except $\pm m^2$. Since $f(m) \neq 0$, $m = \pm m^2$. Squaring, $m^2 = m^4$ and dividing by $m$, $m = m^3$. Since $f(m^3) = 0$, $f(m) = 0$, which is a contradiction for $m \neq 1$. However, if we plug in $x = 1$ with $f(1) = 1$ and $y$ as an arbitrary large number with $f(y) = 0$ into the original equation, we get $0 = 1$ which is a clear contradiction, so our only solutions are $f(x) = 0$ and $f(x) = x^2$.

Given that the range of f consists entirely of integers, it is clear that the LHS must be an integer and $f(yf(y))$ must also be an integer, therefore $\frac{f(x)^2}{x}$ is an integer. If $x$ divides $f(x)^2$ for all integers $x \ne 0$, then $x$ must be a factor of $f(x)$, therefore $f(0)=0$. Now, by setting $y=0$ in the original equation, this simplifies to $xf(-x)=\frac{f(x)^2}{x}$. Assuming $x \ne 0$, we have $x^2f(-x)=f(x)^2$. Substituting in $-x$ for $x$ gives us $x^2f(x)=f(-x)^2$. Substituting in $\frac{f(x)^2}{x^2}$ in for $f(-x)$ in the second equation gives us $x^2f(x)=\frac{f(x)^4}{x^4}$, so $x^6f(x)=f(x)^4$. In particular, if $f(x) \ne 0$, then we have $f(x)^3=x^6$, therefore $f(x)$ is equivalent to $0$ or $x^2$ for every integer $x$. Now, we shall prove that if for some integer $t \ne 0$, if $f(t)=0$, then $f(x)=0$ for all integers $x$. If we assume $f(y)=0$ and $y \ne 0$ in the original equation, this simplifies to $xf(-x)+y^2f(2x)=\frac{f(x)^2}{x}$. However, since $x^2f(-x)=f(x)^2$, we can rewrite this equation as $\frac{f(x)^2}{x}+y^2f(2x)=\frac{f(x)^2}{x}$, $y^2f(2x)$ must therefore be equivalent to $0$. Since, by our initial assumption, $y \ne 0$, this means that $f(2x)=0$, so, if for some integer $y \ne 0$, $f(y)=0$, then $f(x)=0$ for all integers $x$. The contrapositive must also be true, i.e. If $f(x) \ne 0$ for all integers $x$, then there is no integral value of $y \ne 0$ such that $f(y)=0$, therefore $f(x)$ must be equivalent for $x^2$ for every integer $x$, including $0$, since $f(0)=0$. Thus, $f(x)=0, x^2$ are the only possible solutions.

Let's assume $f(0)\neq 0.$ Substitute $(x,y)=(2f(0),0)$ to get
This means that $2(2f(0)-1)$ is a perfect square. However, this is impossible, as it is equivalent to $2\pmod{4}.$ Therefore, $f(0)=0.$ Now substitute $x\neq 0, y=0$ to get
Similarly,
From these two equations, we can find either $f(x)=f(-x)=0,$ or $f(x)=f(-x)=x^2.$ Both of these are valid solutions on their own, so let's see if there are any solutions combining the two.
Let's say we can find $f(x)=x^2, f(y)=0,$ and $x,y\neq 0.$ Then
 (NEEDS FIXING: $f(x)^2/x= x^4/x = x^3$, so the RHS is $0$ instead of $x-x^3$.)
If $f(2x)=4x^2,$ then $y^2=\frac{x-x^3}{4x^2}=\frac{1-x^2}{4x},$ which is only possible when $y=0.$ This contradicts our assumption. Therefore, $f(2x)=0.$ This forces $x=\pm 1$ due to the right side of the equation. Let's consider the possibility $f(2)=0, f(1)=1.$ Substituting $(x,y)=(2,1)$ into the original equation yields   which is impossible. So $f(2)=f(-2)=4$ and there are no solutions "combining" $f(x)=x^2$ and $f(x)=0.$
Therefore our only solutions are $\boxed{f(x)=0}$ and $\boxed{f(x)=x^2.}$

Let the given assertion be $P(x, y)$. We try $P(x, 0)$ and get $xf(2c-x)=f(x)^2/x+c$, where $f(0)=c$. We plug in $x=c$ and get $cf(c)=f(c)^2/c+c$. Rearranging and solving for $c^2$ gives us $c^2=\frac{f(c)^2}{f(c)-1}$. Obviously, the only $c$ that works such that the RHS is an integer is $c=0$, and thus $f(0)=0$.
We use this information on assertion $P(x,0)$ and obtain $xf(-x)=f(x^2)/x$, or $f(-x)=\frac{f(x)^2}{x^2}$. Thus, $f(x)$ is an even function. It follows that $f(x)=0, x^2$ for each $x$. We now prove that $f(x)=x^2$, f(x)=0$ are the only solutions. [in progress] ~SigmaPiE


Let $b\geq 2$ be an integer, and let $s_b(n)$ denote the sum of the digits of $n$ when it is written in base $b$.  Show that there are infinitely many positive integers that cannot be represented in the form $n+s_b(n)$, where $n$ is a positive integer.

Define $S(n) = n + s_b(n)$, and call a number unrepresentable if it cannot equal $S(n)$ for a positive integer $n$.
We claim that in the interval $(b^p, b^{p+1}]$ there exists an unrepresentable number, for every positive integer $p$.
If $b^{p+1}$ is unrepresentable, we're done. Otherwise, time for our lemma:
Lemma: Define the function $f(p)$ to equal the number of integers x less than $b^p$ such that $S(x) \ge b^p$. If $b^{p+1} = S(y)$ for some y, then $f(p+1) > f(p)$.
Proof: Let $F(p)$ be the set of integers x less than $b^p$ such that $S(x) \ge b^p$. Then for every integer in $F(p)$, append the digit $(b-1)$ to the front of it to create a valid integer in $F(p+1)$. Also, notice that $(b-1) \cdot b^p \le y < b^{p+1}$. Removing the digit $(b-1)$ from the front of y creates a number that is not in $F(p)$. Hence, $F(p) \rightarrow F(p+1)$, but there exists an element of $F(p+1)$ not corresponding with $F(p)$, so $f(p+1) > f(p)$.
Note that our lemma combined with the Pigeonhole Principle essentially proves the claim. Therefore, because there are infinitely many disjoint intervals containing an unrepresentable number, there are infinitely many unrepresentable numbers.

Let $f(n) = n + s_b(n)$. It is easy to see that $f(b^2) = b^2 + 1$, and $f(b^2 - b + 1) = b^2 - b + 1 + b - 1 + 1 = b^2 + 1$, because the digits of $b^2 - b + 1$ are $b-1$ and $1$. Additionally, if we take any number, let's say $x$, and multiply it by $b^3$, and then add it to $b^2$ and $b^2 - b + 1$, we still obtain $f(b^3x + b^2) = f(b^3x + b^2 - b + 1)$, because we are simply adding $b^3x + x$ to each value.
Thus, we conclude that there are infinitely many numbers that are counted twice in $f(n)$, and that these numbers come $x^3$ apart. Finally, it is clear that for a large $N$, the number of numbers that are counted at least twice is at least $\left\lfloor\frac{N}{x^3}\right\rfloor$. Because $f(n) > n$ for all $n$, this means that there are at least $\left\lfloor\frac{N}{x^3}\right\rfloor$ numbers uncounted, and because this is unbounded, the proof is complete.
~mathboy100


Let $k$ be a positive integer. Two players $A$ and $B$ play a game on an infinite grid of regular hexagons. Initially all the grid cells are empty. Then the players alternately take turns with $A$ moving first. In his move, $A$ may choose two adjacent hexagons in the grid which are empty and place a counter in both of them. In his move, $B$ may choose any counter on the board and remove it. If at any time there are $k$ consecutive grid cells in a line all of which contain a counter, $A$ wins. Find the minimum value of $k$ for which $A$ cannot win in a finite number of moves, or prove that no such minimum value exists.

Solution:
The answer is $k=6$. We prove that $A$ can win for $k=5$ (which hence proves it for $k<5$ as well) and show that $B$ can thwart $A$ for $k\geq 6$.
Arrange the board so that a pair of opposite sides are horizontal. Create a coordinate system on the board by setting the center of some hexagon as the origin and setting the hexagons directly above and above-and-right as $(0, 1)$ and $(1, 0)$, respectively. Then, for example, the below-and-right hexagon touching the origin is $(1, -1)$. So two hexagons touch if their coordinate difference is one of these.
Now for $k=5$, person $A$ places his counters only in $\{0, 1, 2, 3, 4\}\times\{0, 1\}$. Note that if, at $A$'s turn, there are 4 counters in either column, then $A$ can win immediately, so let us assume that in both columns there are at least 2 missing, meaning that at most $6$ counters are on the board. We would like to find when $A$ cannot play under these circumstances. If we look at the disjoint sets
$\{(0, 0), (0, 1), (1, 0)\}, \{(1, 1), (2, 0), (2, 1)\}, \{(3, 0), (3, 1), (4, 0)\}, \{(4, 1)\}$
we see that either some set has at least $2$ hexagons without counters, in which case $A$ can move, or all four sets have exactly $1$ missing counter. Similarly for the sets
$\{(0, 0)\}, \{(0, 1), (1, 0), (1, 1)\}, \{(2, 0), (2, 1), (3, 0)\}, \{(3, 1), (4, 0), (4, 1)\}$
So both $(0, 0), (4, 1)$ have no token on them. This means that $(0, 1), (1, 0), (3, 1), (4, 0)$ do. Thus $(3, 0)$ and $(1, 1)$ do not. So this is the only situation in which $A$ can neither win immediately nor play in only these 10 hexagons.
So $A$ plays only in these 10 hexagons until either he has a win or he can't anymore. If he wins, then we're done. Otherwise, $A$ plays in hexagons $(5, 0)$ and $(5, 1)$. Then $B$ either removes $(5, 1)$ so that $A$ can win at $(2, 0)$, or $B$ removes $(5, 0)$ and $A$ plays at $(5, 0)$ and $(4, 1)$ and then at either $(3, 0)$ or $(1, 1)$ the next turn, or $B$ removes one of $\{0, 1, 2, 3, 4\}\times\{0, 1\}$ in which case $A$ can either win immediately at $(3, 0)$ or can play in both columns, and then win the next turn.
Now if $k\geq 6$, then if $A$ plays on anything in the lattice generated by $(2, -1)$ and $(1, 1)$, that is $(2a+b, b-a)$ for $a, b$ integers, then $B$ removes it. Otherwise, $B$ removes any of $A$'s counters. This works because in order for $A$ to win, there must be at least 2 counters in this lattice, but $A$ can only put a counter on $1$ at any time, so there's at most 1 on the lattice at any time.
So $A$ wins if $k\leq 5$, and $B$ wins if $k\geq 6$.