Let $ABC$ be a triangle with incenter $I$, incircle $\gamma$ and circumcircle $\Gamma$.  Let $M,N,P$ be the midpoints of sides $\overline{BC}$, $\overline{CA}$, $\overline{AB}$ and let $E,F$ be the tangency points of $\gamma$ with $\overline{CA}$ and $\overline{AB}$, respectively.  Let $U,V$ be the intersections of line $EF$ with line $MN$ and line $MP$, respectively, and let $X$ be the midpoint of arc $BAC$ of $\Gamma$.
(a) Prove that $I$ lies on ray $CV$.
(b) Prove that line $XI$ bisects $\overline{UV}$.

Solution:
(a)
Solution 1: We will prove this via contradiction: assume that line $IC$ intersects line $MP$ at $Q$ and line $EF$ and $R$, with $R$ and $Q$ not equal to $V$. Let $x = \angle A/2 = \angle IAE$ and $y = \angle C/2 = \angle ICA$. We know that $\overline{MP} \parallel \overline{AC}$ because $MP$ is a midsegment of triangle $ABC$; thus, by alternate interior angles (A.I.A) $\angle MVE = \angle FEA = (180^\circ - 2x) / 2 = 90^\circ - x$, because triangle $AFE$ is isosceles. Also by A.I.A, $\angle MQC = \angle QCA = y$. Furthermore, because $AI$ is an angle bisector of triangle $AFE$, it is also an altitude of the triangle; combining this with $\angle QIA = x + y$ from the Exterior Angle Theorem gives $\angle FRC = 90 - x - y$. Also, $\angle VRQ = \angle FRC = 90 - x - y$ because they are vertical angles. This completes part (a).
Solution 2: First we show that the intersection $V'$of $MP$ with the internal angle bisector of $C$ is the same as the intersection $V''$ of $EF$ with the internal angle bisector of $C.$ Let $D$ denote the intersection of $AB$ with the internal angle bisector of $C,$ and let $a,b,c$ denote the side lengths of $BC, AC, AB.$ By Menelaus on $V'', F, E,$ with respect to $\triangle ADC,$
 Similarly,   Since $V'$ and $V''$ divide $CD$ in the same ratio, they must be the same point. Now, since $\frac{b-a}{b+a}>-1,$ $I$ lies on ray $CV.$ $\blacksquare$
Solution 3: By the Iran Lemma, we know $CI, EF, MP$ concur, so Part $\text{A}$ follows easily.
(b)
Solution 1: Using a similar argument to part (a), point U lies on line $BI$. Because $\angle MVC = \angle VCA = \angle MCV$, triangle $VMC$ is isosceles. Similarly, triangle $BMU$ is isosceles, from which we derive that $VM = MC = MB = MU$. Hence, triangle $VUM$ is isosceles.
Note that $X$ lies on both the circumcircle and the perpendicular bisector of segment $BC$. Let $D$ be the midpoint of $UV$; our goal is to prove that points $X$, $D$, and $I$ are collinear, which equates to proving $X$ lies on ray $ID$.
Because $MD$ is also an altitude of triangle $MVU$, and $MD$ and $IA$ are both perpendicular to $EF$, $\overline{MD} \parallel \overline{IA}$. Furthermore, we have $\angle VMD = \angle UMD = x$ because $APMN$ is a parallelogram. (incomplete)
Solution 2: Let $I_A$, $I_B$, and $I_C$ be the excenters of $ABC$. Note that the circumcircle of $ABC$ is the nine-point circle of $I_AI_BI_C$. Since $AX$ is the external angle bisector of $\angle BAC$, $X$ is the midpoint of $I_BI_C$. Now $UV$ and $I_BI_C$ are parallel since both are perpendicular to the internal angle bisector of $\angle BAC$. Since $IX$ bisects $I_BI_C$, it bisects $UV$ as well.
Solution 3: Let $X'$ be the antipode of $X$ with respect to the circumcircle of triangle $ABC$. Then, by the Incenter-Excenter lemma, $X'$ is the center of a circle containing $B$, $I$, and $C$. Because $XX'$ is a diameter, $XB$ and $XC$ are tangent to the aforementioned circle; thus by a well-known symmedian lemma, $XI$ coincides with the $I$-symmedian of triangle $IBC$. From part (a); we know that $BVUC$ is cyclic (we can derive a similar argument for point $U$); thus $XI$ coincides with the median of triangle $VIU$, and we are done.
Solution 4: Let $M_b, M_c$ be the midpoints of arcs $CA, AB$ respectively, and let $T_a$ be the tangency point between the $A$-mixtilinear incircle of $ABC$ and $\Gamma$. It's well-known that $T_a \in XI$, $T_aX$ bisects $M_bM_c$, $AI \perp EF$, and $AI \perp M_bM_c$.
Now, it's easy to see $EF \parallel M_bM_c$, so $IUV$ and $IM_bM_c$ are homothetic at $I$. But $T_aX \equiv IX$ bisects $M_bM_c$, so Part $\text{B}$ follows directly from the homothety.
~ ike.chen


Given a sequence of real numbers, a move consists of choosing two terms and replacing each with their arithmetic mean. Show that there exists a sequence of $2015$ distinct real numbers such that after one initial move is applied to the sequence -- no matter what move -- there is always a way to continue with a finite sequence of moves so as to obtain in the end a constant sequence.

Solution:
Let the set be ${-1007, -1006, ...0,1,2...1006, 1007}$, namely all the consecutive integers from $-1007$ to $1007$.  Notice that the operation we are applying in this problem does not change the sum or the mean of the set, which is $0$.
There are $1007$ pairs of opposite integers $\{a,-a\}$. After the first two elements are chosen, there are at least $1005$ such pairs. For each such pair we perform the operation of average, hence reducing these $2010$ elements to $0$. Then use the other $5$ elements together with three $0$'s produced to form the group of eight: ${a_1,a_2,a_3,a_4,a_5,a_6=0,a_7=0,a_8=0}$, and perform the operation in the following order:  where $m_i=\frac{a_i+a_{i+1}}{2}$. Then, $(m_1,m_2)\to(m_{11}, m_{11})$ for two groups, $(m_3,m_4)\to(m_{12}, m_{12})$ for the other two groups, and finally $(m_{11},m_{12})\to(m_{111}, m_{111})$ for all the eight elements. Since the sum of the eight-group is $0$, $m_{111}$ must also be $0$. Therefore, all the elements are reduced to $0$.
The key to the algorithm is to form a $2^k$ subset, which is guaranteed to be reducible to all the members of the same value, namely the mean. Then before that, if we could always choose $M\ge N-2^k$ members to form pairs, each yielding the average of the total group, then all the members are reduced to the average. Under the condition that two arbitrary elements are chosen first, we need only $N\ge4$ to guarantee this result. But for $N=2$ the first operation leads to equal elements, so $N=3$ is the only case when all the members may not be reduced to average.
Sidenote: Actually, for $N=3$, the members are all reduced to the average, as the sum of the terms is constant and does not change.

Consider any arithmetic sequence. WLOG, let it be $s = (1, 2, 3, \dots, 2015)$, i.e. $s_i = i\ \forall\ 1\le i\le 2015$. Define the move $(x, y)$ as replacing the numbers located at positions $x$ and $y$ with their mean, assuming $x$ and $y$ are distinct. If they are the same integer, define it as not making a move. Now, suppose the initial move $m_0 = (a, b)$. If $a+b=2016$, then $s_a = s_b = \frac{a+b}{2} = 1008$. Then, applying the moves

we get $s_1 = s_2 = \cdots = s_{2015} = 1008$.
Otherwise, suppose $a+b\ne 2016$. Then consider the following $3$ moves:

We have $m_{-1}$ makes $s_{2016-a} = s_{2016-b} = 2016 - \frac{a+b}{2}$. So, $m_{-2}$ makes

Similarly for $m_{-3}$ with $s_b$ and $s_{2016-b}$. Then, finishing up with the moves

we get $s_1 = s_2 = \cdots = s_{2015} = 1008$.

(95% Sure) Doesn't this solution fail for Case $2$ when $a$ or $b$ is $1008$? (Because $2016-1008 = 1008$ so $m_{-1}$ is basically non-existent.)
- ike.chen

Let the set be ${a_1,a_2,\dots ,a_{2015}}$, where all the terms are nonnegative. Note that the sum of all the terms in this sequence will always be the same after any amount of moves. To prove this, let $i,j$ be integers with $1\le i<j\le 2015$, and we have $a_i+a_j = \frac{a_i+a_j}{2}+\frac{a_i+a_j}{2}$.
Also, $a_ia_j \le (\frac{a_i+a_j}{2})(\frac{a_i+a_j}{2})$ by AM-GM, so the product of all the terms will not decrease after any number of moves. However, the product will only stay the same when $a_i=a_j$, so the product will always increase if $a_i\ne a_j$.
Finally, note that $a_1a_2\dots a_{2015}\le (\frac{a_1+a_2+\dots +a_{2015}}{2015})^{2015}$ by AM-GM, so because $a_1+a_2+\dots +a_{2015}$ is fixed, there is a maximum product that is reached after a finite number of moves as the product increases. This product is reached when $a_1=a_2=\dots =a_{2015}$, so we are done.
This solution is incorrect; the product may take an infinite number of moves to reach the maximum (for example, consider the sequence $1, 3, 4, 5... 2016$)

We claim that the sequence $-1007, -1006, ... ,0, ... , 1006, 1007$ satisifes the conditions
Let the initial pair that we choose to operate on be denoted as $(a, b)$
Case 1: $(a, b)$ $\neq$ $0$
Sub case 1a: if $a + b$ sum to $0$ in this sequence, the pair is really just $(a, -a)$ or $(-a, a)$. If we replace $a$, and $-a$ with their AM then they both become $0$. Notice that for every number in the original sequence, there is either a negative or positive value to that (depending on the sign). So once we convert the initial pair to $0$, we can do so for every other pair, for example let $a_i$ be a number in the sequence, we would operate on $(a_i, -a_i)$ for every number until every number in the sequence becomes $0$. (Note that the amount of operations this would take is finite).
Sub case 1b: If $a + b \neq 0$ then we can use the same logic, but with one extra step. After we do $(a, b)$ as our initial operation, we do $(-a, -b)$. This is equivalent to $(-a, a)$ and $(-b, b)$ which turns all those values into $0$ (this is also the same as comparing $(a+b)/2$ and $(-a-b)/2$ which cancels out). Then since the only values that remain besides $0$ both have a negative/positive counter part, do the same thing in Sub case 1a; $(a_i, -a_i)$ turning the whole sequence to $0$ in a finite number of operations.
Case 2: The inital pair is $(0, b)$
Obviously, there is a $-b$ in the sequence, (this will come into play later). Since $b \neq 0$ our only $0$ vanishes due to the AM, our goal is to make another $0$. Remember that for every number in the original sequence (besides $0$) there is a negative or positive value depending on the numbers sign. So even if $b$ to $-b$ or any other number in the sequence doesn't make $0$, we have another option.
Find any $(a, -a)$ such that $(a + -a) = 0$ (again this is guaranteed to be in the sequence).
Now once you have your $0$s, take the $-b$, and take the AM of that and $0$. Then there will be 2 $-b/2$s. This will make $0$s with our two numbers from $(0, b)$ since that produces 2 $b/2$s. Since those cancel and make $0$, everything else is the same positive negative condition, which finishes. ~dukcrantel

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Solution:
We first notice that both sides must be integers, so $\frac{x+y}{3}$ must be an integer.
We can therefore perform the substitution $x+y = 3t$ where $t$ is an integer.
Then:

$4t+1$ is therefore the square of an odd integer and can be replaced with $(2n+1)^2 = 4n^2 + 4n +1$.
By substituting using $t = n^2 + n$ we get:

Using substitution we get the solutions: $(n^3 + 3n^2 - 1, - n^3 + 3n + 1) \cup ( - n^3 + 3n + 1, n^3 + 3n^2 - 1)$


Quadrilateral $APBQ$ is inscribed in circle $\omega$ with $\angle P = \angle Q = 90^{\circ}$ and $AP = AQ < BP$. Let $X$ be a variable point on segment $\overline{PQ}$. Line $AX$ meets $\omega$ again at $S$ (other than $A$). Point $T$ lies on arc $AQB$ of $\omega$ such that $\overline{XT}$ is perpendicular to $\overline{AX}$. Let $M$ denote the midpoint of chord $\overline{ST}$. As $X$ varies on segment $\overline{PQ}$, show that $M$ moves along a circle.

We will use coordinate geometry.
Without loss of generality,
let the circle be the unit circle centered at the origin,
,
where $(1-a)^2+b^2=1$.
Let angle $\angle XAB=A$, which is an acute angle, $\tan{A}=t$, then $X=(1-a,at)$.
Angle $\angle BOS=2A$, $S=(-\cos(2A),\sin(2A))$.
Let $M=(u,v)$, then $T=(2u+\cos(2A), 2v-\sin(2A))$.
The condition $TX \perp AX$ yields: $(2v-\sin(2A)-at)/(2u+\cos(2A)+a-1)=\cot A.$     (E1)
Use identities $(\cos A)^2=1/(1+t^2)$,  $\cos(2A)=2(\cos A)^2-1= 2/(1+t^2) -1$, $\sin(2A)=2\sin A\cos A=2t^2/(1+t^2)$, we obtain $2vt-at^2=2u+a$.   (E1')
The condition that $T$ is on the circle yields $(2u+\cos(2A))^2+ (2v-\sin(2A))^2=1$, namely $v\sin(2A)-u\cos(2A)=u^2+v^2$.   (E2)
$M$ is the mid-point on the hypotenuse of triangle $STX$, hence $MS=MX$, yielding $(u+\cos(2A))^2+(v-\sin(2A))^2=(u+a-1)^2+(v-at)^2$.   (E3)
Expand (E3), using (E2) to replace $2(v\sin(2A)-u\cos(2A))$ with $2(u^2+v^2)$, and using (E1') to replace $a(-2vt+at^2)$ with $-a(2u+a)$, and we obtain
$u^2-u-a+v^2=0$, namely $(u-\frac{1}{2})^2+v^2=a+\frac{1}{4}$, which is a circle centered at $(\frac{1}{2},0)$ with radius $r=\sqrt{a+\frac{1}{4}}$.

Let the midpoint of $AO$ be $K$. We claim that $M$ moves along a circle with radius $KP$.
We will show that $KM^2 = KP^2$, which implies that $KM = KP$, and as $KP$ is fixed, this implies the claim.
$KM^2 = \frac{AM^2+OM^2}{2}-\frac{AO^2}{4}$ by the median formula on $\triangle AMO$.
$KP^2 = \frac{AP^2+OP^2}{2}-\frac{AO^2}{4}$ by the median formula on $\triangle APO$.
$KM^2-KP^2 = \frac{1}{2}(AM^2+OM^2-AP^2-OP^2)$.
As $OP = OT$, $OP^2-OM^2 = MT^2$ from right triangle $OMT$. $(1)$
By $(1)$, $KM^2-KP^2 = \frac{1}{2}(AM^2-MT^2-AP^2)$.
Since $M$ is the circumcenter of $\triangle XTS$, and $MT$ is the circumradius, the expression $AM^2-MT^2$ is the power of point $A$ with respect to $(XTS)$. However, as $AX*AS$ is also the power of point $A$ with respect to $(XTS)$, this implies that $AM^2-MT^2=AX*AS$. $(2)$
By $(2)$, $KM^2-KP^2 = \frac{1}{2}(AX*AS-AP^2)$
Finally, $\triangle APX \sim \triangle ASP$ by AA similarity ($\angle XAP = \angle SAP$ and $\angle APX = \angle AQP = \angle ASP$), so $AX*AS = AP^2$. $(3)$
By $(3)$, $KM^2-KP^2=0$, so $KM^2=KP^2$, as desired. $QED$


Find all functions $f:\mathbb{Q}\rightarrow\mathbb{Q}$ such thatfor all rational numbers $x<y<z<t$ that form an arithmetic progression. ($\mathbb{Q}$ is the set of all rational numbers.)

According to the given, $f(x-a)+f(x+0.5a)=f(x-0.5a)+f(x)$, where x and a are rational. Likewise $f(x-0.5a)+f(x+a)=f(x+0.5a)+f(x)$. Hence $f(x+a)-f(x)= f(x)-f(x-a)$, namely $2f(x)=f(x-a)+f(x+a)$. Let $f(0)=C$, then consider $F(x)=f(x)-C$, where $F(0)=0,$ $2F(x)=F(x-a)+F(x+a)$.
$F(2x)=F(x)+[F(x)-F(0)]=2F(x)$,
$F(3x)=F(2x)+[F(2x)-F(x)]=3F(x)$.
Easily, by induction, $F(nx)=nF(x)$ for all integers $n$.
Therefore, for nonzero integer m, $(1/m)F(mx)=F(x)$ , namely $F(x/m)=(1/m)F(x)$
Hence $F(n/m)=(n/m)F(1)$. Let $F(1)=k$, we obtain $F(x)=kx$, where $k$ is the slope of the linear functions, and $f(x)=kx+C$.

We have  and  Subtracting these two and rearranging gives  and since $f(x+2d)=f(x+d)+f(x)-f(x-d)$ we get  from which we get  Then we have $f(x)+f(y)=f(0)+f(x+y)=2f\left(\frac{x+y}{2}\right)$. Setting $f(0)=c$, we let $f(x)=g(x)+c$ to get $g(x)+g(y)=g(x+y)$. This is Cauchy's functional equation, so it has solutions at $g(x)=kx$, so the answer is $\boxed{f(x)=kx+c}$.


Let $ABCD$ be a cyclic quadrilateral. Prove that there exists a point $X$ on segment $\overline{BD}$ such that $\angle BAC=\angle XAD$ and $\angle BCA=\angle XCD$ if and only if there exists a point $Y$ on segment $\overline{AC}$ such that $\angle CBD=\angle YBA$ and $\angle CDB=\angle YDA$.

Note that lines $AC, AX$ are isogonal in $\triangle ABD$, so an inversion centered at $A$ with power $r^2=AB\cdot AD$ composed with a reflection about the angle bisector of $\angle DAB$ swaps the pairs $(D,B)$ and $(C,X)$. Thus, so that $ACBD$ is a harmonic quadrilateral. By symmetry, if $Y$ exists, then $(B,D;A,C)=-1$. We have shown the two conditions are equivalent, whence both directions follow$.\:\blacksquare\:$

All angles are directed. Note that lines $AC, AX$ are isogonal in $\triangle ABD$ and $CD, CE$ are isogonal in $\triangle CDB$. From the law of sines it follows that

Therefore, the ratio equals $\frac{AD\cdot DC}{DB\cdot BC}.$
Now let $Y$ be a point of $AC$ such that $\angle{ABE}=\angle{CBY}$. We apply the above identities for $Y$ to get that $\frac{CY}{YA}\cdot \frac{CE}{EA}=\left(\frac{CD}{DA}\right)^2$. So $\angle{CDY}=\angle{EDA}$, the converse follows since all our steps are reversible.
Beware that directed angles, or angles $\bmod$ $180$, are not standard olympiad material. If you use them, provide a definition.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Steve is piling $m\geq 1$ indistinguishable stones on the squares of an $n\times n$ grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions $(i, k), (i, l), (j, k), (j, l)$ for some $1\leq i, j, k, l\leq n$, such that $i<j$ and $k<l$. A stone move consists of either removing one stone from each of $(i, k)$ and $(j, l)$ and moving them to $(i, l)$ and $(j, k)$ respectively, or removing one stone from each of $(i, l)$ and $(j, k)$ and moving them to $(i, k)$ and $(j, l)$ respectively.
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.
How many different non-equivalent ways can Steve pile the stones on the grid?

Solution:
Let the number of stones in row $i$ be $r_i$ and let the number of stones in column $i$ be $c_i$. Since there are $m$ stones, we must have $\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m$
Lemma 1: If any $2$ pilings are equivalent, then $r_i$ and $c_i$ are the same in both pilings $\forall i$.
Proof: We suppose the contrary. Note that $r_i$ and $c_i$ remain invariant after each move, therefore, if any of the $r_i$ or $c_i$ are different, they will remain different.
Lemma 2: Any $2$ pilings with the same $r_i$ and $c_i$ $\forall i$ are equivalent.
Proof: Suppose piling 1 and piling 2 not the same piling. Call a stone in piling 1 wrong if the stone occupies a position such that there are more stones in that position in piling 1 than piling 2. Similarly define a wrong stone in piling 2. Let a wrong stone be at $(a, b)$ in piling 1. Since $c_b$ is the same for both pilings, we must have a wrong stone in piling 2 at column b, say at $(c, b)$, such that $c\not = a$. Similarly, we must have a wrong stone in piling 1 at row c, say at $(c, d)$ where $d \not = b$. Clearly, making the move $(a,b);(c,d) \implies (c,b);(a,d)$ in piling 1 decreases the number of wrong stones in piling 1. Therefore, the number of wrong stones in piling 1 must eventually be $0$ after a sequence of moves, so piling 1 and piling 2 are equivalent.
Lemma 3: Given the sequences $g_i$ and $h_i$ such that $\sum_{i=1}^n g_i=\sum_{i=1}^n h_i=m$ and $g_i, h_i\geq 0 \forall i$, there is always a piling that satisfies $r_i=g_i$ and $c_i=h_i$ $\forall i$.
Proof: We take the lowest $i$, $j$, such that $g_i, h_j >0$ and place a stone at $(i, j)$, then we subtract $g_i$ and $h_j$ by $1$ each, until $g_i$ and $h_i$ become $0$ $\forall i$, which will happen when $m$ stones are placed, because $\sum_{i=1}^n g_i$ and $\sum_{i=1}^n h_i$ are both initially $m$ and decrease by $1$ after each stone is placed. Note that in this process $r_i+g_i$ and $c_i+h_i$ remains invariant, thus, the final piling satisfies the conditions above.
By the above lemmas, the number of ways to pile is simply the number of ways to choose the sequences $r_i$ and $c_i$ such that $\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m$ and $r_i, c_i \geq 0 \forall i$. By stars and bars, the number of ways is $\binom{n+m-1}{m}^{2}$.
Solution by Shaddoll


The isosceles triangle $\triangle ABC$, with $AB=AC$, is inscribed in the circle $\omega$. Let $P$ be a variable point on the arc $\stackrel{\frown}{BC}$ that does not contain $A$, and let $I_B$ and $I_C$ denote the incenters of triangles $\triangle ABP$ and $\triangle ACP$, respectively.
Prove that as $P$ varies, the circumcircle of triangle $\triangle PI_BI_C$ passes through a fixed point.

We claim that $M$ (midpoint of arc $BC$) is the fixed point.
We would like to show that $M$, $P$, $I_B$, $I_C$ are cyclic.
We extend $PI_B$ to intersect $\omega$ again at R.
We extend $PI_C$ to intersect $\omega$ again at S.
We invert around a circle centered at $P$ with radius $1$ (for convenience).
(I will denote X' as the reflection of X for all the points)
The problem then becomes: Prove $I_B'$, $I_C'$, and $M'$ are collinear.
Now we look at triangle $\triangle PR'S'$. We apply Menelaus (the version where all three points lie outside the triangle).
It suffices to show that
By inversion, we know $PX' = \dfrac{1}{PX}$ for any point $X$ and $X'Y' = \dfrac{XY}{PX \cdot PY}$ for any points $X$ and $Y$.
Plugging this into our Menelaus equation we obtain that it suffices to show

We cancel out the like terms and rewrite. It suffices to show

We know that $AM$ is the diameter of $\omega$ because $\triangle ABC$ is isosceles and $AM$ is the angle bisector. We also know $\angle RMA = \dfrac{\angle ACB}{2} = \dfrac{\angle ABC}{2} = \angle SMA$ so $R$ and $S$ are symmetric with respect to $AM$ so $RM = SM$.
Thus, it suffices to show $\dfrac{SI_C}{RI_B} = 1$.
This is obvious because $RI_B = RA = SA = SI_C$.
Therefore we are done. $\blacksquare$

We will use complex numbers as mentioned here. Set the circumcircle of $\triangle ABC$ to be the unit circle. Let  such that  We claim that the circumcircle of $\triangle PI_BI_C$ passes through $M=-1.$ This is true if  is real. Now observe that  so $k$ is real and we are done. $\blacksquare$

Let $M$ be the midpoint of arc $BC$. Let $D$ be the midpoint of arc $AB$. Let $E$ be the midpoint of arc $AC$.
Then, $P, I_B$, and $D$ are collinear and $P, I_C$, and $E$ are collinear.
We'll prove $MPI_B I_C$ is cyclic. (Intuition: we'll show that $M$ is the Miquel's point of quadrilateral $DE I_C I_B$.
$D$ is the center of the circle $A I_B B$ (the $P-$ excenter of $PAB$ is also on the same circle). Therefore $D I_B = DB$. Similarly $E I_C = EC$. Since $AB=AC$, $DB=EC$. Therefore $D I_B = E I_C$. Obviously $ME = MD$ and $\angle MEI_C = \angle MEP = \angle MDP = \angle MDI_B$. Thus by SAS, $\triangle MEI_C \cong \triangle MDI_B$.
Hence $\angle I_B M I_C = \angle DME = \angle DPE = \angle I_B P I_C$, so $MPI_B I_C$ is cyclic and we are done.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Prove that there exists a positive integer $n < 10^6$ such that $5^n$ has six consecutive zeros in its decimal representation.

Solution:
Let digit $1$ of a number be the units digit, digit $2$ be the tens digit, and so on. Let the 6 consecutive zeroes be at digits $k-5$ through digit $k$. The criterion is then obviously equivalent to

We will prove that $n = 20+2^{19}, k = 20$ satisfies this, thus proving the problem statement (since $n = 20+2^{19} < 10^6$).
We want

We can split this into its prime factors. Obviously, it is a multiple of $5^{20}$, so we only need to consider it $\mod2^{20}$.

($\varphi$ is the Euler Totient Function.) By Euler's Theorem, since $\bigl(5, 2^{20}\bigr)=1$,

so

Since $2^{20} > 10^6, 5^{20} < 10^{14} = 10^{20-6}$,

for $n = 20+2^{19}$ and $k = 20$, and thus the problem statement has been proven. $\blacksquare$


Let $X_1, X_2, \ldots, X_{100}$ be a sequence of mutually distinct nonempty subsets of a set $S$. Any two sets $X_i$ and $X_{i+1}$ are disjoint and their union is not the whole set $S$, that is, $X_i\cap X_{i+1}=\emptyset$ and $X_i\cup X_{i+1}\neq S$, for all $i\in\{1, \ldots, 99\}$. Find the smallest possible number of elements in $S$.

The answer is that $|S| \ge 8$.
First, we provide a inductive construction for $S = \left\{ 1, \dots, 8 \right\}$. Actually, for $n \ge 4$ we will provide a construction for $S = \left\{ 1, \dots, n \right\}$ which has $2^{n-1} + 1$ elements in a line. (This is sufficient, since we then get $129$ for $n = 8$.) The idea is to start with the following construction for $|S| = 4$: Then inductively, we do the following procedure to move from $n$ to $n+1$: take the chain for $n$ elements, delete an element, and make two copies of the chain (which now has even length). Glue the two copies together, joined by $\varnothing$ in between. Then place the element $n+1$ in alternating positions starting with the first (in particular, this hits $n+1$). For example, the first iteration of this construction gives:
Now let's check $|S| \ge 8$ is sufficient. Consider a chain on a set of size $|S| = 7$. (We need $|S| \ge 7$ else $2^{|S|} < 100$.) Observe that there are sets of size $\ge 4$ can only be neighbored by sets of size $\le 2$, of which there are $\binom 71 + \binom 72 = 28$. So there are $\le 30$ sets of size $\ge 4$. Also, there are $\binom 73 = 35$ sets of size $3$. So the total number of sets in a chain can be at most $30 + 28 + 35 = 93 < 100$.

My proof that $|S|\ge 8$ is basically the same as the one above. Here is another construction for $|S| = 8$ that I like because it works with remainders and it's pretty intuitive. The basic idea is to assign different subsets to different remainders when divided by particular numbers, and then to use the Chinese Remainder Theorem to show that all of the subsets are distinct. The motivation for this comes from the fact that we want $X_i$ and $X_{i+1}$ to always be disjoint, so remainders are a great way to systematically make that happen, since $i$ and $i+1$ do not have the same remainder modulo any positive integer greater than $1.$ Anyway, here is the construction:
Let $S = \left\{ {1, 2, ..., 8} \right\}.$ For $i = 1, 2, ..., 98,$ we will choose which elements of the set $\left\{ {1, 2, 3, 4} \right\}$ belong to $X_i$ based on the remainder of $i$ modulo $9,$ and we will choose which elements of the set $\left\{ {5, 6, 7, 8} \right\}$ belong to $X_i$ based on the remainder of $i$ modulo $11.$ We do this as follows:

Finally, we specially define $X_{99} = \left\{ {1, 2, 3} \right\}$ and $X_{100} = \left\{ {5, 6, 7} \right\}.$
It is relatively easy to see that this configuration satisfies all of the desired conditions. We see that $X_{98} = \left\{ {4, 7} \right\},$ so $X_{98}$ and $X_{99}$ are disjoint, as are $X_{99}$ and $X_{100}.$ The remainder configuration above takes care of the rest, so any two consecutive sets are disjoint. Then, by the Chinese Remainder Theorem, no two integers from $1$ to $98$ have the same combination of residues modulo $9$ and modulo $11,$ so all of the sets $X_i$ are distinct for $i = 1, 2, ..., 98.$ It is also easy to verify that none of these match $X_{99}$ or $X_{100},$ since they all have at most two elements of $\left\{ {1, 2, 3, 4} \right\}$ and at most two elements of $\left\{ {5, 6, 7, 8} \right\},$ whereas $X_{99}$ and $X_{100}$ do not satisfy this; hence all of the sets are distinct. Finally, notice that, for any pair of consecutive sets, at least one of them has at most $3$ elements, while the other has at most $4.$ Thus, their union always has at most $7$ elements, so $X_i\cup X_{i+1}\neq S$ for all $i = 1, 2, ..., 99.$
All of the conditions are satisfied, so this configuration works. We thus conclude that $\text{min}\left(\left|S\right|\right) = 8.$
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Find, with proof, the least integer $N$ such that if any $2016$ elements are removed from the set $\{1, 2,...,N\}$, one can still find $2016$ distinct numbers among the remaining elements with sum $N$.

Solution:
Since any $2016$ elements are removed, suppose we remove the integers from $1$ to $2016$. Then the smallest possible sum of $2016$ of the remaining elements is
so clearly $N\ge 6097392$. We will show that $N=6097392$ works.
$\vspace{0.2 in}$
$\{1,2\cdots 6097392\}$ contain the integers from $1$ to $6048$, so pair these numbers as follows:

When we remove any $2016$ integers from the set $\{1,2,\cdots N\}$, clearly we can remove numbers from at most $2016$ of the $3024$ pairs above, leaving at least $1008$ complete pairs. To get a sum of $N$, simply take these $1008$ pairs, all of which sum to $6049$. The sum of these $2016$ elements is $1008 \cdot 6049 = 6097392$, as desired.
$\vspace{0.2 in}$
We have shown that $N$ must be at least $6097392$, and that this value is attainable. Therefore our answer is $\boxed{6097392}$.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Let $\triangle ABC$ be an acute triangle, with $O$ as its circumcenter. Point $H$ is the foot of the perpendicular from $A$ to line $\overleftrightarrow{BC}$, and points $P$ and $Q$ are the feet of the perpendiculars from $H$ to the lines $\overleftrightarrow{AB}$ and $\overleftrightarrow{AC}$, respectively.
Given that prove that the points $O,P,$ and $Q$ are collinear.

It is well-known that $AH\cdot 2AO=AB\cdot AC$ (just use similar triangles or standard area formulas). Then by Power of a Point,
 Consider the transformation $X\mapsto \Psi(X)$ which dilates $X$ from $A$ by a factor of $\dfrac{AB}{AQ}=\dfrac{AC}{AP}$ and reflects about the $A$-angle bisector. Then $\Psi(O)$ clearly lies on $AH$, and its distance from $A$ is  so $\Psi(O)=H$, hence we conclude that $O,P,Q$ are collinear, as desired.

We will use barycentric coordinates with respect to $\triangle ABC.$ The given condition is equivalent to $(\sin B\sin C)^2=\frac{1}{2}.$ Note that  Therefore, we must show that  Expanding, we must prove
Let $x=e^{iA}, y=e^{iB}, z=e^{iC},$ such that $xyz=-1.$ The left side is equal to  The right side is equal to
 which is equivalent to the left hand side. Therefore, the determinant is $0,$ and $O,P,Q$ are collinear. $\blacksquare$

For convenience, let $a, b, c$ denote the lengths of segments $BC, CA, AB,$ respectively, and let $\alpha, \beta, \gamma$ denote the measures of $\angle CAB, \angle ABC, \angle BCA,$ respectively. Let $R$ denote the circumradius of $\triangle ABC.$
Since the central angle $\angle AOB$ subtends the same arc as the inscribed angle $\angle ACB$ on the circumcircle of $\triangle ABC,$ we have $\angle AOB = 2\gamma.$ Note that $OA = OB,$ so $\angle OAB = \angle OBA.$ Thus, $\angle OAB = \frac{\pi}{2} - \gamma.$ Similarly, one can show that $\angle OAC = \frac{\pi}{2} - \beta.$ (One could probably cite this as well-known, but I have proved it here just in case.)
Clearly, $AO = R.$ Since $AH^2 = 2\cdot AO^2,$ we have $AH = \sqrt{2}R.$ Thus, $AH\cdot AO = \sqrt{2}R^2.$
Note that $AH = b\sin\gamma = c\sin\beta.$ The Extended Law of Sines states that:

Therefore, $AH = \frac{bc}{2R} = \sqrt{2}R.$ Thus, $bc = \sqrt{2}R^2.$
Since $\angle PHA = \beta$ and $\angle QHA = \gamma,$ we have:

It follows that:

We see that $AP\cdot AQ = AH\cdot AO.$
Rearranging $AP\cdot AQ = AH\cdot AO,$ we get $\frac{AP}{AH} = \frac{AO}{AQ}.$ We also have $\angle PAH = \angle OAQ = \frac{\pi}{2} - \beta,$ so $\triangle PAH\sim\triangle OAQ$ by SAS similarity. Thus, $\angle AOQ = \angle APH,$ so $\angle AOQ$ is a right angle.
Rearranging $AP\cdot AQ = AH\cdot AO,$ we get $\frac{AP}{AO} = \frac{AO}{AH}.$ We also have $\angle PAO = \angle HAQ = \frac{\pi}{2} - \gamma,$ so $\triangle PAO\sim\triangle HAQ$ by SAS similarity. Thus, $\angle AOP = \angle AQH,$ so $\angle AOP$ is a right angle.
Since $\angle AOP$ and $\angle AOQ$ are both right angles, we get $\angle POQ = \pi,$ so we conclude that $P, O, Q$ are collinear, and we are done. (We also obtain the extra interesting fact that $AO\perp PQ.$)

Draw the altitude from $O$ to $AB$, and let the foot of this altitude be $D$.
Then, by the Right Triangle Altitude Theorem on triangle $AHB$, we have: $AB\cdot AP=AH^{2}$.
Since $OD$ is the perpendicular bisector of $AB$, $2\cdot AD = AB$.
Substituting this into our previous equation gives $2\cdot AD \cdot AP = AH^{2}$, which equals $2\cdot AO^{2}$ by the problem condition.
Thus, $2\cdot AD\cdot AP = 2\cdot AO^{2} \implies AD\cdot AP = AO^{2}$.
Again, by the Right Triangle Altitude Theorem, angle $AOP$ is right.
By dropping an altitude from $O$ to $AC$ and using the same method, we can find that angle $AOQ$ is right. Since $\angle AOP=\angle AOQ=90$, $P$, $O$, $Q$ are collinear and we are done.
~champion999

We use complex numbers. Let lower case letters represent their respective upper case points, with $|a| = |b| = |c| = 1$. Spamming the foot from point to segment formula, we obtain   and  We now simplify the given length condition:  We would like to show that $P$, $O$, $Q$ are collinear, or  After some factoring (or expanding) that takes about 15 minutes, this eventually reduces to  which is true. $\square$
-MP8148

Claim: $\triangle AOQ \sim \triangle AHB$
Proof: We compute the area of $\triangle ABC$ using two methods. Let $R=AO$ be the circumradius of $\triangle ABC$.
First, by extended law of sines, $BC=2R \sin \angle BAC$. We are also given that $AH= R \sqrt{2}$.
$AH \perp BC$, so
Second, we compute the area using $[ABC]=\frac{1}{2} \cdot AB \cdot AC \sin \angle BAC$.
Equating these two expressions for the area of $\triangle ABC$ and reducing, we get
But $2R^2 =2 AO^2 = AH^2$, so $AB \cdot AC = AH^2 \sqrt{2}$ and $\bf{AB =\frac{AH^2 \sqrt{2}}{AC}}$.
Since $\angle AQH=\angle AHC =90^\circ$, and both triangles share the angle $\angle HAC$, $\triangle AHC \sim \triangle AQH$. This tells us $\frac{AQ}{AH}=\frac{AH}{AC}$ or $AQ =\frac{AH^2}{AC}$.
Substituting into the bolded equation, we get $AB=AQ \sqrt{2}$.
The original length condition can be written as $AH= AO \sqrt{2}$.
We also have
Therefore, by SAS similarity, $\triangle AOQ \sim \triangle AHB$.
We can prove analogously that $\triangle AOP \sim \triangle AHC$.
We now have $\angle AOQ=\angle AHB =90^\circ$ and $\angle AOP=\angle AHC =90^\circ$.
This implies that $\angle POQ=\angle POA +\angle QOA=180^\circ$ which tells us $P,O,$ and $Q$ are collinear, as desired.$\square$
-vvluo
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Find all functions $f:\mathbb{R}\rightarrow \mathbb{R}$ such that for all real numbers $x$ and $y$,

Step 1: Set $x = y = 0$ to obtain $f(0) = 0.$
Step 2: Set $x = 0$ to obtain $f(y)f(-y) = f(y)^2.$
$\indent$ In particular, if $f(y) \ne 0$ then $f(y) = f(-y).$
$\indent$ In addition, replacing $y \to -t$, it follows that $f(t) = 0 \implies f(-t) = 0$ for all $t \in \mathbb{R}.$
Step 3: Set $x = 3y$ to obtain $\left[f(y) + 3y^2\right]f(8y) = f(4y)^2.$
$\indent$ In particular, replacing $y \to t/8$, it follows that $f(t) = 0 \implies f(t/2) = 0$ for all $t \in \mathbb{R}.$
Step 4: Set $y = -x$ to obtain $f(4x)\left[f(x) + f(-x) - 2x^2\right] = 0.$
$\indent$ In particular, if $f(x) \ne 0$, then $f(4x) \ne 0$ by the observation from Step 3, because $f(4x) = 0 \implies f(2x) = 0 \implies f(x) = 0.$ Hence, the above equation implies that $2x^2 = f(x) + f(-x) = 2f(x)$, where the last step follows from the first observation from Step 2.
$\indent$ Therefore, either $f(x) = 0$ or $f(x) = x^2$ for each $x.$
$\indent$ Looking back on the equation from Step 3, it follows that $f(y) + 3y^2 \ne 0$ for any nonzero $y.$ Therefore, replacing $y \to t/4$ in this equation, it follows that $f(t) = 0 \implies f(2t) = 0.$
Step 5: If $f(a) = f(b) = 0$, then $f(b - a) = 0.$
$\indent$ This follows by choosing $x, y$ such that $x - 3y = a$ and $3x - y = b.$ Then $x + y = \tfrac{b - a}{2}$, so plugging $x, y$ into the given equation, we deduce that $f\left(\tfrac{b - a}{2}\right) = 0.$ Therefore, by the third observation from Step 4, we obtain $f(b - a) = 0$, as desired.
Step 6: If $f \not\equiv 0$, then $f(t) = 0 \implies t = 0.$
$\indent$ Suppose by way of contradiction that there exists an nonzero $t$ with $f(t) = 0.$ Choose $x, y$ such that $f(x) \ne 0$ and $x + y = t.$ The following three facts are crucial:
$\indent$ 1. $f(y) \ne 0.$ This is because $(x + y) - y = x$, so by Step 5, $f(y) = 0 \implies f(x) = 0$, impossible.
$\indent$ 2. $f(x - 3y) \ne 0.$ This is because $(x + y) - (x - 3y) = 4y$, so by Step 5 and the observation from Step 3, $f(x - 3y) = 0 \implies f(4y) = 0 \implies f(2y) = 0 \implies f(y) = 0$, impossible.
$\indent$ 3. $f(3x - y) \ne 0.$ This is because by the second observation from Step 2, $f(3x - y) = 0 \implies f(y - 3x) = 0.$ Then because $(x + y) - (y - 3x) = 4x$, Step 5 together with the observation from Step 3 yield $f(3x - y) = 0 \implies f(4x) = 0 \implies f(2x) = 0 \implies f(x) = 0$, impossible.
$\indent$ By the second observation from Step 4, these three facts imply that $f(y) = y^2$ and $f(x - 3y) = \left(x - 3y\right)^2$ and $f(3x - y) = \left(3x - y\right)^2.$ By plugging into the given equation, it follows that
 But the above expression miraculously factors into $\left(x + y\right)^4$! This is clearly a contradiction, since $t = x + y \ne 0$ by assumption. This completes Step 6.
Step 7: By Step 6 and the second observation from Step 4, the only possible solutions are $f \equiv 0$ and $f(x) = x^2$ for all $x \in \mathbb{R}.$ It's easy to check that both of these work, so we're done.

Step 1: $x=y=0 \implies f(0)=0$
Step 2: $x=0 \implies f(y)f(-y)=f(y)^{2}$. Now, assume $y \not = 0$. Then, if $f(y)=0$, we substitute in $-y$ to get $f(y)f(-y)=f(-y)^{2}$, or $f(y)=f(-y)=0$. Otherwise, we divide both sides by $f(y)$ to get $f(y)=f(-y)$. If $y=0$, we obviously have $f(0)=f(0)$. Thus, the function is even.
.
Step 3: $y=-x \implies 2f(4x)(f(x)-x^{2})=0$. Thus, $\forall x$, we have $f(4x)=0$ or $f(x)=x^{2}$.
Step 4: We now assume $f(x) \not = 0$, $x\not = 0$. We have $f(\frac{x}{4})=\frac{x^{2}}{16}$. Now, setting $x=y=\frac{x}{4}$, we have $f(\frac{x}{2})=\frac{x^{2}}{4}$ or $f(\frac{x}{2})=0$. The former implies that $f(x)=0$ or $x^{2}$. The latter implies that $f(x)=0$ or $f(x)=\frac{x^{2}}{2}$. Assume the latter. $y=-2x \implies -\frac{3y^{2}}{2}f(7y)-{2y^{2}}f(5y)=\frac{x^{2}}{2}$. Clearly, this implies that $f(x)$ is negative for some $m$. Now, we have $f(\frac{m}{4})=\frac{m^{2}}{16} \implies f(\frac{m}{2})=0,\frac{m^{2}}{4} \implies f(m) \geq 0$, which is a contradiction. Thus, $\forall x$$f(x)=0$ or $f(x)=x^{2}$.
Step 5: We now assume $f(x)=0$, $f(y)=y^{2}$ for some $x,y \not = 0$. Let $m$ be sufficiently large integer, let $z=|4^{m}x|$ and take the absolute value of $y$(since the function is even). Choose $c$ such that $3z-c=y$. Note that we have $\frac{c}{z}$~$3$ and $\frac{y}{z}$~$0$. Note that $f(z)=0$. Now, $x=z, y=c \implies$ LHS is positive, as the second term is positive and the first term is nonnegative and thus the right term is equal to $(z+c)^{4}$~$256z^{4}$. Now if $f(z-3c)=0$, the second term of the LHS/RHS clearly ~0 as $m \to \infty$. if $f(z-3c)=0$, then we have LHS/RHS ~ $0$, otherwise, we have LHS/RHS~$\frac{8^{2}\cdot 3z^{4}}{256z^{4}}$~$\frac{3}{4}$, a contradiction, as we're clearly not dividing by $0$, and we should have LHS/RHS=1.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Prove that there are infinitely many distinct pairs $(a,b)$ of relatively prime positive integers $a>1$ and $b>1$ such that $a^b+b^a$ is divisible by $a+b$.

Let $a = 2n-1$ and $b = 2n+1$. We see that $(2n \pm 1)^2 = 4n^2\pm4n+1 \equiv 1 \pmod{4n}$. Therefore, we have $(2n+1)^{2n-1} + (2n-1)^{2n+1} \equiv 2n + 1 + 2n - 1  = 4n \equiv 0 \pmod{4n}$, as desired.
(Credits to mathmaster2012)

Let $x$ be odd where $x>1$. We have $x^2-1=(x-1)(x+1),$ so $x^2-1 \equiv 0 \pmod{2x+2}.$ This means that  $x^{x+2}-x^x \equiv 0 \pmod{2x+2},$ and since x is odd, $x^{x+2}+(-x)^x \equiv 0 \pmod{2x+2},$ or $x^{x+2}+(x+2)^x \equiv 0 \pmod{2x+2},$ as desired.

Because problems such as this usually are related to expressions along the lines of $x\pm1$, it's tempting to try these. After a few cases, we see that $\left(a,b\right)=\left(2x-1,2x+1\right)$ is convenient due to the repeated occurrence of $4x$ when squared and added. We rewrite the given expressions as:  After repeatedly factoring the initial equation,we can get:  Expanding each of the squares, we can compute each product independently then sum them:   Now we place the values back into the expression:  Plugging any positive integer value for $x$ into $\left(a,b\right)=\left(2x-1,2x+1\right)$ yields a valid solution, because there is an infinite number of positive integers, there is an infinite number of distinct pairs $\left(a,b\right)$. $\square$
-fatant

Let $a = 2x + 1$ and $b = 2x-1$, where $x$ leaves a remainder of $1$ when divided by $4$.We seek to show that $(2x+1)^{2x-1} + (2x-1)^{2x+1} \equiv 0 \mod 4x$ because that will show that there are infinitely many distinct pairs $(a,b)$ of relatively prime integers $a>1$ and $b>1$ such that $a^b+b^a$ is divisible by $a+b$.
Claim 1: $(2x+1)^{2x-1} + (2x-1)^{2x+1} \equiv 0 \mod 4$.
We have that the remainder when $2x+1$ is divided by $4$ is $3$ and the remainder when $2x-1$ is divided by $4$ is always $1$. Therefore, the remainder when $(2x+1)^{2x-1} + (2x-1)^{2x+1}$ is divided by $4$ is always going to be $(-1)^{2x-1} + 1^{2x+1} = 0$.
Claim 2: $(2x+1)^{2x-1} + (2x-1)^{2x+1} \equiv 0 \mod x$
We know that $(2x+1) \mod x \equiv 1$ and $(2x-1) \mod x \equiv 3$, so the remainder when $(2x+1)^{2x-1} + (2x-1)^{2x+1}$ is divided by $4$ is always going to be $(-1)^{2x-1} + 1^{2x+1} = 0$.
Claim 3: $(2x+1)^{2x-1} + (2x-1)^{2x+1} \equiv 0 \mod 4x$
Trivial given claim $1,2$. $\boxed{}$
~AopsUser101

I claim $(a,b) = (2n-1,2n+1)$,  $n (\in \mathbb{N}) \geq 2$ always satisfies above conditions.
Note: We could have also substituted 2n with 2^n or 4n, 8n, ... any sequence of numbers such that they are all even. The proof will work the same.
Since there are infinitely many integers larger than or equal to 2, there are infinitely many distinct pairs $(a,b)$.
We only need to prove:
$a^b+b^a \equiv 0 \pmod{a+b}$
We can expand $a^b + b^a = (2n-1)^{2n+1} + (2n+1)^{2n-1}$ using binomial theorem. However, since $a + b = 2n-1 + 2n+1 = 4n$, all the $2n$ terms (with more than 2 powers of) when evaluated modulo $4n$ equal to 0, and thus can be omitted. We are left with the terms: $(2n+1)(2n)^1-1+(2n-1)(2n)^1+1 = 4n \cdot 2n$, which is divisible by $4n$.
$(2n-1)^{2n+1} + (2n+1)^{2n-1} \equiv (2n+1)(2n)-1+(2n-1)(2n)+1 = 4n \cdot 2n \equiv 0 \pmod{4n}$
-AlexLikeMath

Note that  To get rid of the $a^a+b^a$ part $\pmod{a+b},$ we can use the sum of powers factorization. However, $a$ must be odd for us to do this. If we assume that $a$ is odd,

Because $a$ and $b$ are relatively prime, $a+b$ cannot divide $a^a.$ Thus, we have to show that there exists an integer $b$ such that for odd $a,$

Suppose that $a=2n-1.$ To keep the powers small, we try $b=2n+k$ for small values of $k.$ We can find that $b=2n$ does not work. $b=2n+1$ works though, as $a+b=4n$ and

Because $a$ is odd, $b=a+2$ is relatively prime to $a.$ Thus,  is a solution for positive $n\ge 2.$ There are infinitely many possible values for $n,$ so the proof is complete. $\blacksquare$
~BS2012
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Consider the equation
(a) Prove that there are infinitely many pairs $(x,y)$ of positive integers satisfying the equation.
(b) Describe all pairs $(x,y)$ of positive integers satisfying the equation.

We have $(3x^3+xy^2)(yx^2+3y^3)=(x-y)^7$, which can be expressed as $xy(3x^2+y^2)(x^2+3y^2)=(x-y)^7$. At this point, we think of substitution. A substitution of form $a=x+y, b=x-y$ is slightly derailed by the leftover x and y terms, so instead, seeing the $xy$ in front, we substitute $x=a+b, y=a-b$. This leaves us with:

Rearranging, we have $b^6(8b+1)=a^6$. To satisfy this equation in integers, $8b+1$ must obviously be a $6$th power, and further inspection shows that it must also be odd. Also, since it is a square and all odd squares are 1 mod 8, every odd sixth power gives a solution. Since the problem asks for positive integers, the pair $(a,b)=(0,0)$ does not work. We go to the next highest odd $6$th power, $3^6$ or $729$. In this case, $b=91$, so the LHS is $91^6\cdot3^6=273^6$, so $a=273$. Using the original substitution yields $(x,y)=(364,182)$ as the first solution. We have shown part a by showing that there are an infinite number of positive integer solutions for $(a,b)$, which can then be manipulated into solutions for $(x,y)$.
To solve part (b), we look back at the original method of generating solutions. Define $a_n$ and $b_n$ to be the pair representing the $n$th solution. Since the $n$th odd number is $2n+1$, $b_n=\frac{(2n+1)^6-1}{8}$. It follows that $a_n=(2n+1)b_n=\frac{(2n+1)^7-(2n+1)}{8}$. From our original substitution, $(x,y)=\left(\frac{(2n+1)^7+(2n+1)^6-2n-2}{8},\frac{(2n+1)^7-(2n+1)^6-2n}{8}\right)$.

First, we shall prove a lemma:
LEMMA:
PROOF: Expanding and simplifying the right side, we find that
which proves our lemma.
Now, we have that
Rearranging and getting rid of the denominator, we have that
Factoring, we have Dividing both sides, we have
Now, since the LHS is the 6th power of a rational number, and the RHS is an integer, the RHS must be a perfect 6th power. Define $a=\frac{x+y}{x-y}$. By inspection, $a$ must be a positive odd integer satistisfying $a \geq 3$. We also have  Now, we can solve for $x$ and $y$ in terms of $a$:
$x-y=\frac{a^6-1}{4}$ and $x+y=a(x-y)=\frac{a(a^6-1)}{4}$.
Now we have:
and it is trivial to check that this parameterization works for all such $a$ (to keep $x$ and $y$ integral), which implies part (a).
MOTIVATION FOR LEMMA:
I expanded the LHS, noticed the coefficients were $(3,10,3)$, and immediately thought of binomial coefficients. Looking at Pascal's triangle, it was then easy to find and prove the lemma.
-sunfishho

So named because it is a mix of solutions 1 and 2 but differs in other aspects.
After fruitless searching, let $x+y=a$, $x-y=b$. Clearly $a,b>0$. Then,

Change the LHS of the original equation to

and change the RHS to $b^7$. Therefore $\biggl(\dfrac{a}{b}\biggr)^6=4b+1$. Let $n=\frac{a}{b}$, and note that $n$ is an integer. Therefore $b=\frac{n^6-1}{4},a=bn=n\biggl(\dfrac{n^6-1}{4}\biggr)$. Because $n^6\equiv1\pmod{4}$, $n$ is odd, and thus is greater than $1$, since $b>0$. Therefore, substituting for $x$ and $y$, we get:

Part a:
Let $a = 1 + \frac{1}{n}$, where $n$ is a positive integer. We will show that there is precisely one solution $(x, y)$ to the equation such that $x = ay$.
If $x = ay$, we have

The numerator is a multiple of $\frac{1}{n^5}$, so $y$ is an integer multiple of $n^2$. Thus, $x = \frac{n+1}{n}\cdot y$ is also an integer, and we conclude that this pair $(x, y)$ satisfies the system of equations. Because this works for any positive integer $n$, we conclude that there are infinitely many solutions to the equation.
Part b:
We will now prove that these are the only possible solutions. Suppose the contrary, that there are solutions with a different ratio between $x$ and $y$. As before, set $a = 1 + \frac{1}{n}$, but this time $n = \frac{p}{q}$ in simplest terms. Then,

For this to be rational, $q$ must divide the expression in brackets and thus must divide $16p^5$. However, $p$ and $q$ are relatively prime, so $q$ must divide $16$, and $p$ is therefore odd.
Next, set $q = 2^k$, where $k$ is a positive integer between $1$ and $4$, inclusive. We have

The sum in the brackets must be divisible by $2^{7k}$, which is a power of $2$ greater than or equal to $2^7$. Let $z$ be this sum. Then,

where $v$ represents $15\cdot 2^{2+2k}p^3$ and $w$ represents $15\cdot 2^{4k}p$. Therefore, we must have

For $k > 1$, this is equal to $0 \pmod{32}$, so we conclude that $k = 1$ (and thus $q = 2$). Then,

For this to be integral, the expression in brackets must be a multiple of $8$. However, there are three terms that are odd in this expression, $p^5$, $15p^3$, and $15p$. Thus, we have a contradiction, and we conclude that the only solutions $(x, y)$ are of the form stated above. $\square$
~mathboy100
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


($*$) Let $ABC$ be an equilateral triangle and let $P$ be a point on its circumcircle. Let lines $PA$ and $BC$ intersect at $D$; let lines $PB$ and $CA$ intersect at $E$; and let lines $PC$ and $AB$ intersect at $F$. Prove that the area of triangle $DEF$ is twice that of triangle $ABC$.

Extend $DP$ to hit $EF$ at $K$. Then note that $[DEF]\cdot\frac{AK}{DK}\cdot\frac{AB}{AF}\cdot\frac{AC}{AE}=[ABC].$ Letting $BF=x$ and $PF=y$, we have that $\frac{x+AB}y=\frac{y+PC}x=\frac{AC}{BP}.$ Solving and simplifying using LoC on $\triangle BPC$ gives $\frac{AB}{AF}=\frac{PC}{PB+PC}.$ Similarly, $\frac{AC}{AE}=\frac{PB}{PB+PC}.$

Now we find $\frac{AK}{DK}.$ Note that $\frac{AD}{DP}=\frac{AD}{BD}\cdot\frac{BD}{DP}=\frac{AC}{PB}\cdot\frac{AB}{PC}=\frac{AB^2}{PB\cdot PC}.$ Now let $E'=DE\cap AF$ and $F'=DF\cap AE$. Then by an area/concurrence theorem, we have that $\frac{DK}{AK}+\frac{DE'}{EE'}+\frac{DF'}{FF'}=1,$ or $\frac{DK}{AK}+(1-\frac{DP}{AP}-\frac{DC}{BC})+(1-\frac{DP}{AP}-\frac{BD}{BC})=1.$ Thus we have that $\frac{DK}{AK}=2\cdot\frac{DP}{AP}.$

Manipulating these gives $\frac{AK}{DK}=\frac{(PB+PC)^2}{2\cdot PB\cdot PC}.$ Thus $\frac{AK}{DK}\cdot\frac{AB}{AF}\cdot\frac{AC}{AE}=\frac12,$ and we are done.
~cocohearts

WLOG, let $AB = 1$. Let $[ABD] = X, [ACD] = Y$, and  $\angle BAD = \theta$. After some angle chasing, we find that $\angle BCF \cong \angle BEC \cong \theta$ and $\angle FBC \cong \angle BCE \cong 120^{\circ}$. Therefore, $\triangle FBC$ ~ $\triangle BCE$.
Lemma 1: If $BF = k$, then $CE = \frac 1k$.
This lemma results directly from the fact that $\triangle FBC$ ~ $\triangle BCE$;  $\frac{BF}{BC} = \frac{BF}{1} = \frac{BC}{CE} = \frac{1}{CE}$, or $CE = \frac{1}{BF}$.
Lemma 2: $[AEF] = (k+\frac 1k + 2)(X+Y)$.
We see that $[AEF] = (X+Y) \frac{[AEF]}{[ABC]} = (k+1)(1+\frac 1k)(X+Y) = (k + \frac 1k + 2)(X+Y)$, as desired.
Lemma 3: $\frac{X}{Y} = k$.
We see that

However, after some angle chasing and by the Law of Sines in $\triangle BCF$, we have $\frac{k}{\sin(\theta)} = \frac{1}{\sin(60^{\circ} - \theta)}$, or $k = \frac{\sin(\theta)}{\sin (60^{\circ} - \theta)}$, which implies the result.
By the area lemma, we have $[BDF] = kX$ and $[CDF] = \frac{Y}{k}$.
We see that $[DEF] = [AEF] - [ABC] - [BDF] - [DCE] = Xk + Yk + \frac Xk + \frac Yk + 2X + 2Y - X - Y - Xk - \frac Yk = X + Y + \frac Xk + yk$. Thus, it suffices to show that $X + Y + \frac Xk + Yk = 2X + 2Y$, or $\frac Xk + Yk = X + Y$. Rearranging, we find this to be equivalent to $\frac XY = k$, which is Lemma 3, so the result has been proven.

We will use barycentric coordinates and vectors. Let $\vec{X}$ be the position vector of a point $X.$ The point $(x, y, z)$ in barycentric coordinates denotes the point $x\vec{A} + y\vec{B} + z\vec{C}.$ For all points in the plane of $\triangle{ABC},$ we have $x + y + z = 1.$ It is clear that $A = (1, 0, 0)$; $B = (0, 1, 0)$; and $C = (0, 0, 1).$
Define the point $P$ as $P = \left(x_P, y_P, z_P\right).$ The fact that $P$ lies on the circumcircle of $\triangle{ABC}$ gives us $x^2_P + y^2_P + z^2_P = 1.$ This, along with the condition $x_P + y_P + z_P = 1$ inherent to barycentric coordinates, gives us $x_Py_P + y_Pz_P + z_Px_P = 0.$
We can write the equations of the following lines:
We can then solve for the points $D, E, F$:
The area of an arbitrary triangle $XYZ$ is:
To calculate $[DEF],$ we wish to compute $(\vec{D}\times\vec{E}) + (\vec{E}\times\vec{F}) + (\vec{F}\times\vec{D}).$ After a lot of computation, we obtain the following:
Evaluating the denominator,
Since $x_P + y_P + z_P = 1$ and $x_Py_P + y_Pz_P + z_Px_P = 0,$ it follows that:
We thus conclude that:
From this, it follows that $[DEF] = 2[ABC],$ and we are done.

We'll use coordinates and shoelace. Let the origin be the midpoint of $BC$. Let $AB=2$, and $BF = 2x$, then $F=(-x-1,-x\sqrt{3})$. Using the facts $\triangle{CBP} \sim  \triangle{CFB}$ and $\triangle{BCP} \sim  \triangle{BEC}$, we have $BF * CE = BC^2$, so $CE = \frac{1}{2x}$, and $E = (\frac{1}{x}+1,-\frac{\sqrt{3}}{x})$.
The slope of $FE$ is

It is well-known that $\triangle{DFE}$ is self-polar, so $FE$ is the polar of $D$, i.e., $OD$ is perpendicular to $FE$. Therefore, the slope of $OD$ is $-\frac{1}{k}$. Since $O=(0,\frac{1}{\sqrt{3}})$, we get the x-coordinate of $D$, $x_D = \frac{k}{\sqrt{3}}$, i.e., $D = (\frac{k}{\sqrt{3}},0)$. Using shoelace,

So $[\triangle{FDE}] = 2\sqrt{3} = 2[\triangle{ABC}]$. Q.E.D
By Mathdummy.

Note that $\angle{APB}=\angle{FPB}=\angle{EPC}=\angle{APC} = 60$. We will use a special version of Stewart's theorem for angle bisectors in triangle with an 120 angle to calculate various side lengths.
Let $BP = x$ and $CP = y$. Then,
From Law of Cosine, $BC^2 = x^2 + y^2 + xy$.
From Ptolemy's theorem, $AP BC = x AC + y AB$, so $AP = x + y$.
Lemma 1: In Triangle ABC with side lengths $a,b,c$ and $\angle A =120^o$, the length of the angle bisector of $A$ is

This can be easily proved with Stewart's and Law of Cosine.
Using Lemma 1, we have

Plug in $AP=x+y$, we get:

Then
By Mathdummy.


Are there any triples $(a,b,c)$ of positive integers such that $(a-2)(b-2)(c-2) + 12$ is prime that properly divides the positive number $a^2 + b^2 + c^2 + abc - 2017$?

The answer is no. Substitute $x=a-2,y=b-2,z=c-2$. This means that $x,y,z\geq -1$. Then  It is given in the problem that this is positive. Now, suppose for the sake of contradiction that $xyz+12$ is a prime. Clearly $x,y,z\neq 0$. Then we have  is an integer greater than or equal to $1$. This also implies that $x+y+z > 41$. Since $xyz+12$ is prime, we must have  Additionally, $x, y, z$ must be odd, so that $xyz+12$ is odd while $x+y+z-41,x+y+z+49$ are even. So, if  we must have  Now suppose WLOG that $x=-1$ and $y,z>0$. Then we must have $yz\leq 10$, impossible since $x+y+z>41$. Again, suppose that $x,y=-1$ and $z>0$. Then we must have  and since in this case we must have $z>43$, this is also impossible.
Then the final case is when $x,y,z$ are positive odd numbers. Note that if $xyz>x+y+z$ for positive integers $x,y,z$, then $abc>a+b+c$ for positive integers $a,b,c$ where $a>x,b>y,c>z$. Then we only need to prove the case where $x+y+z=43$, since $x+y+z$ is odd. Then one of  is true, implying that $xyz\leq -11$ or $xyz\leq 34$. But if $x+y+z=43$, then $xyz$ is minimized when $x=1,y=1,z=41$, so that $xyz\geq 41$. This is a contradiction, so we are done.


Let $O$ and $H$ be the circumcenter and the orthocenter of an acute triangle $ABC$. Points $M$ and $D$ lie on side $BC$ such that $BM = CM$ and $\angle BAD = \angle CAD$. Ray $MO$ intersects the circumcircle of triangle $BHC$ in point $N$. Prove that $\angle ADO = \angle HAN$.

It's well known that the reflection of $H$ across $\overline{BC}$, $H'$, lies on $(ABC)$. Then $(BHC)$ is just the reflection of $(BH'C)$ across $\overline{BC}$, which is equivalent to the reflection of $(ABC)$ across $\overline{BC}$. Reflect points $A$ and $N$ across $\overline{BC}$ to points $A'$ and $N'$, respectively. Then $N'$ is the midpoint of minor arc $\overarc{BC}$, so $A, D, N'$ are collinear in that order. It suffices to show that $\angle AA'N'=\angle ADO$.
Claim: $\triangle AA'N' \sim \triangle ADO$. The proof easily follows.
Proof: Note that $\angle BAA'=\angle CAO=90^{\circ}-\angle ABC$. Then we have $\angle A'AN'=\angle BAD-\angle BAA'=\angle CAD-\angle CAO=\angle DAO$. So, it suffices to show that  Notice that $\triangle ABA' \sim \triangle AOC$, so that  Therefore, it suffices to show that  But it is easy to show that $\triangle BAN'\sim \triangle DAC$, implying the result. $\blacksquare$

Suppose ray $OM$ intersects the circumcircle of $BHC$ at $N'$, and let the foot of the A-altitude of $ABC$ be $E$. Note that $\angle BHE=90-\angle HBE=90-90+\angle C=\angle C$. Likewise, $\angle CHE=\angle B$. So, $\angle BHC=\angle BHE+\angle CHE=\angle B+\angle C$.
$BHCN'$ is cyclic, so $\angle BN'C=180-\angle BHC=180-\angle B-\angle C=\angle A$. Also, $\angle BAC=\angle A$. These two angles are on different circles and have the same measure, but they point to the same line $BC$! Hence, the two circles must be congruent. (This is also a well-known result)
We know, since $M$ is the midpoint of $BC$, that $OM$ is perpendicular to $BC$. $AH$ is also perpendicular to $BC$, so the two lines are parallel. $AN$ is a transversal, so $\angle HAN=\angle ANO$. We wish to prove that $\angle ANO=\angle ADO$, which is equivalent to $AOND$ being cyclic.
Now, assume that ray $OM$ intersects the circumcircle of $ABC$ at a point $P$. Point $P$ must be the midpoint of $\stackrel{\frown}{BC}$. Also, since $AD$ is an angle bisector, it must also hit the circle at the point $P$. The two circles are congruent, which implies $MN=MP\implies ND=DP\implies$ NDP is isosceles. Angle ADN is an exterior angle, so $\angle ADN=\angle DNP+\angle DPO=2\angle DPO$.
Assume WLOG that $\angle B>\angle C$. So, $\angle DPO=\angle APO=\frac{\angle B+\angle C}{2}-\angle C=\frac{\angle B-\angle C}{2}$.
In addition, $\angle AON=\angle AOP=\angle AOB+\angle BOP=2\angle C+\angle A$. Combining these two equations, $\angle AON+\angle ADN=\angle B-\angle C+2\angle C+\angle A=\angle A+\angle B+\angle C=180$.
Opposite angles sum to $180$, so quadrilateral $AOND$ is cyclic, and the condition is proved.
-william122


Let $P_1, \ldots, P_{2n}$ be $2n$ distinct points on the unit circle $x^2 + y^2 = 1$ other than $(1,0)$. Each point is colored either red or blue, with exactly $n$ of them red and exactly $n$ of them blue. Let $R_1, \ldots, R_n$ be any ordering of the red points. Let $B_1$ be the nearest blue point to $R_1$ traveling counterclockwise around the circle starting from $R_1$. Then let $B_2$ be the nearest of the remaining blue points to $R_2$ traveling counterclockwise around the circle from $R_2$, and so on, until we have labeled all the blue points $B_1, \ldots, B_n$. Show that the number of counterclockwise arcs of the form $R_i \rightarrow B_i$ that contain the point $(1,0)$ is independent of the way we chose the ordering $R_1, \ldots, R_n$ of the red points.

Solution:
I define a sequence to be, starting at $(1,0)$ and tracing the circle counterclockwise, and writing the color of the points in that order - either R or B. For example, possible sequences include $RB$, $RBBR$, $BBRRRB$, $BRBRRBBR$, etc.
Note that choosing an $R_1$ is equivalent to choosing an $R$ in a sequence, and $B_1$ is defined as the $B$ closest to $R_1$ when moving rightwards. If no $B$s exist to the right of $R_1$, start from the far left. For example, if I have the above example $RBBR$, and I define the 2nd $R$ to be $R_1$, then the first $B$ will be $B_1$. Because no $R$ or $B$ can be named twice, I can simply remove $R_1$ and $B_1$ from my sequence when I choose them. I define this to be a move. Hence, a possible move sequence of $BBRRRB$ is:
$BBR_1RRB_1\implies B_2BRR_2\implies B_3R_3$
Note that, if, in a move, $B_n$ appears to the left of $R_n$, then $\stackrel{\frown}{R_nB_n}$ intersects $(1,0)$
Now, I define a commencing $B$ to be a $B$ which appears to the left of all $R$s, and a terminating $R$ to be a $R$ which appears to the right of all $B$s. Let the amount of commencing $B$s be $j$, and the amount of terminating $R$s be $k$, I claim that the number of arcs which cross $(1,0)$ is constant, and it is equal to $\text{max}(j,k)$. I will show this with induction.
Base case is when $n=1$. In this case, there are only two possible sequences - $RB$ and $BR$. In the first case, $\stackrel{\frown}{R_1B_1}$ does not cross $(1, 0)$, but both $j$ and $k$ are $0$, so $\text{max}(j,k)=0$. In the second example, $j=1$, $k=1$, so $\text{max}(j,k)=1$. $\stackrel{\frown}{R_1B_1}$ crosses $(1,0)$ since $B_1$ appears to the left of $R_1$, so there is one arc which intersects. Hence, the base case is proved.
For the inductive step, suppose that for a positive number $n$, the number of arcs which cross $(1,0)$ is constant, and given by $\text{max}(j, k)$ for any configuration. Now, I will show it for $n+1$.
Suppose I first choose $R_1$ such that $B_1$ is to the right of $R_1$ in the sequence. This implies that $\stackrel{\frown}{R_1B_1}$ does not cross $(1,0)$. But, neither $R_1$ nor $B_1$ is a commencing $B$ or terminating $R$. These numbers remain constant, and now after this move we have a sequence of length $2n$. Hence, by assumption, the total amount of arcs is $0+\text{max}(j,k)=\text{max}(j,k)$.
Thus, this solution probably doesn't work.
Now suppose that $R_1$ appears to the right of $B_1$, but $B_1$ is not a commencing $B$. This implies that there are no commencing $B$s in the series, because there are no $B$s to the left of $B_1$, so $j=0$. Note that this arc does intersect $(1,0)$, and $R_1$ must be a terminating $R$. $R_1$ must be a terminating $R$ because there are no $B$s to the right of $R_1$, or else that $B$ would be $B_1$. The $2n$ length sequence that remains has $0$ commencing $B$s and $k-1$ terminating $R$s. Hence, by assumption, the total amount of arcs is $1+\text{max}(0,k-1)=1+k-1=k=\text{max}(j,k)$.
Finally, suppose that $R_1$ appears to the right of $B_1$, and $B_1$ is a commencing $B$. We know that this arc will cross $(1,0)$. Analogous to the previous case, $R_1$ is a terminating $R$, so the $2n$ length sequence which remains has $j-1$ commencing $B$s and $k-1$ terminating $R$s. Hence, by assumption, the total amount of arcs is $1+\text{max}(j-1,k-1)=1+\text{max}(j,k)-1=\text{max}(j,k)$.
There are no more possible cases, hence the induction is complete, and the number of arcs which intersect $(1,0)$ is indeed a constant which is given by $\text{max}(j,k)$.
-william122

Lemma: If we switch the ordering of two consecutive $R_k$, $R_{k+1}$, the number of arcs crossing $(1,0)$ stays invariant.
Proof: There are two situations. If the two arcs don't cross this is simple because the actual arcs stay the same, and only the number order of the arcs change. Otherwise, if $B_k$ is to the left of $R_{k+1}$, the two arcs will have some overlap. The order of the points counterclockwise must be RRBB or some rotation of it. Notice how in both the old and the new ordering, the arc between the second R and the first B is counted twice and the arcs between the same colors are only counted once. Thus no matter where $(1,0)$ is the number of arcs containing it will stay invariant.
Lemma 2: We can swap the place of any two points $R_i$ and $R_j$ while keeping the number of crossings invariant.
Proof: By Lemma 1 we can use consecutive arc moves to swap $R_i$ with $R_{i+1}$, then the new $R_{i+1}$ with $R_{i+2}$ and so on until it swaps with $R_j$. Now, we can do the reverse swaps to move the new $R_{j-1}$ to $R_{j-2}$, and so on into the original position of $R_i$. Since the other points were moved once in one direction and once in the opposite, all the other points are kept in place.
Now, let $I$ be the sequence where $R_1$ through $R_n$ is numbered counterclockwise. We show that any ordering has the same number of crossings as $I$. We can swap the current place of $R_1$ with the desired position in $I$. Now we can ignore $R_1$ and swap the currrent place of $R_2$ with the place of $R_2$ in $I$, and so on until all the points are in the desired position. Thus, all orderings of $R_1$ to $R_n$ have the same number of crossings as $I$.
-tigershark22


For each positive integer $n$, find the number of $n$-digit positive integers that satisfy both of the following conditions:
$\bullet$ no two consecutive digits are equal, and
$\bullet$ the last digit is a prime.

The answer is $\boxed{\frac{2}{5}\left(9^n+(-1)^{n+1}\right)}$.
Suppose $a_n$ denotes the number of $n$-digit numbers that satisfy the condition. We claim $a_n=4\cdot 9^{n-1}-a_{n-1}$, with $a_1=4$.
$\textit{Proof.}$ It is trivial to show that $a_1=4$. Now, we can do casework on whether or not the tens digit of the $n$-digit integer is prime. If the tens digit is prime, we can choose the digits before the units digit in $a_{n-1}$ ways and choose the units digit in $3$ ways, since it must be prime and not equal to the tens digit. Therefore, there are $3a_{n-1}$ ways in this case.
If the tens digit is not prime, we can use complementary counting. First, we consider the number of $(n-1)$-digit integers that do not have consecutive digits. There are $9$ ways to choose the first digit and $9$ ways to choose the remaining digits. Thus, there are $9^{n-1}$ integers that satisfy this. Therefore, the number of those $(n-1)$-digit integers whose units digit is not prime is $9^{n-1}-a_{n-1}$. It is easy to see that there are $4$ ways to choose the units digit, so there are $4\left(9^{n-1}-a_{n-1}\right)$ numbers in this case. It follows that
and our claim has been proven.
Then, we can use induction to show that $a_n=\frac{2}{5}\left(9^n+(-1)^{n+1}\right)$. It is easy to see that our base case is true, as $a_1=4$. Then,
which is equal to
as desired. $\square$
Solution by TheUltimate123.

The answer is $\boxed{\frac{2}{5}\left(9^n-(-1)^{n}\right)}$.
As in the first solution, let $a_n$ denote the number of $n$-digit numbers that satisfy the condition.  Clearly $a_1 = 4$ and $a_2 = 32$.  We claim that for $n \geq 3$ we have the recurrence $a_n = 8a_{n-1} + 9a_{n-2}$.
To prove this, we split the $n$-digit numbers satisfying the conditions into cases depending on whether or not the second digit is $0$.   If the second digit is nonzero, our number is formed from one of the $a_{n-1}$ numbers with one fewer digit satisfying the conditions, times $8$ possible choices of adding a digit to the left.  If the second digit is zero, our number is formed from one of the $a_{n-2}$ numbers with two fewer digits satisfying the conditions, times $9$ possible choices of adding $0$ and then any nonzero digit to the left.  This proves our claim.
This gives us a linear three-term recurrence.  It is well-known that its solution is of the form $c_1r_1^n + c_2r_2^n$, where the $c_i$ are constants to be determined from the initial conditions $a_1$ and $a_2$, and $r_1$ and $r_2$ are the roots of the corresponding quadratic equation $x^2 = 8x + 9$.  We solve and get $(x-9)(x+1) = 0$, so our roots are $r_1 = 9$ and $r_2 = -1$.  Now, we use our conditions $a_1 = 4$ and $a_2 = 32$ to derive the system of linear equations

Solving this system yields $c_1 = \frac{2}{5}$ and $c_2 = -\frac{2}{5}$, and we are done.
Solution by putnam-lowell.

The answer is $\boxed{\frac{2}{5}\left(9^n-(-1)^{n}\right)}$.
As in the first solution, let $a_n$ denote the number of $n$-digit numbers that satisfy the condition. Clearly $a_1 = 4$ and $a_2 = 32$.
From here, we proceed by complementary counting. We first count the total amount of numbers that satisfy both bullets but that may have zero as its first digit. The units digit can be one of four primes, and each digit to the left will have 9 choices (any digit but the one that was just used). Then the total for this group of numbers is just $4*9^{n-1}$.
Now we must subtract all numbers in the above group that have 0 as its first digit. This is just $a_{n-1}$ because for each number in the first group beginning with a zero, we could take away the zero, leaving us with a number that works for the case $n-1$ (this is true because the next number would not be zero, or the consecutive digit requirement would be violated). Then we have the recursive formula $a_n = 4*9^{n-1}-a_{n-1}$.
To simplify this, we take a look at the first few terms. We see that

We see a pattern where $a_n = 4(9^{n-1}-9^{n-2}+9^{n+3}...+(-1)^{n-1}9^0)$ and we can prove that it holds for all $a_n$ because subtracting $a_{n-1}$ from $4(9^n)$ is the same thing as reversing all previous signs of the preceding powers of 9. This constitutes an alternating pattern, which we can calculate as a geometric series. The first term is $4(9^{n-1})$ and the common ratio is $-\frac{1}{9}$, so

We are done.
Solution by aopsal

Let $f(n)$ denote the number of $n$-digit positive integers satisfying the conditions listed in the problem.
Claim 1: $f(n) = 8f(n-1) + 9f(n-2).$
To prove this, let $k$ be the leftmost digit of the $n$-digit positive integer. When $k$ ranges from $1$ to $9,$ the allowable second-to-leftmost digits is the set $\{0, 1, 2, …, 9\},$ with $k$ excluded. Note that since $1, 2, …, 9$ are all repeated $8$ times and using our definition of $f(n)$ (since $n$-digit positive integers must begin with a positive digit), we have proved that $8f(n-1)$ part. Since $0$ is repeated $9$ times, and since digits that are allowed to be adjacent to the $0$ (the third-to-leftmost digit of our positive integer) are integers ranging from $1$ to $9,$ we have proved the $9f(n-2)$ part similarly. We can see that $\frac{f(1)}{4} = 1$ and $\frac{f(2)}{4} = 8,$ by simple computation. These will be our base cases.
Now, let $s(n) = \frac{f(n)}{4}.$
Claim 2: $s(n+1) = 9s(n) + (-1)^n$
We can prove this using induction. Let $s(a) = k$ and $s(a+1) = 9k - 1.$ By plugging $k$ and $9k - 1$ into our formula $s(a+2) = 8s(a+1) + 9s(a),$ we obtain Now, by plugging $9k - 1$ and $81k - 8$ into the same formula, we obtain $s(a+3) = 8(81k - 8) + 9(9k - 1) = 729k - 73 = 9s(a+2) - 1.$ Since with $a+2$ and $a+3$ we’re back where we started (this is since $s(a+3) = 9s(a+2) - 1$ just like $s(a+1) = 9s(a) - 1$), and using our base cases of $s(1) = 1$ and $s(2) = 8,$ our induction is complete.
Claim 3: $s(n) = \frac{9^n + (-1)^{n+1}}{10}$
We can prove that by simply using our base case of $s(1) = 1$ and repeatedly using the distributive property to obtain further values of $s(n).$ For the case where $n$ is even, we can manipulate the summation into $\sum_{i=0}^{\frac{n}{2} - 1} 8 \cdot 9^{2i}$ which equals $\frac{8 \cdot 9^{n} - 1}{9^2 - 1} = \frac{9^n - 1}{10},$ by geometric series. For the case where $n$ is odd, we can manipulate the summation into $1 + \sum_{i=0}^{\frac{n-1}{2} - 1} 8 \cdot 9^{2i + 1}$ which equals Thus, we have proved Claim 3 for both odd and even $n.$
Since $f(n) = 4s(n),$ our answer is $4 \cdot \frac{9^n + (-1)^{n+1}}{10} = \boxed{ \frac{2}{5} (9^n + (-1)^{n+1})}.$
-fidgetboss_4000

Let $a_n$ be the number of $n$-digit numbers that satisfy the condition that most-left digit different than $0$. Let $b_n$ be the number of $n$-digit numbers that satisfy the condition that most-left digit is $0$. We can write that

and so we find that

$x+1$ is the characteristic polynomial of the homogeneous recurrence relation $a_n + a_{n-1}  = 0$. Then $x=-1$ is a root. Also, by the non-homogeneous part of $4\cdot 9^{n-1}$, we understand that $x=9$ is another root of the recurrence relation $(1)$ with the complementary solution idea. Therefore, $(a_n)$ sequence in the form
We can calculate that $C_1 = \dfrac{2}{5}, C_2 = - \dfrac{2}{5}$ with using $a_1=4, a_2=32$. Thus we get:
Lokman GÖKÇE


Let $a,b,c$ be positive real numbers such that $a+b+c=4\sqrt[3]{abc}$. Prove that

WLOG let $a \leq b \leq c$. Add $2(ab+bc+ca)$ to both sides of the inequality and factor to get:
By substituting $a+b+c=4\sqrt[3]{abc}$, we get:

The last inequality is true by AM-GM. Since all these steps are reversible, the proof is complete.

WLOG let $a \geq b \geq c$. Note that the equations are homogeneous, so WLOG let $c=1$.
Thus, the inequality now becomes $2ab + 2a + 2b + 4 \geq a^2 + b^2 + 1$, which simplifies to $2(a+b) + 3 \geq (a-b)^2$.
Now we will use the condition. Letting $x=a+b$ and $y=a-b$, we have
$x+1=\sqrt[3]{16(x^2-y^2)} \implies 16y^2=-x^3+13x^2-3x-1$.
Plugging this into the inequality, we have $2x+3 \geq \frac{1}{16}(-x^3+13x^2-3x-1) \implies x^3-13x^2+35x+49 = (x-7)^2(x+1) \geq 0$, which is true since $x \geq 0$.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


($*$) Let $ABCD$ be a quadrilateral inscribed in circle $\omega$ with $\overline{AC} \perp \overline{BD}$. Let $E$ and $F$ be the reflections of $D$ over lines $BA$ and $BC$, respectively, and let $P$ be the intersection of lines $BD$ and $EF$. Suppose that the circumcircle of $\triangle EPD$ meets $\omega$ at $D$ and $Q$, and the circumcircle of $\triangle FPD$ meets $\omega$ at $D$ and $R$. Show that $EQ = FR$.

First we have that $BE=BD=BF$ by the definition of a reflection. Let $\angle DEB = \alpha$ and $\angle DFB = \beta.$ Since $\triangle DBE$ is isosceles we have $\angle BDE = \alpha.$ Also, we see that $\angle BDE = \angle CAB = \angle CDB = \alpha,$ using similar triangles and the property of cyclic quadrilaterals. Similarly,  Now, from $BE=BD=BF$ we know that $B$ is the circumcenter of $\triangle DEF.$ Using the properties of the circumcenter and some elementary angle chasing, we find that
Now, we claim that $Q$ is the intersection of ray $\overrightarrow{EB}$ and the circumcircle of $ABCD.$ To prove this, we just need to show that $DEPQ$ is cyclic by this definition of $Q.$ We have that  We also have from before that  so $\angle DQE=\angle DPE$ and this proves the claim.
We can use a similar proof to show that $F, B, R$ are collinear.
Now, $DP$ is the radical axis of the circumcircles of $\triangle EDP$ and $\triangle FDP.$ Since $B$ lies on $DP,$ and $E, Q$ lie on the circumcircle of $\triangle EPD$ and $F, R$ lie on the circumcircle of $\triangle FPD,$ we have that  However, $BF=BE,$ so $BR=BQ.$ Since $E, B, Q$ are collinear and so are $F, B, R$ we can add these $2$ equations to get  which completes the proof.
~nukelauncher
(Monday G. Fern)

We begin with the following claims.
Claim. $B$ is the circumcenter of $\triangle DEF$.
Proof. By reflection $BD=BE=BF$.
Claim. $A$ is the circumcenter of $\triangle EPD$.
Proof. First, we have
Then
Then $2\angle ADE = 180^{\circ}-2(180^{\circ}-\angle DPE) \implies \angle DAE = 2(180^{\circ}-\angle DPE)$. This is enough to imply what we desire. \newline
Claim. $C$ is the circumcenter of $\triangle FPD$.
Proof. Similar to above.
Claim. $E, B, Q$ are collinear.
Proof. We have
Claim.$F, B, R$ are collinear.
Proof. Similar to above.
Since $DEPQ$ is cyclic, $\triangle EBP \sim \triangle DBQ$. However, $BE=BD$, so $BP=BQ$. Similarly, $BP=BR$. Finishing, we have , as desired. $\blacksquare$ ~MSC
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Triangle $ABC$ is inscribed in a circle of radius $2$ with $\angle ABC \geq 90^\circ$, and $x$ is a real number satisfying the equation $x^4 + ax^3 + bx^2 + cx + 1 = 0$, where $a=BC,b=CA,c=AB$. Find all possible values of $x$.

Solution:
Notice that

Thus, if $b > \frac{a^2}{4} + \frac{c^2}{4},$ then the expression above is strictly greater than $0$ for all $x,$ meaning that $x$ cannot satisfy the equation $x^4 + ax^3 + bx^2 + cx + 1 = 0.$ It follows that $b\le\frac{a^2}{4} + \frac{c^2}{4}.$
Since $\angle ABC\ge 90^{\circ},$ we have $b^2\ge a^2 + c^2.$ From this and the above we have $4b\le a^2 + c^2\le b^2,$ so $4b\le b^2.$ This is true for positive values of $b$ if and only if $b\ge 4.$ However, since $\triangle ABC$ is inscribed in a circle of radius $2,$ all of its side lengths must be at most the diameter of the circle, so $b\le 4.$ It follows that $b=4.$
We know that $4b\le a^2 + c^2\le b^2.$ Since $4b = b^2 = 16,$ we have $4b = a^2 + c^2 = b^2 = 16.$
The equation $x^4 + ax^3 + bx^2 + cx + 1 = 0$ can be rewritten as $\left(x^2 + \frac{a}{2}x\right)^2 + \left(\frac{c}{2}x + 1\right)^2 = 0,$ since $b = \frac{a^2}{4} + \frac{c^2}{4}.$ This has a real solution if and only if the two separate terms have zeroes in common. The zeroes of $\left(x^2 + \frac{a}{2}x\right)^2$ are $0$ and $-\frac{a}{2},$ and the zero of $\left(\frac{c}{2}x + 1\right)^2 = 0$ is $-\frac{2}{c}.$ Clearly we cannot have $0=-\frac{2}{c},$ so the only other possibility is $-\frac{a}{2} = -\frac{2}{c},$ which means that $ac = 4.$
We have a system of equations: $ac = 4$ and $a^2 + c^2 = 16.$ Solving this system gives $(a, c) = \left(\sqrt{6}+\sqrt{2}, \sqrt{6}-\sqrt{2}\right), \left(\sqrt{6}-\sqrt{2}, \sqrt{6}+\sqrt{2}\right).$ Each of these gives solutions for $x$ as $-\frac{\sqrt{6}+\sqrt{2}}{2}$ and $-\frac{\sqrt{6}-\sqrt{2}}{2},$ respectively. Now that we know that any valid value of $x$ must be one of these two, we will verify that both of these values of $x$ are valid.
First, consider a right triangle $ABC,$ inscribed in a circle of radius $2,$ with side lengths $a = \sqrt{6}+\sqrt{2}, b = 4, c = \sqrt{6}-\sqrt{2}.$ This generates the polynomial equation

This is satisfied by $x=-\frac{\sqrt{6}+\sqrt{2}}{2}.$
Second, consider a right triangle $ABC,$ inscribed in a circle of radius $2,$ with side lengths $a = \sqrt{6}-\sqrt{2}, b = 4, c = \sqrt{6}+\sqrt{2}.$ This generates the polynomial equation

This is satisfied by $x=-\frac{\sqrt{6}-\sqrt{2}}{2}.$
It follows that the possible values of $x$ are $-\frac{\sqrt{6}+\sqrt{2}}{2}$ and $-\frac{\sqrt{6}-\sqrt{2}}{2}.$
Fun fact: these solutions correspond to a $15$-$75$-$90$ triangle.
(sujaykazi)
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Let $p$ be a prime, and let $a_1, \dots, a_p$ be integers. Show that there exists an integer $k$ such that the numbers produce at least $\tfrac{1}{2} p$ distinct remainders upon division by $p$.

Solution:
$\textbf{Lemma: }$ For fixed $i\neq j,$ where $i, j\in\{1, 2, ..., p\},$ the statement $a_i + ik\equiv a_j + jk\text{ (mod } p\text{)}$ holds for exactly one $k\in {1, 2, ..., p}.$
$\textbf{Proof: }$ Notice that the left side minus the right side is congruent to $(a_i - a_j) + (i - j)k$ modulo $p.$ For this difference to equal $0,$ there is a unique solution for $k$ modulo $p$ given by $k\equiv (a_j - a_i)(i - j)^{-1}\text{ (mod } p\text{)},$ where we have used the fact that every nonzero residue modulo $p$ has a unique multiplicative inverse. Therefore, there is exactly one $k\in {1, 2, ..., p}$ that satisfies $a_i + ik\equiv a_j + jk\text{ (mod } p\text{)}$ for any fixed $i\neq j. \textbf{ End Lemma}$
Suppose that you have $p$ graphs $G_1, G_2, ..., G_p,$ and graph $G_k$ consists of the vertices $(i, k)$ for all $1\le i\le p.$ Within any graph $G_k,$ vertices $(i_1, k)$ and $(i_2, k)$ are connected by an edge if and only if $a_{i_1} + i_1k\equiv a_{i_2} + i_2k\text{ (mod } p\text{)}.$ Notice that the number of disconnected components of any graph $G_k$ equals the number of distinct remainders when divided by $p$ given by the numbers $a_1 + k, a_2 + 2k, ..., a_p + pk.$
These $p$ graphs together have exactly one edge for every unordered pair of elements of $\{1, 2, ..., p\},$ so they have a total of exactly $\frac{p(p-1)}{2}$ edges. Therefore, there exists at least one graph $G_k$ that has strictly fewer than $\frac{p}{2}$ edges, meaning that it has more than $\frac{p}{2}$ disconnected components. Therefore, the collection of numbers $\{a_i + ik: 1\le i\le p\}$ for this particular value of $k$ has at least $\frac{p}{2}$ distinct remainders modulo $p.$ This completes the proof.
(sujaykazi)
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Karl starts with $n$ cards labeled $1,2,3,\dots,n$ lined up in a random order on his desk. He calls a pair $(a,b)$ of these cards swapped if $a>b$ and the card labeled $a$ is to the left of the card labeled $b$. For instance, in the sequence of cards $3,1,4,2$, there are three swapped pairs of cards, $(3,1)$, $(3,2)$, and $(4,2)$.
He picks up the card labeled 1 and inserts it back into the sequence in the opposite position: if the card labeled 1 had $i$ card to its left, then it now has $i$ cards to its right. He then picks up the card labeled $2$ and reinserts it in the same manner, and so on until he has picked up and put back each of the cards $1,2,\dots,n$ exactly once in that order. (For example, the process starting at $3,1,4,2$ would be $3,1,4,2\to 3,4,1,2\to 2,3,4,1\to 2,4,3,1\to 2,3,4,1$.)
Show that no matter what lineup of cards Karl started with, his final lineup has the same number of swapped pairs as the starting lineup.

Solution:
Note that in this solution, the term "inversions" is used synonymously with "swapped pairs."
We define a new process $P'$ where, when re-inserting card $i$, we additionally change its label from $i$ to $n+i$. For example, an example of $P'$ also starting with $3142$ is:

Note that now, each step of $P'$ preserves the number of inversions. Moreover, the final configuration of $P'$ is the same as the final configuration of $P$ with all cards incremented by $n$, and thus, of course, has the same number of inversions.
~ v_enhance (clarified by integralarefun)
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


There are $a+b$ bowls arranged in a row, numbered $1$ through $a+b$, where $a$ and $b$ are given positive integers. Initially, each of the first $a$ bowls contains an apple, and each of the last $b$ bowls contains a pear.
A legal move consists of moving an apple from bowl $i$ to bowl $i+1$ and a pear from bowl $j$ to bowl $j-1$, provided that the difference $i-j$ is even. We permit multiple fruits in the same bowl at the same time. The goal is to end up with the first $b$ bowls each containing a pear and the last $a$ bowls each containing an apple. Show that this is possible if and only if the product $ab$ is even.

Solution:
Claim: If $a$ and $b$ are both odd, then the end goal of achieving $b$ pears followed by $a$ apples is impossible.
Proof: Let $A_1$ and $P_1$ denote the number of apples and the number of pears in odd-numbered positions, respectively. We show that $A_1 - P_1$ is invariant. Notice that if $i$ and $j$ are odd, then $A_1$ and $P_1$ both decrease by 1, as one apple and one pear are both moved from odd-numbered positions to even-numbered positions. If $i$ and $j$ are even, then $A_1$ and $P_1$ both increase by 1.
Because the starting configuration $aa\ldots ab\ldots b$ has $\left\lfloor \frac{a}{2} \right\rfloor + 1$ odd-numbered apples and $\left\lfloor \frac{b}{2} \right\rfloor$ odd-numbered pears, the initial value of $A_1 - P_1$ is $\left\lfloor \frac{a}{2} \right\rfloor - \left\lfloor \frac{b}{2} \right\rfloor + 1$. But the desired ending configuration has $\left\lfloor \frac{b}{2}\right\rfloor + 1$ odd-numbered pears and $\left\lfloor \frac{a}{2} \right\rfloor$ odd-numbered apples, so $A_1 - P_1 = \left\lfloor \frac{a}{2} \right\rfloor - \left\lfloor \frac{b}{2} \right\rfloor - 1$. As $A_1 - P_1$ is invariant, it is impossible to attain the desired ending configuration. $\blacksquare$
Claim: If at least one of $a$ and $b$ is even, then the end goal of achieving $b$ pears followed by $a$ apples is possible.
Proof: Without loss of generality, assume $a$ is even. If only $b$ is even, then we can number the bowls in reverse, and swap apples with pears. We use two inductive arguments to show that $(a,b) = (2,b)$ is achievable for all $b\ge 1$, then to show that $(a,b)$ is achievable for all even $a$ and all $b\ge 1$.
Base case: $(a,b) = (2,1)$. Then we can easily achieve the ending configuration in two moves, by moving the apple in bowl #1 and the pear in bowl #3 so that everything is in bowl #2, then finishing the next move.
Inductive step: suppose that for $a \ge 2$ (even) apples and $b \ge 1$ pears, that with $a$ apples and $b$ pears, the ending configuration is achievable. We will show two things: i) achievable with $a$ apples and $b+1$ pears, and ii) achievable with $a+2$ apples and $b$ pears.
i) Apply the process on the $a$ apples and first $b$ pairs to get a configuration $bb\ldots ba\ldots ab$. Now we will "swap" the leftmost apple with the last pear by repeatedly applying the move on just these two fruits (as $a$ is even, the difference $i-j$ is even). This gives a solution for $a$ apples and $b+1$ pears. In particular, this shows that $(a,b) = (2,b)$ for all $b\ge 1$ is achievable.
ii) To show $(a+2, b)$ is achievable, given that $(a,b)$ is achievable, apply the process on the last $a$ apples and $b$ pears to get the configuration $aabbb\ldots baaa\ldots a$. Then, because we have shown that 2 apples and $b$ pears is achievable in i), we can now reverse the first two apples and $b$ pears.
Thus for $ab$ even, the desired ending configuration is achievable. $\blacksquare$
Combining the above two claims, we see that this is possible if and only if $ab$ is even. -scrabbler94

"If" part:
Note that two opposite fruits can be switched if they have even distance. If one of $a$, $b$ is odd and the other is even, then switch $1$ with $a+b$, $2$ with $a+b-1$, $3$ with $a+b-2$... until all of one fruit is switched. If both are even, then if $a>b$, then switch $1$ with $a+1$, $2$ with $a+2$, $3$ with $a+3$... until all of one fruit is switched; if $a<b$ then switch $a$ with $a+b$, $a-1$ with $a+b-1$, $a-2$ with $a+b-2$... until all of one fruit is switched. Each of these processes achieve the end goal.
"Only if" part:
Assign each apple a value of $1$ and each pear a value of $-1$. At any given point in time, let $E$ be the sum of the values of the fruit in even-numbered bowls. Because $a$ and $b$ both are odd, at the beginning there are $\frac{a-1}{2}$ apples in even bowls and $\frac{b+1}{2}$ pears in even bowls, so at the beginning $E=\frac{a-b}{2}-1$. After the end goal is achieved, there are $\frac{a+1}{2}$ apples in even bowls and $\frac{b-1}{2}$ pears in even bowls, so after the end goal is achieved $E=\frac{a-b}{2}+1$. However, because two opposite fruits must have the same parity to move and will be the same parity after they move, we see that $E$ is invariant, which is a contradiction; hence, it is impossible for the end goal to be reached if $ab$ is odd.
Stormersyle

We define a cycle to be when $2$ fruits in bowls $i$ and $j$ are swapped with eachother, provided that bowls $i$ contains an apple, bowl $j$ contains a pear, and the difference $i-j$ is even.
We claim that a cycle consists of only the valid moves described in the problem statement.
Proof: We can move the apple and pear one step at a time to eventually reach the other's bowl(i.e. the apple moves to $i+1$ and the pear moves to bowl $j-1$ at the beginning) using only valid moves. By a simple parity argument(if $k$ moves have already been done, $i+k-(j-k)=i+j+2k=0+2k=2k=0 \textbf{mod 2}$), these moves are always valid, so we are done. $\blacksquare$
We now split the "if" part of this proof into cases based on the parities of $a$ and $b$.
Case 1: $a$ even, $b$ odd
In this case we can simply cycle the fruit in bowl $k+1$ with the fruit in bowl $a+b-k$ for all integer $k$ in the range $[0,b-1]$ to achieve our desired goal. The difference $a+b-k-k-1=a+b-1$ is even, so the move is valid.
Case 2: $b$ even, $a$ odd
Using the same cycle as the previous case works here.
Case 3: $a$ even, $b$ even
Here, we can cycle the fruits in bowls $k$ and $a+b-k$ for all integer $k$ in the range $[1,b]$. Then, we finish by cycling the fruits in bowls $a$ and $a+b$. These are both valid moves by similar parity arguments as done in Case 1.
Since we have exhausted all possible cases for the "if" part of this proof, we have completed the if part. We will proceed with the "only if" part.
We let the number of apples in odd positions be $A_1$, and the number of pears in odd positions be $A_2$. Obviously $A_1-A_2$ is invariant when using valid moves only. We can now use proof by contradiction(i.e. showing that this invariant does not occur when $a, b \equiv 1 \text{ mod } 2$ and our desired goal is achieved) to find that we have that $0=2$, which is obviously false, so we have completed the proof for the "only if" part.
We are now done, since we have completed our proofs for the "if" and "only if" parts. $\blacksquare$
~smartninja2000

Begin by defining a $\textit{swap}$ as a set of $i - j$ legal moves taking an apple in $i \rightarrow j$ and the pear in $j \rightarrow i$. Now we begin by proving if $ab$ is even, then the final configuration is possible.
WLOG let $b$ be even. Then there are two cases to consider. $a < b, a \ge b$ to provide valid constructions for. In the first case, consider the apple/pear pairs $(1,b+1), (2, b+2), \dots, (i, b+i), \dots, (a, b+a)$ and swap them. This results in the transformation,

as desired.
Now consider the case where $a \ge b$. Also consider the pairing, $(a-b + 1, a + 1), (a - b + 2, a+2), \dots, (a - b + i, a+i), \dots, (a, a + b)$ and swap them. This results in the transformation,

Now just consider the leftmost $a$ bowls. There are $a-b$ apples, and then $b$ pears. We have effectively reduced $(a,b) \rightarrow (a-b, b)$. Reducing in this fashion recursively will lead to $(a \pmod{b}, b)$ which can be constructed with the $a<b$ case. This finishes the construction for $a \ge b$.
Now assume $ab,a,b$ are odd. FTSOC, let this case satisfy the claim. Then, for each apple, define it's $\textit{position}$ as the sum of the distance from it to all other pairs. So for apple in bowl $i \le a$ originally, the position of $i$ is $\sum_{j = a+1}^{b} j - i .$
Every time a legal move is made, the position of the apple decreases by $b - 1 + 2 = b+1$ (from the $b-1$ pears not part of the move and the decrease in $2$ by the corresponding pear). Also note that there needs to be exactly $ab$ moves in order to attain the final configurations. So the difference in sum of positions of the apples at the beginning and end is $ab(b+1)$. Mathematically,

A symmetric argument for the position of pears gives $b = 1$. Clearly the $a=b=1$ does not have a solution, therefore we have contradiction. $\square$
~ Aaryabhatta1
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Let $\mathbb Z$ be the set of all integers. Find all pairs of integers $(a,b)$ for which there exist functions $f:\mathbb Z\rightarrow\mathbb Z$ and $g:\mathbb Z\rightarrow\mathbb Z$ satisfying  for all integers $x$.

We claim that the answer is $|a|=|b|$.
Proof:
$f$ and $g$ are surjective because $x+a$ and $x+b$ can take on any integral value, and by evaluating the parentheses in different order, we find $f(g(f(x)))=f(x+b)=f(x)+a$ and $g(f(g(x)))=g(x+a)=g(x)+b$. We see that if $a=0$ then $g(x)=g(x)+b$ to $b=0$ as well, so similarly if $b=0$ then $a=0$, so now assume $a, b\ne 0$.
We see that if $x=|b|n$ then $f(x)\equiv f(0) \pmod{|a|}$, if $x=|b|n+1$ then $f(x)\equiv f(1)\pmod{|a|}$, if $x=|b|n+2$ then $f(x)\equiv f(2)\pmod{|a|}$... if $x=|b|(n+1)-1$ then $f(x)\equiv f(|b|-1)\pmod{|a|}$. This means that the $b$-element collection $\left\{f(0), f(1), f(2), ... ,f(|b|-1)\right\}$ contains all $|a|$ residues mod $|a|$ since $f$ is surjective, so $|b|\ge |a|$. Doing the same to $g$ yields that $|a|\ge |b|$, so this means that only $|a|=|b|$ can work.
For $a=b$ let $f(x)=x$ and $g(x)=x+a$, and for $a=-b$ let $f(x)=-x$ and $g(x)=-x-a$, so  $|a|=|b|$ does work and are the only solutions, as desired.
-Stormersyle

We claim that $f$ and $g$ exist if and only if $|a|=|b|$.
Only If:
For some fixed $j$, let $f(j)=k$.
If $b=0$, then $g(k)=j$. Suppose $a\ne 0$. Then $f(j)=f(g(k))=k+a\ne k$, a contradiction. Thus, $a=0$. Similarly, if $a=0$, then $b=0$, satisfying $|a|=|b|$.
Otherwise, $a,b\ne 0$. We know that $g(k)=g(f(j))=j+b$, $f(j+b)=f(g(k))=k+a$, $g(k+a)=j+2b$, and so on: $f(j+nb)=k+na$ and $g(k+na)=j+(n+1)b$ for $n\ge 0$.
Consider the value of $g(k-a)$. Suppose $g(k-a)=j'\ne j$. Then $f(j')=k$ and $g(f(j'))=j+b\ne j'+b$, a contradiction. Thus, $g(k-a)=j$. We repeat with $f(j-b)$. Suppose $f(j-b)=k'-b\ne k-b$. Then $g(k'-b)=j$ and $f(g(k'-b))=k\ne k'$, a contradition. Thus, $f(j-b)=k-b$. Continuing, $g(k-2a)=j-a$, and so on: $f(j+nb)=k+na$ and $g(k+na)=j+(n+1)b$ now for all $n$.
This defines $f(x)$ for all $x\equiv j\pmod{|b|}$ and $g(x)$ for all $x\equiv f(j)\pmod{|a|}$.
This means that $x\equiv j\pmod{|b|}\implies f(x)\equiv f(j)\pmod{|a|}$, and $y\equiv f(j)\pmod{|a|}\implies g(y)\equiv j\pmod{|b|}$ which implies $f(x)\equiv f(j)\pmod{|a|}\implies x\equiv j\pmod{|b|}$.
As a result, $f(x)$ maps each residue mod $|b|$ to a unique residue mod $|a|$, so $|a|\ge|b|$. Similarly, $g(x)$ maps each residue mod $|a|$ to a unique residue mod $|b|$, so $|b|\ge|a|$. Therefore, $|a|=|b|$.
If:
$|a|=|b|$ means that either $a=b$ or $a=-b$. $f(x)=x,g(x)=x+a$ works for the former and $f(x)=-x,g(x)=-x-a$ works for the latter, and we are done.
~emerald_block
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Let $ABCD$ be a cyclic quadrilateral satisfying $AD^2+BC^2=AB^2$. The diagonals of $ABCD$ intersect at $E$. Let $P$ be a point on side $\overline{AB}$ satisfying $\angle APD=\angle BPC$. Show that line $PE$ bisects $\overline{CD}$.

Let $PE \cap DC = M$. Also, let $N$ be the midpoint of $AB$.
Note that only one point $P$ satisfies the given angle condition. With this in mind, construct $P'$ with the following properties:
$AP' \cdot AB = AD^2 \quad \text{and} \quad BP' \cdot AB = CD^2$
Claim: $P = P'$
Proof:
The conditions imply the similarities $ADP \sim ABD$ and $BCP \sim BAC$ whence $\measuredangle APD = \measuredangle BDA = \measuredangle BCA = \measuredangle CPB$ as desired. $\square$
Claim: $PE$ is a symmedian in $AEB$
Proof:
We have

as desired. $\blacksquare$
Since $P$ is the isogonal conjugate of $N$, $\measuredangle PEA = \measuredangle MEC = \measuredangle BEN$. However $\measuredangle MEC = \measuredangle BEN$ implies that $M$ is the midpoint of $CD$ from similar triangles, so we are done. $\blacksquare$
~sriraamster

By monotonicity, we can see that the point $P$ is unique. Therefore, if we find another point $P'$ with all the same properties as $P$, then $P = P'$
Part 1) Let $N$ be a point on $\overline{AB}$ such that $AN\cdot AB = AD^2$, and $BN \cdot AB = BC^2$. Obviously $N$ exists because adding the two equations gives $AN\cdot AB + BN \cdot AB = AD^2 + BC^2 = AB^2$, which is the problem statement. Notice that converse PoP givesTherefore, $\angle AND = \angle ADB = \angle ACB = \angle CNB$, so $N$ does indeed satisfy all the conditions $P$ does, so $N = P$. Hence, $\bigtriangleup ADP \sim \bigtriangleup ABD$ and $\bigtriangleup CBP \sim\bigtriangleup ABC$.
Part 2) Define $G$ as the midpoint of $CD$. Furthermore, create a point $X$ such that $DX || EC$ and $CX || ED$. Obviously $XCED$ must be a parallelogram. Now we set up for Jacobi's. The problem already gives us that $\angle APD = \angle CPB$, which is good for starters. Furthermore, $\bigtriangleup ADP \sim \bigtriangleup ABD$ tells us thatThis gives us our second needed angle equivalence. Lastly, $\bigtriangleup CBP \sim\bigtriangleup ABC$ will givewhich is our last necessary angle equivalence to apply Jacobi's. Finally, applying Jacobi's tells us that $AC$, $BD$, and $XP$ are concurrent $\implies$ $X$, $E$, $P$ collinear. Additionally, since parallelogram diagonals bisect each other, $X$, $G$, and $E$ are collinear, so finally we obtain that $P$, $E$, and $G$ are collinear, as desired.
-jj_ca888
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


$(*)$ Let $ABC$ be a triangle with $\angle ABC$ obtuse. The $A$-excircle is a circle in the exterior of $\triangle ABC$ that is tangent to side $\overline{BC}$ of the triangle and tangent to the extensions of the other two sides. Let $E$, $F$ be the feet of the altitudes from $B$ and $C$ to lines $AC$ and $AB$, respectively. Can line $EF$ be tangent to the $A$-excircle?

Instead of trying to find a synthetic way to describe $EF$ being tangent to the $A$-excircle (very hard), we instead consider the foot of the perpendicular from the $A$-excircle to $EF$, hoping to force something via the length of the perpendicular.  It would be nice if there were an easier way to describe $EF$, something more closely related to the $A$-excircle; as we are considering perpendicularity, if we could generate a line parallel to $EF$, that would be good.
So we recall that it is well known that triangle $AEF$ is similar to $ABC$.  This motivates reflecting $BC$ over the angle bisector at $A$ to obtain $B'C'$, which is parallel to $EF$ for obvious reasons.
Furthermore, as reflection preserves intersection, $B'C'$ is tangent to the reflection of the $A$-excircle over the $A$-angle bisector.  But it is well-known that the $A$-excenter lies on the $A$-angle bisector, so the $A$-excircle must be preserved under reflection over the $A$-excircle.  Thus $B'C'$ is tangent to the $A$-excircle.Yet for all lines parallel to $EF$, there are only two lines tangent to the $A$-excircle, and only one possibility for $EF$,  so $EF = B'C'$.
Thus as $ABB'$ is isoceles,  contradiction. -alifenix-

The answer is no.
Suppose otherwise. Consider the reflection over the bisector of $\angle BAC$. This swaps rays $AB$ and $AC$; suppose $E$ and $F$ are sent to $E'$ and $F'$. Note that the $A$-excircle is fixed, so line $E'F'$ must also be tangent to the $A$-excircle.
Since $BEFC$ is cyclic, we obtain $\measuredangle ECB = \measuredangle EFB = \measuredangle EF'E'$, so $\overline{E'F'} \parallel \overline{BC}$. However, as $\overline{EF}$ is a chord in the circle with diameter $\overline{BC}$, $EF \le BC$.
If $EF < BC$ then $E'F' < BC$ too, so then $\overline{E'F'}$ lies inside $\triangle ABC$ and cannot be tangent to the excircle.
The remaining case is when $EF = BC$. In this case, $\overline{EF}$ is also a diameter, so $BECF$ is a rectangle. In particular $\overline{BE} \parallel \overline{CF}$. However, by the existence of the orthocenter, the lines $BE$ and $CF$ must intersect, contradiction.

The answer is $\boxed{\text{no}}$.
Suppose for the sake of contradiction that it is possible for $EF$ to be tangent to the $A$-excircle. Call the tangency point $T$, and let $S_1, S_2$ denote the contact points of $AB, AC$ with the $A$-excircle, respectively. Let $s$ denote the semiperimeter of $ABC$. By equal tangents, we have It is also well known that $AS_1 = AS_2 = \frac{s}{2}$, so It is well known (by an easy angle chase) that $\triangle AEF \sim \triangle ABC$, so we must have the ratio of similitude is $2$. In particular, This results in which is absurd since $\triangle BEC$ is a right triangle. We reached a contradiction, so we are done. $\blacksquare$ ~ Mathscienceclass

We claim that the answer is no. We proceed with contradiction. Suppose that $EF$ is indeed tangent to the a-excenter. Define the point of tangency to be $X$. Let $G$ to be the intersection of the a-excircle with the extension of $AB$ and $H$ to be the intersection of the a-excircle with the extension of $AC$. Define $I_a$ to be the a-excenter. It is a well-known fact that $I_a$ lies on the angle bisector of $\angle BAC$.
For convenience, let $AB = c, AC = b, BC = a$, $\angle CAB = A, \angle CBA = B, \angle ACB = C$.
Notice that by Power of a Point:

Therefore, adding, we see that:

It would be rather nice if we could re-write $FG$. Indeed, we can:

and similarly for $FH$:

We now seek to re-write $FE$. Using the law of cosines:

Therefore,

Putting this all together, we see that:

Now, we seek to write $\tan \left(\frac{a}{2} \right)$ in terms of the side lengths of the triangle. Notice that:

where $s$ is the semi-perimeter. We get that:

Using the fact that $\cos^2 \left(\frac{A}{2} \right) + \sin^2 \left(\frac{A}{2} \right) = 1$, we have that:

Therefore,

Returning to our original problem:

It is a well-known fact that $r_a = \sqrt{\frac{s(s-b)(s-c)}{s-a}}$, so:
 which implies that:

which is a contradiction. Hence, our original assumption that $EF$ is tangent to the a-excircle is incorrect. $\blacksquare$
~AopsUser101