For a positive integer $n\geq 3$ plot $n$ equally spaced points around a circle.  Label one of them $A$, and place a marker at $A$.  One may move the marker forward in a clockwise direction to either the next point or the point after that.  Hence there are a total of $2n$ distinct moves available; two from each point.  Let $a_n$ count the number of ways to advance around the circle exactly twice, beginning and ending at $A$, without repeating a move.  Prove that $a_{n-1}+a_n=2^n$ for all $n\geq 4$.

We label the points in clockwise order as $1,2,3,\ldots,n$, where point $A$ is the same as point $1$.  We start and end at point $1$, and we must cross over it, either by visiting it again, or else by making the move from point $n$ to point $2$. We interpret each of these cases in terms of tiling. In each move, we either move one or two points clockwise, so we can think of each move as a $1\times 1$ or $1\times 2$ tile. If the point $1$ is visited in the middle, then the first cycle around the circle can be thought of as a tiling of a $1\times n$ board, and the second cycle around the circle can also be thought of as a $1\times n$ board. We place this second board directly below the first board. Therefore, in this first case, we wish to find the number of tilings of two $1\times n$ boards, and to guarantee that no move is repeated, we cannot have two tiles of the same type lying directly atop each other in the $2\times n$ board. Suppose there are $u_n$ such tilings. It can easily be computed that $u_3=2$ and $u_4=6$ as shown below.

In the second case, where we pass by point $1$ by moving from point $n$ to point $2$, we can similarly think about it in terms of tiling two rows of $1\times n$ boards, but we remove the last square in the first row and the first square in the second row to make sure that we jump from point $n$ to point $2$. Suppose that we can tile such boards in $s_n$ ways. It can be easily computed that $s_3=3$ and $s_4=5$ as shown below.

Since these are the only two possible cases, we see that
For the sake of convenience in determining recurrence relations, we define another type of board with two $1\times n$ boards where a specific corner is removed (without loss of generality, we place this in the lower left hand corner). Let $t_n$ be the number of ways to tile such a board without placeing two of the same type of tile atop each other. Once again, we compute that $t_3=3$ and $t_4=5$ as shown below.

We can determine reccurence relations for $s_n$, $t_n$, and $u_n$ in terms of each other. For $s_n$, note that a tiling can end in one of the three following ways such that the rest of the board can be tiled without restriction (the placed tiles are shaded).

In the first, second, and third cases, we see that we can tile the rest of the board in $t_{n-1}$, $t_{n-2}$, and $s_{n-2}$ ways, respectively. Hence for $n\ge 5$, we see that

For $t_n$, note that a tiling can end in one of the three following ways such that the rest of the board can be tiled without restriction.

In the first, second, and third cases, we see that we can tile the rest of the board in $s_{n-1}$, $s_{n-2}$, and $t_{n-2}$ ways, respectively. Hence for $n\ge 5$, we see that

For $u_n$, note that a tiling can end in one of the two following ways such that the rest of the board can be tiled without restriction.
In either case, we are left with a board with a corner removed, hence we can tile the rest of the board in $t_{n-1}$  ways in each case. Hence for $n\ge 4$, we see that

Subtracting (3) from (2), we find that

Therefore, if $s_{n-1}=t_{n-1}$, then $s_n=t_n$. Since $s_3=t_3$ and $s_4=t_4$, we see that $s_n=t_n$ for all $n\ge 3$. Therefore, (2) can be rewritten as

and (4) can be rewritten as

Now by (1), we know that

In particular, $a_4+a_3=6+5+2+3=2^4$, so the statement is true for $n=4$. Then by (7), and then substituting (5) and (6) (where these are valid for $n\ge 5$), we find

But then by (5), and then substituting $4s_{n-3}=2u_{n-2}$ and $2s_{n-2}=u_{n-1}$ (by (6), and these are valid for $n\ge 6$), we find

We substitute this into (8), finding that for $n\ge 6$,

Therefore, if $a_{n-1}+a_{n-2}=2^{n-1}$, then $a_{n}+a_{n-1}=2^n$. We already know that $a_4+a_3=2^4$. Also, we can compute that

Hence $a_5=s_5+u_5=21$. So as $a_4=s_4+u_4=11$, we find that $a_5+a_4=2^5$. Then we can use (9) for $n\ge 6$ to find by induction that $a_{n}+a_{n-1}=2^n$ for all $n\ge 4$.

We choose the tilings for the first and second pass around the circle simultaneously. As we tile both passes, our state is defined by whether or not we are in a continuation of a length 2 block on the first and second pass. We can't be in a continuation of a length 2 block on both passes, since that would mean we used the same move on the same block on both passes. Thus we have three states: (non-continuation, non-continuation), (non-continuation, continuation), and (continuation, non-continuation), where the elements of each tuple refer to the first and second pass respectively. Listing out the state transitions (while following the rule that we can't use the same move on both passes, and that a continuation must become a non-continuation), we get the transition matrix $T = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{bmatrix} = J-I$, where $J$ is the ones matrix, and $I$ is the identity. We have that $a_n = \left(T^n\right)_{11} + \left(T^n\right)_{23}$. The first term represents the case where we end the first pass at point $A$, and the second term represents the case where we jump over point $A$ when finishing the first pass. Thus it simply remains to compute $T^n$. We have
\begin{align*}
&\mathrel{\phantom{=}} T^n \\
&= (J-I)^n \\
&= \sum_{k=0}^n J^k (-1)^{n-k} {n \choose k} \\
&= J \sum_{k=1}^n 3^{k-1} (-1)^{n-k} {n \choose k} + (-1)^n I \\
&= \frac{1}{3}J\left(2^n-(-1)^n\right) + (-1)^n I
\end{align*}
Thus $a_n = \left(T^n\right)_{11} + \left(T^n\right)_{23} = \frac{2}{3}\left(2^n-(-1)^n\right) + (-1)^n$. Thus, $a_{n-1}+a_n = 2^n$, as desired.

We split this into two cases.
Case 1: The marker lands on $A$ thrice.
This implies that $A$ is touched after one full cycle. Place any nodes not touched in the first cycle in the set $K$.
Lemma 1: Any unique configuration of $K$ such that [Work In Progress]
~SigmaPiE
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Let $n$ be a positive integer.  There are $\tfrac{n(n+1)}{2}$ marks, each with a black side and a white side, arranged into an equilateral triangle, with the biggest row containing $n$ marks.  Initially, each mark has the black side up.  An operation is to choose a line parallel to the sides of the triangle, and flipping all the marks on that line.  A configuration is called admissible if it can be obtained from the initial configuration by performing a finite number of operations.  For each admissible configuration $C$, let $f(C)$ denote the smallest number of operations required to obtain $C$ from the initial configuration.  Find the maximum value of $f(C)$, where $C$ varies over all admissible configurations.

Solution:
This problem needs a solution. If you have a solution for it, please help us out by adding it.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Given positive integers $m$ and $n$, prove that there is a positive integer $c$ such that the numbers $cm$ and $cn$ have the same number of occurrences of each non-zero digit when written in base ten.

This solution is adopted from the official solution. Both the problem and the solution were suggested by Richard Stong.
Without Loss of Generality, suppose $m \geq n \geq 1$. By prime factorization of $n$, we can find a positive integer $c_1$ such that $c_1n=10^s n_1$ where $n_1$ is relatively prime to $10$. If a positive $k$ is larger than $s$, then $(10^k c_1 m - c_1 n)= 10^s t$, where $t=10^{k-s} c_1m-n_1>0$ is always relatively prime to $10$.
Choose a $k$ large enough so that $t$ is larger than $c_1m$. We can find an integer $b\geq 1$ such that $10^b-1$ is divisible by $t$, and also larger than $10c_1m$. For example, let $b=\varphi(t)$ and use Euler's theorem. Now, let $c_2=(10^b-1)/t$, and $c=c_1c_2$. We claim that $c$ is the desired number.
Indeed, since both $c_1m$ and $n_1$ are less than $t$, we see that the decimal expansion of both the fraction $(c_1m)/t = (cm)/(c_2t) = (cm)/(10^b-1)$ and $n_1/t=(c_2n_1)/(10^b-1)$ are repeated in $b$-digit. And we also see that $10^k (c_1m)/t = (t+c_1n)/t= 1+10^s (n_1/t)$, therefore the two repeated $b$-digit expansions are cyclic shift of one another.
This proves that $cm$ and $c_2n_1$ have the same number of occurrences of non-zero digits. Furthermore, $cn = c_2c_1n=10^s c_2n_1$ also have the same number of occurrences of non-zero digits with $c_2n_1$.

This is a rephrasing of the above solution.
It is enough to solve the problem when $m,n$ are replaced by $km,kn$ for any positive integer $k$. In particular, by taking $k=2^a5^b$ for appropriate values of $a,b$, we may assume $n=10^sn_1$ where $n_1$ is relatively prime to 10.
Furthermore, adding or removing trailing zeros from $m$ and $n$ doesn't affect the claim, so we may further assume $\gcd(n,10)=1$ and that $m$ has a xillion trailing zeros (enough to make $m$ way bigger than $n$, and also so that $m$ has at least one trailing zero).
For clarity of exposition, we will also multiply $m,n$ by a small number to make the units digit of $n$ be $1$ (though this is not necessary for the solution to work).
The point is that, for any positive integer $X$, most nonzero digits appear the same number of times in $X$ and $X+999\dots999$ if there are enough $9$s; In particular, if the units digits of $X$ is $1$, then all nonzero digits appear the same number of times as long as there are at least as many $9$s as digits in $X$.
So we will pick $c$ to satisfy:
Because we made the units of $n$ to be $1$, the second condition is equivalent to making the units digit of $c$ to be $1$.
The first condition is equivalent to $(m-n)c=999\dots999$. Because $m$ has at least one trailing 0, the units digit of $m-n$ is 9, so $\gcd(m-n,10)=1$ and there is some $c$ so that $(m-n)c=999\dots999$, and the units digit of $c$ must be $1$ which agrees with the other condition.
Finally, as $m\gg n, (m-n)c\approx mc\gg nc$ so it is possible to make the number of $9$s more than the number of digits in $nc$.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Let $ABC$ be a triangle.  Find all points $P$ on segment $BC$ satisfying the following property:  If $X$ and $Y$ are the intersections of line $PA$ with the common external tangent lines of the circumcircles of triangles $PAB$ and $PAC$, then

Solution:
Let circle $PAB$ (i.e. the circumcircle of $PAB$), $PAC$ be $\omega_1, \omega_2$ with radii $r_1$, $r_2$ and centers $O_1, O_2$, respectively, and $d$ be the distance between their centers.
Lemma. $XY = \frac{r_1 + r_2}{d} \sqrt{d^2 - (r_1 - r_2)^2}.$
Proof. Let the external tangent containing $X$ meet $\omega_1$ at $X_1$ and $\omega_2$ at $X_2$, and let the external tangent containing $Y$ meet $\omega_1$ at $Y_1$ and $\omega_2$ at $Y_2$. Then clearly $X_1 Y_1$ and $X_2 Y_2$ are parallel (for they are both perpendicular $O_1 O_2$), and so $X_1 Y_1 Y_2 X_2$ is a trapezoid.
Now, $X_1 X^2 = XA \cdot XP = X_2 X^2$ by Power of a Point, and so $X$ is the midpoint of $X_1 X_2$. Similarly, $Y$ is the midpoint of $Y_1 Y_2$. Hence, $XY = \frac{1}{2} (X_1 Y_1 + X_2 Y_2).$ Let $X_1 Y_1$, $X_2 Y_2$ meet $O_1 O_2$ s at $Z_1, Z_2$, respectively. Then by similar triangles and the Pythagorean Theorem we deduce that $X_1 Z_1 = \frac{r_1 \sqrt{d^2 - (r_1 - r_2)^2}}{d}$ and $\frac{r_2 \sqrt{d^2 - (r_1 - r_2)^2}}{d}$. But it is clear that $Z_1$, $Z_2$ is the midpoint of $X_1 Y_1$, $X_2 Y_2$, respectively, so $XY = \frac{(r_1 + r_2)}{d} \sqrt{d^2 - (r_1 - r_2)^2},$ as desired.
Lemma 2. Triangles $O_1 A O_2$ and $BAC$ are similar.
Proof. $\angle{AO_1 O_2} = \frac{\angle{PO_1 A}}{2} = \angle{ABC}$ and similarly $\angle{AO_2 O_1} = \angle{ACB}$, so the triangles are similar by AA Similarity.
Also, let $O_1 O_2$ intersect $AP$ at $Z$. Then obviously $Z$ is the midpoint of $AP$ and $AZ$ is an altitude of triangle $A O_1 O_2$.Thus, we can simplify our expression of $XY$:

where $h_a$ is the length of the altitude from $A$ in triangle $ABC$. Hence, substituting into our condition and using $AB = c, BC = a, CA = b$ gives

Using $2 a h_a = 4[ABC] = \sqrt{(a + b + c)(a + b - c)(a - b + c)(-a + b + c)}$ by Heron's Formula (where $[ABC]$ is the area of triangle $ABC$, our condition becomes

which by $(a + b + c)(-a + b + c) = (b + c)^2 - a^2$ becomes

Let $PB = x$; then $PC = a - x$. The quadratic in $x$ is

which factors as

Hence, $PB = \frac{ab}{b+c}$ or $\frac{ac}{b+c}$, and so the $P$ corresponding to these lengths are our answer.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


Let $a,b,c,d$ be real numbers such that $b-d \ge 5$ and all zeros $x_1, x_2, x_3,$ and $x_4$ of the polynomial $P(x)=x^4+ax^3+bx^2+cx+d$ are real. Find the smallest value the product $(x_1^2+1)(x_2^2+1)(x_3^2+1)(x_4^2+1)$ can take.

Solution: Using the hint we turn the equation into $\prod_{k=1} ^4 (x_k-i)(x_k+i) \implies P(i)P(-i) \implies (b-d-1)^2 + (a-c)^2 \implies \boxed{16}$. This minimum is achieved when all the $x_i$ are equal to $1$.


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

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

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

Then:

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

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

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

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

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

which simplifies to:

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

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

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

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

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


Prove that there exists an infinite set of points  in the plane with the following property: For any three distinct integers $a,b,$ and $c$, points $P_a$, $P_b$, and $P_c$ are collinear if and only if $a+b+c=2014$.

Consider an elliptic curve with a generator $g$, such that $g$ is not a root of $0$. By repeatedly adding $g$ to itself under the standard group operation, with can build $g, 2g, 3g, \ldots$ as well as $-g, -2g, -3g, \ldots$. If we let  then we can observe that collinearity between $P_a$, $P_b$, and $P_c$ occurs only if $P_a + P_b + P_c = 0$ (by definition of the group operation), which is equivalent to $(3a-2014)g + (3b-2014)g + (3c-2014)g = (3a+3b+3c-3*2014)g = 0$, or $3a + 3b + 3c = 3*2014$, or $a + b + c = 2014$. We know that all these points $P_k$ exist because $3k-2014$ is never 0 for integer $k$, so that none of these points need to be point at infinity (the identity element of the group).

Consider letting $P_x$ be the point $(x, f(x))$, where $f(x) = x^3 - 2014x^2$. Then if three points $P_a, P_b, P_c$ are on the same line $y = mx + p$, they must be the solutions to the equation $x^3 - 2014x^2 = mx + p$ (i.e. the intersection of $f$ and the line). By Vieta's Formulas, the sum of the roots to this equation is 2014. Because each value of x corresponds to a different one of a, b, and c by definition of $P_x$, $a + b + c = 2014$. Conversely, if $a + b + c = 2014$, they must be the solutions to $(x-a)(x-b)(x-c) = x^3 - 2014x^2 - mx - p = 0$ for some real $m$ and $p$. Clearly, then, $P_a, P_b, P_c$ must all lie on the line $y = mx + p$. Hence, our setting $P_x = f(x)$ produces a valid infinite set of points.
Note: We could have let $f(x) = ax^3 - 2014ax^2 + bx + c$, where a, b, and c are arbitrary constants. (a is nonzero.)


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

Solution:
We claim that the minimum $k$ such that A cannot create a $k$ in a row is $\boxed{6}$.
It is easy to verify that player A can create a 5 in a row.
Let A place two counters anywhere, and B take off one of them. Then, A should create a "triangle of hexagons" by placing two adjacent counters also next to the unremoved one, so that no matter what B does there will be a line of two counters on adjacent hexagons.
Note: A diagram and more conciseness is required in the following solution. Better maneuvers are always appreciated.
Then, it is advisable for A to make a 4-in-a-row by placing 2 counters at the end of the line. B to prevent a 5-in-a-row must counter by removing a middle counter (a counter not on the edge of the 4-in-a-row). Player A then could reinstate the threat by placing a counter there and one adjacent to that hexagon (but not adjacent to the other middle counter). It is not in B's best interest to then remove the other middle counter, for then A can "add" a counter to both hexagons (adjacent to the removed counter) on the same side of the originally placed hexagon while preserving the threat. Now, we have two different threats B cannot both counter. Thus, assume B does not remove the other middle counter. Eventually, by "adding" counters and preserving the threat player A can create a web of hexagons surrounding the chosen middle counter. As we have proven, it will be disastrous for B to then remove the other middle counter; thus, B has to remove the chosen middle counter.
Now, player A can administer the decisive winning maneuver as follows. Let X be two adjacent counters of the web, one of which is adjacent to the initial edge counter. Let Y be the other two counters that satisfy the condition. The line X should not have more than two counters on it. Player A should place his two counters on the first two hexagons not adjacent to any counter in X (or the web), so that B is forced to remove the outermost counter A played. Then, A should place two counters adjacent to his remaining counter in a direction parallel to line Y. B has to expunge the outermost one; otherwise A can place two counters to complete a 5-in-a-row. Let A place two more counters in the same direction; then, B has to remove the middle counter played. Now, turn in a direction parallel to line X; let A place a counter on the first two spaces adjacent to counters already placed. B will remove the second counter played. A's knockout blow occurs when he reinstates the lost counter and a counter adjacent to that counter and the remaining one he played last turn, and it is easy to verify he is guaranteed a 5-in-a-row. Therefore, A can (after an elongated siege) obtain a 5-in-a-row.
To prove that 6-in-a-row is impossible, tile the hexagon board in an A-B-C-A-B-C-A-B-C format. Define an "A tile" to be a tile engraved with the letter A. To prevent player A from obtaining a 6 in a row, all player B has to do is to remove counters placed on A tiles by player A. Because no two A tiles are adjacent, player A can play at most one counter on an A tile at a time; thus, there can at most be one counter on A tiles any time of the game. Clearly, then, a 6 in a row, which requires A-B-C-A-B-C (or two counters on A tiles), is impossible, completing the proof.


Let $ABC$ be a triangle with orthocenter $H$ and let $P$ be the second intersection of the circumcircle of triangle $AHC$ with the internal bisector of the angle $\angle BAC$.  Let $X$ be the circumcenter of triangle $APB$ and $Y$ the orthocenter of triangle $APC$.  Prove that the length of segment $XY$ is equal to the circumradius of triangle $ABC$.

Let $O_1$ be the center of $(AHPC)$, $O$ be the center of $(ABC)$. Note that $(O_1)$ is the reflection of $(O)$ across $AC$, so $AO=AO_1$. Additionally

so $Y$ lies on $(O)$. Now since $XO,OO_1,XO_1$ are perpendicular to $AB,AC,$ and their bisector, $XOO_1$ is isosceles with $XO=OO_1$, and $\angle XOO_1=180-\angle A$. Also

But $YO=OA$ as well, and $\angle YOX=\angle AOO_1$, so $\triangle OYX\cong \triangle OAO_1$. Thus $XY=AO_1=AO$.

Since $AHPC$ is a cyclic quadrilateral, $\angle AHC = \angle APC$. $\angle AHC = 90^\circ + \angle ABC$ and $\angle APC = 90^\circ + \angle AYC$, we find $\angle ABC = \angle AYC$. That is, $ABYC$ is a cyclic quadrilateral. Let $D$ be mid-point of $\overline{AB}$. $O, X, D$ are collinear and $OX \perp AB$. Let $M$ be second intersection of $AP$ with circumcircle of the triangle $ABC$. Let $YP \cap AC = E$, $YM \cap AB = F$. Since $M$ is mid-point of the arc $BC$, $OM\perp BC$. Since $AYMC$ is a cyclic quadrilateral, $\angle CYM = \angle CAM = \angle BAC /2$. Since $Y$ is the orthocenter of triangle $APC$, $\angle PYC = \angle CAP = \angle BAC /2$. Thus, $\angle PYM = \angle BAC$ and $AEYF$ is a cyclic quadrilateral. So, $YF \perp AB$ and $OX \parallel MY$. We will prove that $XYMO$ is a parallelogram.
https://wiki-images.artofproblemsolving.com//7/7b/Usamo2014-5.png (figure link)
We see that $YPM$ is an isosceles triangle and $YM=YP$. Also $XB=XP$ and $\angle BXP = 2\angle BAP = \angle BAC = \angle PYM$. Then, $BXP \sim MYP$. By spiral similarity, $BPM \sim XPY$ and $\angle XYP = \angle BMP = \angle BCA$. Hence, $\angle XYP = \angle BCA$, $XY \perp BC$. Since $OM \perp BC$, we get $XYMO$ is a parallelogram. As a result, $OM = XY$.
(Lokman GÖKÇE)


Prove that there is a constant $c>0$ with the following property: If $a, b, n$ are positive integers such that $\gcd(a+i, b+j)>1$ for all $i, j\in\{0, 1, \ldots n\}$, then

Solution:
The following solution is due to Gabriel Dospinescu and v_Enhance (also known as Evan Chen).
Let $N = n+1$ and assume $N$ is (very) large. We construct an $N \times N$ with cells $(i,j)$ where $0 \le i, j \le n$ and in each cell place a prime $p$ dividing $\gcd (a+i, b+j)$.
The central claim is at least $50\%$ of the primes in this table exceed $0.001n^2$. We count the maximum number of squares they could occupy:
 Here the summation runs over primes $p \le 0.001n^2$.
Let $r = \pi(0.001n^2)$ denote the number of such primes. Now we apply the three bounds:  which follows by adding all the primes directly with some computation,  using the harmonic series bound, and  via Prime Number Theorem.  Hence the sum in question is certainly less than $\tfrac 12 N^2$ for $N$ large enough, establishing the central claim.
Hence some column $a+i$ has at least one half of its primes greater than $0.001n^2$. Because this is greater than $n$ for large $n$, these primes must all be distinct, so $a+i$ exceeds their product, which is larger than  where $c$ is some constant.


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:
$(3t)^2 - xy = (t+1)^3$
$9t^2 + x (x - 3t) = t^3 + 3t^2 + 3t + 1$
$4x^2 - 12xt + 9t^2 = 4t^3 - 15t^2 + 12t + 4$
$(2x - 3t)^2 = (t - 2)^2(4t + 1)$
$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:
$(2x - 3n^2 - 3n)^2 = [(n^2 + n - 2)(2n+1)]^2$
$2x - 3n^2 - 3n = \pm (2n^3 + 3n^2 -3n -2)$
$x = n^3 + 3n^2 - 1$ or $x = -n^3 + 3n + 1$
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)$

Let $n = \frac{x+y}{3}$.
Thus, $x+y = 3n$.
We have

Substituting $n$ for $\frac{x+y}{3}$, we have

Treating $x$ as a variable and $n$ as a constant, we have

which turns into

a quadratic equation.
By the quadratic formula,

which simplifies to

Since we want $x$ and $y$ to be integers, we need $4(n+1)^3 - 27n^2$ to be a perfect square.
We can factor the aforementioned equation to be
for an integer $k$.
Since $(n-2)^2$ is always a perfect square, for $(n-2)^2 (4n+1)$ to be a perfect square, $4n + 1$ has to be a perfect square as well.
Since $4n + 1$ is odd, the square root of the aforementioned equation must be odd as well.
Thus, we have $4n + 1 = a^2$ for some odd $a$.
Thus,  in which by difference of squares it is easy to see that all the possible values for $n$ are just $n = p(p-1)$, where $p$ is a positive integer.
Thus,
Thus, the general form for  for a positive integer $p$.
(This is an integer since $4(p(p-1)+1)^3 - 27(p(p-1))^2$ is an even perfect square (since $4(p(p-1)+1)$ is always even, as well as $27(p(p-1))^2$ being always even) as established, and $3p(p-1)$ is always even as well. Thus, the whole numerator is even, which makes the quantity of that divided by $2$ always an integer.)
Since $y = 3n - x$, the general form for $y$ is just

(This is an integer since $4(p(p-1)+1)^3 - 27(p(p-1))^2$ is an even perfect square (since $4(p(p-1)+1)$ is always even, as well as $27(p(p-1))^2$ being always even) as established, and $3p(p-1)$ is always even as well. Thus, the whole numerator is even, which makes the quantity of that divided by $2$ always an integer, which thus trivially makes  an integer.)
for a positive integer $p$.
Thus, our general in integers $(x, y)$ is
$\boxed{}$
-fidgetboss_4000


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$

To begin with, we connect $\overline{AT}$ and we construct the nine-point circle of $\triangle AST$ centered at $N_9$.
Lemma $1$: $AX \cdot AS = AP^2$.
We proceed on a directed angle chase. We get $\measuredangle ASP = \measuredangle AQP = \measuredangle QPA$, so $\triangle PAS \sim \triangle XAP$ and the desired result follows by side length ratios.
Lemma $2$: The locus of $N_9$ as $X$ moves along $\overline{PQ}$ is a circle centered about $A$.
We add the midpoint of $\overline{AS}$, $N$, and let the circumradius of $\triangle AST$ be $R$. Taking the power of $A$ with respect to $(N_9)$, we get
Hence, $AN_9 = \sqrt{\frac{1}{4}R^2 + \frac{1}{2}AP^2}$, which remains constant as $X$ moves.
Next, consider the homothety of scale factor $\frac{2}{3}$ about $O$ mapping $N_9$ to $G$. This means that the locus of $G$ is a circle as well.
Finally, we take a homothety of scale factor $\frac{3}{2}$ about $A$ mapping $G$ to $M$. Hence, the locus of $M$  is a circle, as desired. - Spacesam


Let $S = \{1, 2, ..., n\}$, where $n \ge 1$. Each of the $2^n$ subsets of $S$ is to be colored red or blue. (The subset itself is assigned a color and not its individual elements.) For any set $T \subseteq S$, we then write $f(T)$ for the number of subsets of T that are blue.
Determine the number of colorings that satisfy the following condition: for any subsets $T_1$ and $T_2$ of $S$,

Solution:
Define function: $C(T)=1$ if the set T is colored blue, and $C(T)=0$ if $T$ is colored red.
Define the $\text{Core} =\text{intersection of all } T \text{ where } C(T)=1$.
The empty set is denoted as $\varnothing$, $\cap$ denotes intersection, and $\cup$ denotes union. Let $S_n=\{n\}$ are one-element subsets.
Let $m_{c_k}=\dbinom{m}{k} = \frac{m!}{k!(m-k)!}$ denote m choose k.
(Case I) $f(\varnothing)=1$. Then for distinct m and k, $f(S_m \cup S_k)=f(S_m)f(S_k)$, meaning only if $S_m$ and $S_k$ are both blue is their union blue. Namely $C(S_m \cup S_k)=C(S_m)C(S_k).$
Similarly, for distinct $m,n,k$, $f(S_m \cup S_k \cup Sn)=f(S_m \cup S_k)f(S_n)$, $C(S_m \cup S_k \cup S_n)=C(S_m)C(S_k)C(S_n)$. This procedure of determination continues to $S$. Therefore, if $T=\{a_1,a_2, \cdots a_k\}$, then $C(T)=C(S_{a_1})C(S_{a_2}) \cdots C(S_{a_k})$. All colorings thus determined by the free colors chosen for subsets of one single elements satisfy the condition.  There are $2^n$ colorings in this case.
(Case II.)  $f(\varnothing)=0$.
(Case II.1)  $\text{Core}=\varnothing$. Then either (II.1.1) there exist two nonintersecting subsets A and B, $C(A)=C(B)=1$, but f$(A)f(B)=0$, a contradiction, or (II.1.2) all subsets has $C(T)=0$, which is easily confirmed to satisfy the condition $f(T_1)f(T_2)=f(T_1 \cap T_2)f(T_1 \cup T_2)$.  There is one coloring in this case.
(Case II.2) Core = a subset of 1 element. WLOG, $C(S_1)=1$. Then $f(S_1)=1$, and subsets containing element 1 may be colored blue. $f(S_1 \cup S_m)f(S_1\cup S_n)=f(S_1 \cup S_m \cup S_n)$, namely $C(S_1 \cup S_m \cup S_n)=C(S_m \cup S_1)C(S_n \cup S_1)$. Now S_1 functions as the $\varnothing$ in case I, with $n-1$ elements to combine into a base of $n-1$ two-element sets, and all the other subsets are determined. There are $2^{n-1}$ colorings for each choice of core. However, there are nC1 = n such cores. Hence altogether there are $n2^{n-1}$ colorings in this case.
(Case II.3) Core = a subset of 2 elements. WLOG, let $C(S_1 \cup S_2)=1$. Only subsets containing the core may be colored blue. With the same reasoning as in the preceding case, there are $(nC2)2^{n-2}$ colorings.
$\dots$
(Case II.n+1) Core = S. Then $C(S)=1$, with all other subsets $C(T)=0$, there is $1=\dbinom{n}{n}2^0$
Combining all the cases, we have $1+\left[2^n+\dbinom{n}{1}2^{n-1}+\dbinom{n}{2}2^{n-2}+ \cdots + \dbinom{n}{n}2^0\right]=\boxed{1+3^n}$ colorings. sponsored by ALLEN


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,j 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


Let $a, b, c, d, e$ be distinct positive integers such that $a^4 + b^4 = c^4 + d^4 = e^5$. Show that $ac + bd$ is a composite number.

Note:  This solution is definitely not what the folks at MAA intended, but it works!
Look at the statement $a^4+b^4=e^5$.  This can be viewed as a special case of Beal's Conjecture (http://en.wikipedia.org/wiki/Beal%27s_conjecture), stating that the equation $A^x+B^y=C^z$ has no solutions over positive integers for $gcd(a, b, c) = 1$ and $x, y, z > 2$. This special case was proven in 2009 by Michael Bennet, Jordan Ellenberg, and Nathan Ng, as $(x, y, z) = (2, 4, n)$.  This case $a^4+b^4=e^5$ is obviously contained under that special case, so $a$ and $b$ must have a common factor greater than $1$.
Call the greatest common factor of $a$ and $b$ $f$.  Then $a = f \cdot a_1$ for some $a_1$ and likewise $b = f \cdot b_1$ for some $b_1$.  Then consider the quantity $ac+bd$.
$ac+bd = f \cdot a_1 \cdot c + f \cdot b_1 \cdot d = f\cdot(a_1 \cdot c + b_1 \cdot d)$.
Because $c$ and $d$ are both positive, $(a_1 \cdot c + b_1 \cdot d) > 1$, and by definition $f > 1$, so $ac+bd$ is composite.
~BealsConjecture

A more conventional approach, using proof by contradiction:
Without loss of generality, assume $a>d$
Since $a^4 +b^4=c^4+d^4$, It is obvious that $b<c$
We construct the equation $(a^4 +b^4)c^2d^2-(c^4+d^4)a^2b^2=(a^2c^2-b^2d^2)(a^2d^2-b^2c^2)$ (the right side is the factorization of the left) Which factors into: $e^5(cd-ab)(cd+ab)=(ac-bd)(ac+bd)(ad-bc)(ad+bc)$ (by using $a^4 +b^4=c^4+d^4=e^5$ and factoring)
If $ac-bd$ or $ad-bc$ equal zero, then $a:b$ equals $c:d$ or $d:c$ respectively, which is impossible because $a^4 +b^4=c^4+d^4$ and because $a,b,c,d,e$ are distinct. Therefore the right side of the equation above is non-zero and the left side must be divisible by $ac+bd$
If $ac+bd$ were prime,
We have $ac+bd-(cd+ab)=(a-d)(c-b)>0$
Which means that  $ac+bd>cd+ab>cd-ab$ and neither $cd+ab$ nor $cd-ab$ can be multiples of $ac+bd$ meaning $e$ must be a multiple of $ac+bd$ and $e=k(ac+bd)$ for some integer $k$
But clearly this is impossible since $(k(ac+bd))^5>a^4+b^4$.
Therefore, by contradiction, $ac+bd$ is composite.


Consider $0<\lambda<1$, and let $A$ be a multiset of positive integers. Let $A_n=\{a\in A: a\leq n\}$. Assume that for every $n\in\mathbb{N}$, the set $A_n$ contains at most $n\lambda$numbers. Show that there are infinitely many $n\in\mathbb{N}$ for which the sum of the elements in $A_n$ is at most $\frac{n(n+1)}{2}\lambda$. (A multiset is a set-like collection of elements in which order is ignored, but repetition of elements is allowed and multiplicity of elements is significant. For example, multisets $\{1, 2, 3\}$ and $\{2, 1, 3\}$ are equivalent, but $\{1, 1, 2, 3\}$ and $\{1, 2, 3\}$ differ.)

Solution:
Proposed by mengmeng142857.
We prove this by contradiction. Suppose that the number of times that an integer $a$ appears in $A$ is $k_a$. Let the sum of the elements in $A_n$ be $S_n=\sum_{i=1}^{n}i\cdot k_i$. If there are only finitely many $n\in\mathbb{N}$ such that $S_n\leq\frac{n(n+1)}{2}\lambda$, then by the Well Ordering Principle, there must be a largest $m\in\mathbb{N}$ such that $S_m\leq\frac{m(m+1)}{2}\lambda$, and for all $n>m$, $S_n>\frac{n(n+1)}{2}\lambda$.
Now, observe that for some $n>m$,

Also,
$\frac{S_{n}}{n}>\frac{n+1}{2}\lambda$,
$\frac{S_{n-1}}{n(n-1)}>\frac{1}{2}\lambda$,
$\frac{S_{n-2}}{(n-1)(n-2)}>\frac{1}{2}\lambda$,
$\hdots$
$\frac{S_{m+1}}{(m+2)(m+1)}>\frac{1}{2}\lambda$,
$\frac{S_{m}}{(m+1)m}\leq \frac{1}{2}\lambda$.
Now, for any $n\in\mathbb{N}$, we let $\frac{S_n}{(n+1)n}-\frac{1}{2}\lambda=d_n$, then

Let $\sum_{i=1}^{m}d_i=-c$ (where $c$ is positive, otherwise we already have a contradiction), then

Dividing both sides by $n$, $\lambda-c/n<\frac{\sum_{i=1}^{n}k_i}{n}\leq \lambda$. Taking the limit yields
$\lim_{n\to\infty}{\frac{\sum_{i=1}^{n}k_i}{n}}=\lambda$.
Observe that this would imply that

However, as $k_n$ is an integer, it is impossible for it to converge to $\lambda$. This yields the desired contradiction.


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.


Prove that for any positive integer $k,$

is an integer.

Define $v_p(N)$ for all rational numbers $N$ and primes $p$, where if $N=\frac{x}{y}$, then $v_p(N)=v_p(x)-v_p(y)$, and $v_p(x)$ is the greatest power of $p$ that divides $x$ for integer $x$. Note that the expression(that we're trying to prove is an integer) is clearly rational, call it $N$.
$v_p(N)=\sum_{i=1}^\infty \left\lfloor \frac{k^{2}}{p^{i}} \right\rfloor+\sum_{j=0}^{k-1} \sum_{i=1}^\infty \left\lfloor \frac{j}{p^{i}}\right\rfloor-\sum_{j=k}^{2k-1} \sum_{i=1}^\infty \left\lfloor \frac{j}{p^{i}} \right\rfloor$, by Legendre. Clearly, $\left\lfloor{\frac{x}{p}}\right\rfloor={\frac{x-r(x,p)}{p}}$, and $\sum_{i=0}^{k-1} r(i,m)\leq \sum_{i=k}^{2k-1} r(i,m)$, where $r(i,m)$ is the remainder function(we take out groups of $m$ which are just permutations of numbers $1$ to $m$ until there are less than $m$ left, then we have $m$ distinct values, which the minimum sum is attained at $0$ to $k-1$). Thus, $v_p(N)=\sum_{m=p^{i}, i\in \mathbb{N}_{+}}-\frac{k^{2}}{m}+\left\lfloor{\frac{k^{2}}{m}}\right\rfloor-\frac{\sum_{i=0}^{k-1} r(i,m)-\sum_{i=k}^{2k-1} r(i,m)}{m} \geq \sum_{m=p^{i}, i\in \mathbb{N}} \left\lceil -\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor\right\rceil \geq 0$, as the term in each summand is a sum of floors also and is clearly an integer.

Consider an $k\times k$ grid, which is to be filled with the integers $1$ through $k^2$ such that the numbers in each row are in increasing order from left to right, and such that the numbers in each column are in increasing order from bottom to top. In other words, we are creating an $k\times k$ standard Young tableaux.
The Hook Length Formula is the source of the controversy, as it is very powerful and trivializes this problem. The Hook Length Formula states that the number of ways to create this standard Young tableaux (call this $N$ for convenience) is:

Now, we do some simple rearrangement:

This is exactly the expression given in the problem! Since the expression given in the problem equals the number of distinct $k\times k$ standard Young tableaux, it must be an integer, so we are done.

Define  Clearly, $A(1) = 1$ and $A(2) = 2.$
Then  Lots of terms cancel, and we are left with  The numerator has $2k+1$ consecutive positive integers, so one of them must be divisible by $(2k+1).$ Also, there are $2k$ terms left, $k$ of which are even. We can choose one of these to cancel out the $2$ in the denominator. Therefore, the ratio between $A(k+1)$ and $A(k)$ is an integer. By our inductive hypothesis, $A(k)$ is an integer. Therefore, $A(k+1)$ is as well, and we are done.


Let $\triangle ABC$ be an acute triangle, and let $I_B, I_C,$ and $O$ denote its $B$-excenter, $C$-excenter, and circumcenter, respectively. Points $E$ and $Y$ are selected on $\overline{AC}$ such that $\angle ABY = \angle CBY$ and $\overline{BE}\perp\overline{AC}.$ Similarly, points $F$ and $Z$ are selected on $\overline{AB}$ such that $\angle ACZ = \angle BCZ$ and $\overline{CF}\perp\overline{AB}.$
Lines $I_B F$ and $I_C E$ meet at $P.$ Prove that $\overline{PO}$ and $\overline{YZ}$ are perpendicular.

Solution:
This problem can be proved in the following two steps.
1. Let $I_A$ be the $A$-excenter, then $I_A,O,$ and $P$ are colinear. This can be proved by the Trigonometric Form of Ceva's Theorem for $\triangle I_AI_BI_C.$
2. Show that $I_AY^2-I_AZ^2=OY^2-OZ^2,$ which implies $\overline{OI_A}\perp\overline{YZ}.$ This can be proved by multiple applications of the Pythagorean Thm.

We find point $T$ on line $YZ,$ we prove that $TY \perp OI_A$ and state that $P$ is the point $X(24)$ from ENCYCLOPEDIA OF TRIANGLE, therefore $P \in OI_A.$
Let $\omega$ be circumcircle of $\triangle ABC$ centered at $O.$
Let $Y_1,$ and $Z_1$ be crosspoints of $\omega$ and $BY,$ and $CZ,$ respectively.
Let $T$ be crosspoint of $YZ$ and $Y_1 Z_1.$
In accordance the Pascal theorem for pentagon $AZ_1BCY_1,$ $AT$ is tangent to $\omega$ at $A.$
Let $I_A, I_B, I_C$ be $A, B,$ and $C$-excenters of $\triangle ABC.$
Denote

$V$ is the foot ot perpendicular from $O$ to $AI_A.$
$I$ is ortocenter of $\triangle I_A I_B I_C$ and incenter of $\triangle ABC.$
$\omega$ is the Nine–point circle of $\triangle I_A I_B I_C.$
$Y_1$ is the midpoint of $II_B, Z_1$ is the midpoint of $II_C$ in accordance with property of Nine–point circle $\implies$

In $\triangle ABC$ segment $YZ$ cross segment $AX \implies \frac {AU}{UX} = \frac {m + nk}{k+1},$ where $n = \frac {a}{b}, m = \frac{a}{c}, k=\frac {b}{c},$

Let $\triangle II_B I_C$ be the base triangle with orthocenter $I_A,$ center of Nine-points circle $O \implies OI_A$ be the Euler line of $\triangle II_B I_C.$
$\triangle ABC$ is orthic triangle of $\triangle II_B I_C,$
$\triangle DEF$ is orthic-of-orthic triangle.
$P$ is perspector of base triangle and orthic-of-orthic triangle.
Therefore $P$ is point $X(24)$ of ENCYCLOPEDIA OF TRIANGLE CENTERS which lies on Euler line of the base triangle.
[[1]]
Claim
Proof
vladimir.shelomovskii@gmail.com, vvsss


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.


An equilateral pentagon $AMNPQ$ is inscribed in triangle $ABC$ such that $M\in\overline{AB},$ $Q\in\overline{AC},$ and $N, P\in\overline{BC}.$ Let $S$ be the intersection of lines $MN$ and $PQ.$ Denote by $\ell$ the angle bisector of $\angle MSQ.$
Prove that $\overline{OI}$ is parallel to $\ell,$ where $O$ is the circumcenter of triangle $ABC,$ and $I$ is the incenter of triangle $ABC.$

Let  $D$ be the intersection of line $AI$ and the circumcircle of $\Delta ABC$ (other than $A$), then $OD\perp BC$. Let $R$ be the point such that $NPQR$ is a rhombus. It follows that $OD\perp QR$.
Since $AM=AQ$, $AI\perp MQ$, or $DI\perp MQ$. It follows that $\angle ODI=\angle RQM$.
Since $BO=OD$, $MA=AQ$, $\angle BOD=\angle MAQ$, it follows that $\Delta BOD\sim\Delta MAQ$, so $AQ/MQ=OD/BD$.
It is given that $AQ=NP=RQ$, and by basic properties of the incenter, $ID=BD$. Therefore, $RQ/MQ=OD/ID$, so $\Delta RQM\sim\Delta ODI$.
Since the rotation between the two triangles in 90 degrees, $OI\perp MR$. However, $l$ is parallel to the bisector of $MNR$, which is perpendicular to $MR$, so we are done.

Write $\angle{JKL} = K$ for all $J,K,L$ chosen as distinct vertices of triangle $ABC$. Define $a, b, c$ as sides opposite to angles $A, B$, and $C$, respectively. Place the triangle in the Euclidean plane with $A$ at the origin and $C$ on the positive x-axis. Assume without loss of generality that C is acute.
Consider the sides of the pentagon as vectors and note that
Define $\delta$ and $\gamma$ as the angles made between the positive x-axis and $\overrightarrow{MN}$ and $\overrightarrow{QP}$, respectively. Considering the x and y coordinates of the vectors in $(1)$, it follows that
Suppose $\sin C - \sin A = 0$. Then $A = C$, and the triangle is isosceles. In this case, it is clear by symmetry that $\overline{OI}$ is vertical. Further, since point $S$ exists, $\delta \neq \gamma$, so $\delta + \gamma = 180$ and $\overrightarrow{MN} + \overrightarrow{QP}$ must be vertical as well.
For the remainder of the proof, assume $\sin C \neq \sin A$. Note that  whenever $x, y \in \mathbb{R}$ and $\sin x \neq \sin y$. Note further that the slope of the line defined by the vector formed by summing vectors $(\cos x, \sin x)$ and $(\cos y, \sin y)$ is this expression. Since $\ell$ is parallel to $\overrightarrow{MN} + \overrightarrow{QP}$, the slope of $\ell$ can be formed by dividing expressions in $(2)$ and $(3)$ and inverting the sign:
Determine the coordinates of $I$ by drawing perpendiculars from $I$ to the sides and vertices of the triangle. By exploiting congruence between pairs of right triangles that share a vertex, one can partition $a,b,c$ into $p+q, p+r, q+r$ where $p,q,r$ are bases of these triangles that lie on the sides of triangle $ABC$. From here it is clear that $I = \left(\frac{b + c – a}{2} , \frac{b + c – a}{2}\tan(A / 2)\right)$.
To find the coordinates of $O$, note that $\angle{OJK} + \angle{OJL} = \angle{J}$ and that $\angle {OJK} = \angle{OKJ}$ in any acute triangle $JKL$. It easily follows that $\angle{OJK} = 90 – L$. Note also that the perpendicular from $O$ to $\overline{JK}$ bisects $\overline{JK}$. Hence,  if triangle $ABC$ is acute.
If triangle $JKL$ is obtuse at $\angle J$, then it can be similarly shown that $\angle{OKL} = \angle{OLK} = J – 90$ but that the remaining angles of this form are still $90-L$ and $90-K$. It easily follows that $(5)$ holds if $\angle A$ is obtuse. If $\angle B$ is obtuse then $\angle OAC = B – 90$ and the $y$ coordinate of $O$ is $-\frac{b}{2} \tan{B-90}$. From this, $(5)$ follows in this case as well.
We can conclude the slope of $\overline {OI}$ is  by the Law of Sines and rearrangement.
Setting $(6) = (4)$ is equivalent to
Since $\tan(A/2) = \frac{\sin A}{1 + \cos A}$, this equation is equivalent to
This equation is equivalent to  which is evident.

Let $A', B',$ and $C'$ be the arc midpoints of $BC, CA, AB,$ respectively. Let $E$ be crosspoint of $AI$ and $B'C'.$
Therefore $O$ is the circumcenter of triangle $A'B'C'.$
Points $A, I, E,$ and $A'$ are collinear.
$\angle A'EB' = \frac {\overset{\Large\frown} {AC'}+\overset{\Large\frown} {B'C} +\overset{\Large\frown} {CA'}}{2} = 90^\circ \implies AA' \perp B'C'$
$\implies I$ is orthocenter of $\triangle A'B'C' \implies$
$IO$ is the Euler line of $\triangle A'B'C'.$
Let $G$ be the centroid of $\triangle A'B'C' \implies G$ lies on line $IO$
$\implies \overline {OG} = \frac {\overline{OA'} + \overline{OB'} + \overline{OC'}}{3}$ is paraller to $\overline{OI}.$
$\overline{OB'} \perp \overline{AC} \implies \overline{OB'} \perp \overline{QA}.$
Similarly $\overline{OC'} \perp \overline{AM}, \overline{OA'} \perp \overline{NP},$ rotation from $\overline{OA'}$ to $\overline{NP}$, from $\overline{OB'}$ to $\overline{QA},$ and from $\overline{OC'}$ to $\overline{AM}$ is in clockwise direction, $|\overline{QA}|=| \overline{AM}| =|\overline{NP}|, |\overline{OA'}| = |\overline{OB'}| = |\overline{OC'}| \implies$
$\overline{QA} + \overline{AM} + \overline{NP} = \overline{QM} + \overline{NP}$ is perpendicular to $|\overline{OI}.$
$|\overline{MN}| = |\overline{QP}|$ therefore in accordance with Claim $\overline{MN} + \overline{QP}$ is parallel to $\overline{OI}.$
This sum is parallel to $\ell,$, so we are done.
Claim
Let $|\overline{BA}|= |\overline{CD}|, \overline{CB} + |\overline{BA} + |\overline{AD} = |\overline{CD}.$
Then $(\overline{BA} + \overline{CD}) \perp (\overline{CB} + \overline{AD}).$
Proof
$(\overline{BA} + \overline{CD}) \cdot (\overline{CB} + \overline{AD}) = (\overline{BA} + \overline{CD}) \cdot (\overline{CB} + \overline{CD} – \overline{CB} – \overline{BA}) = |\overline{CD}|^2 – |\overline{BA}|^2 = 0.$
vladimir.shelomovskii@gmail.com, vvsss


Integers $n$ and $k$ are given, with $n\ge k\ge 2.$ You play the following game against an evil wizard.
The wizard has $2n$ cards; for each $i = 1, ..., n,$ there are two cards labeled $i.$ Initially, the wizard places all cards face down in a row, in unknown order.
You may repeatedly make moves of the following form: you point to any $k$ of the cards. The wizard then turns those cards face up. If any two of the cards match, the game is over and you win. Otherwise, you must look away, while the wizard arbitrarily permutes the $k$ chosen cards and turns them back face-down. Then, it is your turn again.
We say this game is $\textit{winnable}$ if there exist some positive integer $m$ and some strategy that is guaranteed to win in at most $m$ moves, no matter how the wizard responds.
For which values of $n$ and $k$ is the game winnable?

We claim that the game is winnable if and only if $n>k$. Suppose after the first step, the cards $1$ to $n$ are shuffled around. Notice that we have $n$ cards that we don't know the position of (which are all cards from $1$ to $n$). Now, suppose we pick $p$ known cards. Note that the $p$ cards are all different(since the known cards are the cards from $1$ to $n$), and there is still a possibility that the other cards from the unknown cards complement and cause $1$ to $n$. Therefore, we are in the same state as before, and the game is unwinnable.
Now, suppose $n>k$. Denote the ith card counting from the left. We pick cards $1$ to $k$, keeping track of the set of values of the cards. Then, we pick cards $2$ to $k+1$, adding the value of the $k+1$th card into the set of value of cards. We keep doing this, until we pick cards $2n-k$ to $2n-1$, at which point we know the exact number on the $2n$th card. Now, we go back to $1$ through $k$, and repeat this process, until we reveal the $2n-1$th card(unless we win during the process). This process terminates only when there are less or equal to $k$ cards that we don't know the exact numbers on or if we somehow win, clearly, as otherwise we're still revealing new information by picking cards from $1$ through $k$. Note that we now know the exact values on $2n-k$ of the cards. By the Pigeonhole Principle, since $k<n$, $2$ of them are the same, and we pick those $2$ cards and $k-2$ other random cards and we win.
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 $n=a+b$. Since $gcd(a,b)=1$, we know $gcd(a,n)=1$. We can rewrite the condition as
Assume $a$ is odd. Since we need to prove an infinite number of pairs exist, it suffices to show that infinitely many pairs with $a$ odd exist.
Then we have
We know by Euler's theorem that $a^{\varphi(n)} \equiv 1 \mod{n}$, so if $2a-n=\varphi(n)$ we will have the required condition.
This means $a=\frac{n+\varphi(n)}{2}$. Let $n=2p$ where $p$ is a prime, $p\equiv 1\mod{4}$. Then $\varphi(n) = 2p*\left(1-\frac{1}{2}\right)\left(1-\frac{1}{p}\right) = p-1$, so
Note the condition that $p\equiv 1\mod{4}$ guarantees that $a$ is odd, since $3p-1 \equiv 2\mod{4}$
This makes $b = \frac{p+1}{2}$. Now we need to show that $a$ and $b$ are relatively prime. We see that

By the Euclidean Algorithm.
Therefore, for all primes $p \equiv 1\mod{4}$, the pair $\left(\frac{3p-1}{2},\frac{p+1}{2}\right)$ satisfies the criteria, so infinitely many such pairs exist.

Take $a=2n-1, b=2n+1, n\geq 2$. It is obvious (use the Euclidean Algorithm, if you like), that $\gcd(a,b)=1$, and that $a,b>1$.
Note that

So

Since $a+b=4n$, all such pairs work, and we are done.

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.

I claim that the ordered pair $(2^{n} - 1, 2^{n} + 1)$ satisfies the criteria for all $n \geq 2.$
Proof:
It is easy to see that the order modulo $2^{n+1}$ of $(2^{n} - 1)^k$ is $2,$ since $(2^{n} - 1)^2 = 2^{2n} - 2 \cdot 2^{n} + 1 \equiv 1 \mod 2^{n+1}.$, and we can assert and prove similarly for the order modulo $2^{n+1}$ of $(2^{n} + 1)^k.$ Thus, the remainders modulo $2^{n+1}$ that the sequences of powers of $2^{n} - 1$ and $2^{n} + 1$ generate are $1$ for even powers and $2^{n} - 1$ and $2^{n} + 1$ for odd powers, respectively. Since $2^{n} + 1$ and $2^{n} - 1$ are both odd for $n \geq 2,$  Since there are infinitely many powers of $2$ and since all ordered pairs $(2^n - 1, 2^n+1)$ contain relatively prime integers, we are done.
$\boxed{}$
-fidgetboss_4000


Let $ABC$ be a scalene triangle with circumcircle $\Omega$ and incenter $I.$ Ray $AI$ meets $BC$ at $D$ and $\Omega$ again at $M;$ the circle with diameter $DM$ cuts $\Omega$ again at $K.$ Lines $MK$ and $BC$ meet at $S,$ and $N$ is the midpoint of $IS.$ The circumcircles of $\triangle KID$ and $\triangle MAN$ intersect at points $L_1$ and $L.$ Prove that $\Omega$ passes through the midpoint of either $IL_1$ or $IL.$

Solution:
Let $X$ be the point on circle $\Omega$ opposite $M$. This means $\angle MAX = 90^\circ, BC \perp XM.$
$\angle XKM = \angle DKM = 90^\circ \implies$ the points $X, D,$ and $K$ are collinear.
Let $D' = BC \cap XM \implies DD' \perp XM \implies$
$S$ is the orthocenter of $\triangle DMX \implies$ the points $X, A,$ and $S$ are collinear.
Let $\omega$ be the circle centered at $S$ with radius $R = \sqrt {SK \cdot SM}.$
We denote $I_\omega$ inversion with respect to $\omega.$
Note that the circle $\Omega$ has diameter $MX$ and contain points $A, B, C,$ and $K.$
$I_\omega (K) = M \implies$ circle $\Omega \perp \omega \implies C = I_\omega (B), X = I_\omega (A).$
$I_\omega (K) = M \implies$ circle $KMD \perp \omega \implies D' = I_\omega (D) \in KMD \implies$
$\angle DD'M = 90^\circ \implies$  the points $X, D',$ and $M$ are collinear.
Let $F \in AM, MF = MI.$ It is well known that $MB = MI = MC \implies$
$\Theta = BICF$ is circle  centered at $M.$ $C = I_\omega (B) \implies \Theta \perp \omega.$
Let $I' =  I_\omega (I ) \implies I' \in \Theta \implies \angle II'M =  90^\circ.$
$I' =  I_\omega (I ), X =  I_\omega (A ) \implies AII'X$ is cyclic.
$\angle XI'I = \angle XAI =  90^\circ \implies$  the points $X, I' ,$ and $F$ are collinear.
$I'IDD'$ is cyclic $\implies \angle I'D'M = \angle I'D'C + 90^\circ =  \angle I'ID + 90^\circ,$
$\angle XFM = \angle I'FI = 90^\circ – \angle I'IF = 90^\circ – \angle I'ID  \implies$
$\angle XFM +  \angle I'D'M = 180^\circ \implies I'D'MF$ is cyclic.
Therefore point $F$ lies on  $I_\omega (IDK).$
$FA \perp SX, SI' \perp FX \implies I$ is orthocenter of $\triangle FSX.$
$N$ is midpoint $SI, M$ is midpoint $FI, I$ is orthocenter of $\triangle FSX, A$ is root of height $FA \implies AMN$ is the nine-point circle of $\triangle FSX \implies I' \in AMN.$
Let $N' = I_\omega (N) \implies R^2 = SN \cdot SN' = SI \cdot  SI' \implies$

$\angle XN'I' = \angle XSI' = 90^\circ – \angle AXI' = \angle IFX \implies N'XIF$ is cyclic.
Therefore point $F$ lies on  $I_\omega (AMN) \implies I_\omega(F) = L \implies$
The points $F, L,$ and $S$ are collinear, $AXFL$ is cyclic.
Point $I$ is orthocenter $\triangle FSX \implies XI \perp SF, \angle ILS = \angle SI'F = 90^\circ$
$\implies$ The points $X, I, E,$ and $L$ are collinear.
$AXFL$ is circle $\implies AI \cdot IF = IL \cdot XI\implies$
$AI \cdot \frac {IF}{2} = \frac {IL}{2} \cdot IX \implies AI \cdot IM = EI \cdot IX \implies AEMX$ is cyclic.

vladimir.shelomovskii@gmail.com, vvsss


Let $\mathbf{Z}$ denote the set of all integers. Find all real numbers $c > 0$ such that there exists a labeling of the lattice points $( x, y ) \in \mathbf{Z}^2$ with positive integers for which: only finitely many distinct labels occur, and for each label $i$, the distance between any two points labeled $i$ is at least $c^i$.

See page 11 of this PDF:
https://web.evanchen.cc/exams/USAMO-2017-notes.pdf

For $c\le 1,$ we can label every lattice point $1.$ For $c\le \sqrt[4]{2},$ we can make a "checkerboard" labeling, i.e. label $(x, y)$ with $1$ if $x+y$ is even and $2$ if $x+y$ is odd. One can easily verify that these labelings satisfy the required conditions. Therefore, a labeling as desired exists for all $0 < c\le \sqrt[4]{2}.$
An iterated version of the checkerboard labeling can actually work for all values $c < \sqrt{2}.$ For convenience, define the original lattice grid to be the set of all lattice points in the coordinate plane. Define a modified lattice grid of size $x$ to be a structure similar to the lattice points on the coordinate plane, but with the minimum separation between any two points equaling $x$ (as opposed to $1$).
On the first step, assign a label $1$ to half of the points in a checkerboard arrangement. One can see that the points that have not yet been labeled form a modified lattice grid of size $\sqrt{2}$ (this lattice grid is also rotated by $45^{\circ}$ from the original lattice grid). At this point, for the second step, assign a label $2$ to half of the points, again in a checkerboard arrangement. At this point, the points that have not yet been labeled form a modified lattice grid of size $2$ (and again, it is rotated $45^{\circ}$ from the modified lattice grid after the first step). One then continues in this fashion. For the $N^{\text{th}}$ step, the points we are labeling are separated by at least $\sqrt{2}\times\left(\sqrt{2}\right)^{N-1} = \left(\sqrt{2}\right)^N > c^N,$ so we know that our labeling at each step is acceptable.
After the $N^{\text{th}}$ step (where $N$ is a natural number), the points that have not yet been labeled form a modified lattice grid with size $\left(\sqrt{2}\right)^N.$ Since $c < \sqrt{2},$ we will eventually have $\left(\sqrt{2}\right)^N > c^{N+1}$ for some sufficiently large $N.$ At this point, we can label all remaining points in the original lattice grid $N+1,$ and this produces a labeling of all of the lattice points in the plane that satisfies all of the conditions. Therefore, a labeling as desired exists for all $c < \sqrt{2}.$
We now prove that no labeling as desired exists for any $c\ge 2.$ To do this, we will prove that labeling a $2^k$-by-$2^k$ square grid of lattice points requires at least $k+3$ distinct labels for all natural numbers $k$; hence for a sufficiently large section of the lattice plane the number of distinct labels required grows arbitrarily large, so the entire lattice plane cannot be labeled with finitely many distinct labels. We will prove this using induction.
For the base case, $k=1,$ we have four points in a square of side length $1.$ The maximum distance between any two of these points is $\sqrt{2} < c^1$ for all $c\ge 2,$ so all four points must have different labels. This completes the base case.
Now, for the inductive step, suppose that labeling a $2^k$-by-$2^k$ square grid of lattice points requires at least $k+3$ distinct labels for some natural number $k.$ We will now prove that labeling a $2^{k+1}$-by-$2^{k+1}$ square grid of lattice points requires at least $k+4$ distinct labels.
Take a $2^{k+1}$-by-$2^{k+1}$ square grid of lattice points. Divide this grid into four quadrants, $A, B, C,$ and $D.$ By the inductive hypothesis, $A$ requires at least $k+3$ distinct labels. At least one of these labels must be $k+3$ or greater; take one such label and call it $L.$
The largest distance between any two points in the entire grid is $\sqrt{2}\left(2^{k+1} - 1\right) < c^{k+3}$ for all $c\ge 2.$ Therefore, the label $L$ cannot be used anywhere else in the grid. However, $B, C,$ and $D$ each require at least $k+3$ distinct labels as well by the inductive hypothesis. Thus, they must use at least one label that is not used in $A.$ It follows that the entire grid requires at least $k+4$ distinct labels. This completes the inductive step, and thus we conclude that no labeling as desired exists for any $c\ge 2.$
I have heard from others that the actual boundary is $\sqrt{2}.$ This makes intuitive sense, since the iterated checkerboard labeling outlined above just breaks down at this value (you will be able to get closer and closer to labeling all of the lattice points, but you can never get there, since you will never have $\left(\sqrt{2}\right)^N > c^{N+1}$). The inductive argument above seems fairly loose, so I think that it can be sharpened to bring the upper bound down to $\sqrt{2},$ but I am not sure yet how exactly to do so. I think the way to do it is to somehow force $2$ new labels (instead of just $1$) each time you double the side length of the square grid.

We claim that for all $c<\sqrt{2}$, there exists such a configuration.
Lemma 1a: If there exists a configuration for $c=c_1$, then for any $c_2\le{c_1}$, there also exists a configuration for $c=c_2$.
Note that any labeling that can be done for $c=c_1$ exists for $c=c_2$. Thus, we may copy the configuration from $c=c_1$ to $c=c_2$.
Lemma 1b: If there does not exist a configuration for $c=c_1$, then for any $c_2\ge{c_1}$, there does not exist a configuration for $c=c_2$.
Note that any labeling which may be done for $c=c_2$ should also be available for $c=c_1$. However, we already stated that $c=c_1$ has no configuration, and so $c=c_2$ doesn't either.
We now prove that $c=\sqrt{2}$ does not work. WLOG, label the origin of our lattice plan with label $1$. WLOG, we can cover every point that we can with label $1$ because not labeling any such possible point does not affect the distance between points that aren't allowed to be labelled.
Name the state of the lattice grid before using label $1$ state $S$. After covering every point possible, we are left with only lattice points that have coordinates that sum to an odd integer. Notice, however, that if we discard the covered points and rotate all the new points by $\frac{\pi}{4}$ radians counterclockwise, we end up with the same grid as state $S$, only all the distances are multiplied by scalar $\sqrt{2}$. However, before placing label $2$s, note that we are in the same state $S$ as before, because our minimum distance is also multiplied by scalar $\sqrt{2}$. Thus, we will always be in an infinite loop, stuck in state $S$, and thus it is impossible to complete the labeling.
It suffices to show that any $c=2^{k}$ works given $k<0.5$. Note that the two smallest distances between any two points in the starting grid are $1$ and $\sqrt{2}$. When we are currently in state $S$ using label $I$, it is obvious that if $2ki-i\le{1}$, we can break out of state $S$ (Our effective minimum length would be at most 1, and we can cover every remaining point). Because $k<0.5$, there does exist an $I$ where this occurs. Thus, any $c<\sqrt{2}$ works, hence proved. $\blacksquare{}$ ~SigmaPiE


Find the minimum possible value of

given that $a,b,c,d,$ are nonnegative real numbers such that $a+b+c+d=4$.

Solution:
See here: https://artofproblemsolving.com/community/c5t211539f5h1434574_looks_like_mount_inequality_erupted_
or:
https://www.youtube.com/watch?v=LSYP_KMbBNc


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

Solution:
WLOG let $a \leq b \leq c$. Add $2(ab+bc+ca)$ to both sides of the inequality and factor to get:
The last inequality is true by AM-GM. Since all these steps are reversible, the proof is complete.

Similarly to Solution 2, we will prove homogeneity but we will use that to solve the problem differently. Let $f(a,b,c)=a+b+c-4\sqrt[3]{abc}$. Note that $f(a,b,c)=f(ka,kb,kc)$, thus proving homogeneity.
WLOG, we can scale down all variables such that the lowest one is $1$. WLOG, let this be $a=1$.
We now have $1+b+c=4\sqrt[3]{bc}$, and we want to prove $2bc+2b+2c+4\ge 1+b^2+c^2.$ Adding $2bc$ to both sides and subtracting $2b+2c$ gives us $4bc+4\ge 1+ (b+c)(b+c-2)$, or $4bc+3\ge (b+c)(b+c-2)$. Let $\sqrt[3]{bc}=x$. Now, we have     By the trivial inequality, this is always true. Since all these steps are reversible, the proof is complete.
~SigmaPiE


Find all functions $f:(0,\infty) \to (0,\infty)$ such that
for all $x,y,z >0$ with $xyz =1.$

Solution:
Obviously, the output of $f$ lies in the interval $(0,1)$. Define $g:(0,1)\to(0,1)$ as $g(x)=f\left(\frac1x-1\right)$. Then for any $a,b,c\in(0,1)$ such that $a+b+c=1$, we have $g(a)=f\left(\frac1a-1\right)=f\left(\frac{1-a}a\right)=f\left(\frac{b+c}a\right)$. We can transform $g(b)$ and $g(c)$ similarly:

Let $x=\frac ca$, $y=\frac ab$, $z=\frac bc$. We can see that the above expression is equal to $1$. That is, for any $a,b,c\in(0,1)$ such that $a+b+c=1$, $g(a)+g(b)+g(c)=1$.
(To motivate this, one can start by writing $x=\frac ab$, $y=\frac bc$, $z=\frac ca$, and normalizing such that $a+b+c=1$.)
For convenience, we define $h:\left(-\frac13,\frac23\right)\to\left(-\frac13,\frac23\right)$ as $h(x)=g\left(x+\frac13\right)-\frac13$, so that for any $a,b,c\in\left(-\frac13,\frac23\right)$ such that $a+b+c=0$, we have

Obviously, $h(0)=0$. If $|a|<\frac13$, then $h(a)+h(-a)+h(0)=0$ and thus $h(-a)=-h(a)$. Furthermore, if $a,b$ are in the domain and $|a+b|<\frac13$, then $h(a)+h(b)+h(-(a+b))=0$ and thus $h(a+b)=h(a)+h(b)$.
At this point, we should realize that $h$ should be of the form $h(x)=kx$. We first prove this for some rational numbers. If $n$ is a positive integer and $x$ is a real number such that $|nx|<\frac13$, then we can repeatedly apply $h(a+b)=h(a)+h(b)$ to obtain $h(nx)=nh(x)$. Let $k=6h\left(\frac16\right)$, then for any rational number $r=\frac pq\in\left(0,\frac13\right)$ where $p,q$ are positive integers, we have $h(r)=6p*h\left(\frac1{6q}\right)=\frac{6p}q*h\left(\frac16\right)=kr$.
Next, we prove it for all real numbers in the interval $\left(0,\frac13\right)$. For the sake of contradiction, assume that there is some $x\in\left(0,\frac13\right)$ such that $h(x)\ne kx$. Let $E=h(x)-kx$, then obviously $0<|E|<1$. The idea is to "amplify" this error until it becomes so big as to contradict the bounds on the output of $h$. Let $N=\left\lceil\frac1{|E|}\right\rceil$, so that $N\ge2$ and $|NE|\ge1$. Pick any rational $r\in\left(\frac{N-1}Nx,x\right)$, so that
All numbers and sums are safely inside the bounds of $\left(-\frac13,\frac13\right)$. Thus

but picking any rational number $s\in\left(N(x-r),\frac13\right)$ gives us $|kN(x-r)|<|ks|$, and since $ks=h(s)\in\left(-\frac13,\frac23\right)$, we have $kN(x-r)\in\left(-\frac13,\frac23\right)$ as well, but since $NE\ge1$, this means that $h(N(x-r))=kN(x-r)+NE\notin\left(-\frac13,\frac23\right)$, giving us the desired contradiction.
We now know that $h(x)=kx$ for all $0<x<\frac13$. Since $h(-x)=-h(x)$ for $|x|<\frac13$, we obtain $h(x)=kx$ for all $|x|<\frac13$. For $x\in\left(\frac13,\frac23\right)$, we have $h(x)+h\left(-\frac x2\right)+h\left(-\frac x2\right)=0$, and thus $h(x)=kx$ as well. So $h(x)=kx$ for all $x$ in the domain. Since $h(x)$ is bounded by $-\frac13$ and $\frac23$, we have $-\frac12\le k\le1$. It remains to work backwards to find $f(x)$.
- wzs26843545602


For a given integer $n\ge 2,$ let $\{a_1,a_2,…,a_m\}$ be the set of positive integers less than $n$ that are relatively prime to $n.$ Prove that if every prime that divides $m$ also divides $n,$ then $a_1^k+a_2^k + \dots + a_m^k$ is divisible by $m$ for every positive integer $k.$

https://maa.org/sites/default/files/pdf/AMC/usamo/2018/2018USAMO.pdf
The integer m in the statement of the problem is ϕ(n), where ϕ is the Euler totient function.
Throughout our proof we write p
s
|| m, if s is the greatest power of p that divides m.
We begin with the following lemma:
Lemma 1. If p is a prime and p
s divides n for some positive integer s, then 1k + 2k + · · · + n
k
is
divisible by p
s−1
for any integer k ≥ 1.
2018 USAMO – Solutions 4
Proof. Let {a1, a2, . . . , am} be a complete reduced residue set modulo p
s and m = p
s−1
(p − 1).
First we prove by induction on s that for any positive integer k, a
k
1 + a
k
2 + · · · + a
k
m is divisible by
p
s−1
. The base case s = 1 is true. Suppose the statement holds for some value of s. Consider the
statement for s + 1. Note that
{a1, . . . , am, ps + a1, . . . , ps + am, . . . , ps
(p − 1) + a1, . . . , ps
(p − 1) + am}
is a complete reduced residue set modulo p
s+1. Therefore, the desired sum of k-th powers is equal
to
a
k
1 + · · · + a
k
m + · · · + (p
s
(p − 1) + a1)
k + · · · + (p
s
(p − 1) + am)
k ≡ p(a
k
1 + · · · + a
k
m) ≡ 0 (mod p
s
),
where we have used the induction hypothesis for the second congruence. This gives the induction
step.
Now we are ready to prove the lemma. Because numbers from 1 to n can be split into blocks of
consecutive numbers of length p
s
, it is enough to show that 1k + 2k +· · · + (p
s
)
k
is divisible by p
s−1
for any positive integer k. We use induction on s. The statement is true for s = 1. Assume the
statement is true for s − 1. The sum
1
k + 2k + · · · + (p
s
)
k = a
k
1 + a
k
2 + · · · + a
k
m + p
k
�
1
k + 2k + · · · + (p
s−1
)
k
�
is divisible by p
s−1
, because p
s−1
| a
k
1 + · · · + a
k
m and by the induction hypothesis p
s−2
| 1
k + · · · +
(p
s−1
)
k
.
Now we proceed to prove a second lemma, from which the statement of the problem will immediately
follow:
Lemma 2. Suppose p is a prime dividing n. Let {a1, . . . , am} be a complete reduced residue set
mod n, and define s by p
s
|| m. Then p
s divides a
k
1 + · · · + a
k
m for any integer k ≥ 1.
Proof. We fix p, and use induction on the number of prime factors of n (counted by multiplicity)
that are different from p. If there are no prime factors other than p, then n = p
s+1
, m = p
s
(p − 1),
and we proved in Lemma 1 that a
k
1 +· · ·+a
k
m is divisible by p
s
. Now suppose the statement is true
for n. We show that it is true for nq, where q is a prime not equal to p.
Case 1. q divides n. We have p
s
|| ϕ(n) and p
s
|| ϕ(nq), because ϕ(nq) = qϕ(n). If {a1, a2, . . . , am}
is a complete reduced residue set modulo n, then
{a1, . . . , am, n + a1, . . . , n + am, . . . , n(q − 1) + a1, . . . , n(q − 1) + am}
is a complete reduced residue set modulo nq. The new sum of k-th powers is equal to
a
k
1 + · · · + a
k
m + · · · + (n(q − 1) + a1)
k + · · · + (n(q − 1) + am)
k = mnk
�
1
k + · · · + (q − 1)k
�
+
2018 USAMO – Solutions 5
�
k
1
�
n
k−1
�
1
k−1 + · · · + (q − 1)k−1
�
(a1 + · · · + am) + · · · + q(a
k
1 + · · · + a
k
m).
This sum is divisible by p
s because p
s
|| m and p
s
| a
j
1 + a
j
2 + · · · + a
j
m for any positive integer j.
Case 2. q doesn’t divide n. Suppose p
b
|| q − 1, where b ≥ 0. Note that ϕ(nq) = ϕ(n)(q − 1), so
p
s
|| ϕ(n) and p
s+b
|| ϕ(nq). Let {a1, . . . , am} be a complete reduced residue set modulo n. The
complete reduced residue set modulo nq consists of the mq numbers
{a1, . . . , am, n + a1, . . . , n + am, . . . , n(q − 1) + a1, . . . , n(q − 1) + am}
with the m elements {qa1, qa2, . . . , qam} removed.
The new sum of k-th powers is equal to
a
k
1 + · · · + a
k
m + · · · + (n(q − 1) + a1)
k + · · · + (n(q − 1) + am)
k − q
k
(a
k
1 + · · · + a
k
m) =
mnk
�
1
k + · · · + (q − 1)k
�
+
�
k
1
�
n
k−1
�
1
k−1 + · · · + (q − 1)k−1
�
(a1 + · · · + am) + · · ·
· · · +
�
k
k − 1
�
n (1 + · · · + (q − 1)) (a
k−1
1 + · · · + a
k−1
m ) + q(a
k
1 + · · · + a
k
m) − q
k
(a
k
1 + · · · + a
k
m).
Each term
�
k
j
�
n
k−j
�
1
k−j + · · · + (q − 1)k−j
�
(a
j
1 + · · · + a
j
m),
for 0 ≤ j ≤ k − 1, is divisible by p
s+b because p | n
k−j
, p
s
| a
j
1 + · · · + a
j
m, and p
b−1
| 1
k−j + · · · +
(q − 1)k−j by Lemma 1.
Also (q
k − q)(a
k
1 + · · · + a
k
m) is divisible by p
s+b because p
b
| q − 1 | q
k − q and p
s
| a
k
1 + · · · + a
k
m.
Thus p
s+b divides our sum and our proof is complete.
Remark. In fact, one can also show the converse statement: if {a1, a2, . . . , am} is as defined in
the problem and a
k
1 + a
k
2 + · · · + a
k
m is divisible by m for every positive integer k, then every prime
that divides m also divides n.
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.
$\textbf{Note: This is the same problem as 2018 USAJMO Problem 5.}$

We consider the Lemma and it's proof as in the above solution.
For every $k$, let $x_k$ be the number of distinct residues that $a_i + ik$ takes on. Further for each residue $r_i$, let $n_i$ be the number of times it is achieved by an $a_j + jk$ for $i \in [1, x_k]$. Note that $\sum_{i = 1}^{x_k} n_i = p.$
The number of pairs $(a_i, a_j)$ s.t $(a_i + ik) - (a_j + jk) \equiv 0$ for a given $k$ is,

The first equality is given by a well known theorem, which can be proven by C-S or Jensen's.
Summing over all $k$, the number of times a pair $(a_i, a_j)$ has $(a_i + ik) - (a_j + jk) \equiv 0$ is,

Alternatively, every pair $(a_i, a_j)$ has a unique $k$ s.t $(a_i + ik) - (a_j + jk) \equiv 0$ by the Lemma so we double-count as,

By AM-HM inequality,

So it is clear that $\exists k$ s.t $x_k \ge \frac{p}{2}$.
~Aaryabhatta1


In convex cyclic quadrilateral $ABCD,$ we know that lines $AC$ and $BD$ intersect at $E,$ lines $AB$ and $CD$ intersect at $F,$ and lines $BC$ and $DA$ intersect at $G.$ Suppose that the circumcircle of $\triangle ABE$ intersects line $CB$ at $B$ and $P$, and the circumcircle of $\triangle ADE$ intersects line $CD$ at $D$ and $Q$, where $C,B,P,G$ and $C,Q,D,F$ are collinear in that order. Prove that if lines $FP$ and $GQ$ intersect at $M$, then $\angle MAC = 90^{\circ}.$

Solution:
so $P,E,Q$ are collinear. Furthermore, note that $DQBP$ is cyclic because:

Notice that since $A$ is the intersection of $(EDQ)$ and $(BPE)$, it is the Miquel point of $DQBP$.
Now define $X$ as the intersection of $BQ$ and $DP$. From Pappus's theorem on $BFPDGQ$ that $A,M,X$ are collinear. It’s a well known property of Miquel points that $\angle EAX = 90$, so it follows that $MA \perp AE$, as desired. $\blacksquare$
~AopsUser101


Let $a_n$ be the number of permutations $(x_1, x_2, \dots, x_n)$ of the numbers $(1,2,\dots, n)$ such that the $n$ ratios $\frac{x_k}{k}$ for $1\le k\le n$ are all distinct. Prove that $a_n$ is odd for all $n\ge 1.$

Solution:
Write out the mapping of each $k$ to $x_k$ as follows:
Now, consider what happens when the two rows are swapped (and the top-bottom pairs are reordered so that the top reads (1,2,3,...,n)).  This will result in a new permutation if and only if $x_k = j$ does not imply $x_j = k$ for all $k,j$ in $(1,2,3,\dots,n)$.  I will denote this new permutation as $(y_1,y_2,y_3,\dots,y_n)$.  Notice that $(y_1,y_2,y_3,\dots,y_n)$ is a valid permutation if and only if $(x_1,x_2,x_3,\dots,x_n)$ is valid, because each fraction $\frac{y_k}{k}$ is the reciprocal of $\frac{x_k}{k}$.  This means that we need only consider the parity of number of cases in which $(y_1,y_2,y_3,\dots, y_n) = (x_1,x_2,x_3,\dots, x_n)$, as there will be an even number of cases where $(y_1,y_2,y_3,\dots, y_n) \ne (x_1,x_2,x_3,\dots, x_n)$.  Let the number of valid permutations where $(y_1,y_2,y_3,\dots, y_n) = (x_1,x_2,x_3,\dots, x_n)$ be $b_n$.
Notice that the only permutations that have the property $x_{x_k}=k$ (which is an equivalent statement to the one given above) are those that are formed by taking pairs of elements and swapping their positions having the maximum number of pairs possible and having no two pairs both contain the same element.  Some more necessary conditions will be outlined below after we split $n$ into two cases.
Case 1:  $n$ is odd.  If $n$ is odd then there must be exactly one $k$ such that $x_k = k$.  This yields $b_n=n\cdot b_{n-1}$* which has the same parity as $b_{n-1}$, so we need only consider the parity of $b_n$ for odd $n$. (*Note: This is wrong, as $b_n$ is only the number of valid involutions for $1,2,...,n$, not $1,2,...,n+1$ with one number removed.)
Case 2:  $n$ is even.  If $n$ is even then can be no $k$ so that $x_k=k$, or else there must be at least two distinct numbers $k$ and $j$ so that $x_k=k$ and $x_j=j$ which violates the given conditions.  Denote a pair of numbers that are swapped to arrive at the final permutation as the pair $(a,b)$.  Then if a permutation yields an invalid arrangement there must be two pairs $(a,b)$ and $(c,d)$ such that $\frac{a^2}{b^2} = \frac{c^2}{d^2}$.  But notice that the two pairs $(a,c)$ and $(b,d)$ will also result in an invalid arrangement. So, there must be an even number of invalid arrangements (Note: This proof doesn't work, as no specific pairing of invalid arrangements is constructed. Indeed, when three pairs all with the same fraction are present, this doesn't work.), meaning the parity we desire is just the number of ways to separate $n$ objects into $\frac n2$ pairs!  However, this is quite simply just $(n-1)(n-3)(n-5)\cdots(3)(1)$, which is clearly the product of odd numbers.  So we conclude that there are an odd number of valid permutations $(x_1,x_2,x_3,\dots,x_n)$.  $\blacksquare$


Let $\mathbb{N}$ be the set of positive integers. A function $f:\mathbb{N}\to\mathbb{N}$ satisfies the equation for all positive integers $n$. Given this information, determine all possible values of $f(1000)$.

Solution:
Let $f^r(x)$ denote the result when $f$ is applied to $f^{r-1}(x)$, where $f^1(x)=f(x)$.
$\hfill \break \hfill \break$
If $f(p)=f(q)$, then $f^2(p)=f^2(q)$ and $f^{f(p)}(p)=f^{f(q)}(q)$
$\implies p^2=f^2(p)\cdot f^{f(p)}(p)=f^2(q)\cdot f^{f(q)}(q)=q^2$
$\implies p=\pm q$
$\implies p=q$ since $p,q>0$.
Therefore, $f$ is injective. It follows that $f^r$ is also injective.
Lemma 1: If $f^r(b)=a$ and $f(a)=a$, then $b=a$.
Proof:
$f^r(b)=a=f^r(a)$ which implies $b=a$ by injectivity of $f^r$.
Lemma 2: If $f^2(m)=f^{f(m)}(m)=m$, and $m$ is odd, then $f(m)=m$.
Proof:
Let $f(m)=k$. Since $f^2(m)=m$, $f(k)=m$. So, $f^2(k)=k$. $\newline f^2(k)\cdot f^{f(k)}(k)=k^2$.
Since $k\neq0$, $f^{f(k)}(k)=k$
$\implies f^m(k)=k$
$\implies f^{gcd(m, 2)}(k)=k$
$\implies f(k)=k$
This proves Lemma 2.
I claim that $f(m)=m$ for all odd $m$.
Otherwise, let $m$ be the least counterexample.
Since $f^2(m)\cdot f^{f(m)}(m)=m^2$, either
$(1) f^2(m)=k<m$, contradicted by Lemma 1 since $k$ is odd and $f^2(k)=k$.
$(2) f^{f(m)}(m)=k<m$, also contradicted by Lemma 1 by similar logic.
$(3) f^2(m)=m$ and $f^{f(m)}(m)=m$, which implies that $f(m)=m$ by Lemma 2.
This proves the claim.
By injectivity, $f(1000)$ is not odd.
I will prove that $f(1000)$ can be any even number, $x$. Let $f(1000)=x, f(x)=1000$, and $f(k)=k$ for all other $k$. If $n$ is equal to neither $1000$ nor $x$, then $f^2(n)\cdot f^{f(n)}(n)=n\cdot n=n^2$. This satisfies the given property.
If $n$ is equal to $1000$ or $x$, then $f^2(n)\cdot f^{f(n)}(n)=n\cdot n=n^2$ since $f(n)$ is even and $f^2(n)=n$. This satisfies the given property.

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}$.

Solution:
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:
(1) $AP' \cdot AB = AD^2$
(2) $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. $\square$
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. $\square$

Let $\omega$ be the circle centered at $A$ with radius $AD.$
Let $\Omega$ be the circle centered at $B$ with radius $BC.$
We denote $I_\omega$ and $I_\Omega$ inversion with respect to $\omega$ and $\Omega,$ respectively.

Let $\theta$ be the circle $ABCD.$
$I_\omega (\theta) = B'C'D,$ straight line, therefore
$I_\Omega (\theta) = A'D'C,$ straight line, therefore

$ABCD$ is cyclic $\implies \angle BA'C = \angle AB'D.$
 points $A'$ and $B'$ are coincide.
Denote $A' = B' = Q \in AB.$
Suppose, we move point $Q$ from $A$ to $B.$ Then $\angle AQD$ decreases monotonically, $\angle BQC$ increases monotonically. So, there is only one point where
$\hspace{19mm} I_\omega (CD'P) = AC'D'B$ is cyclic.

$\hspace{19mm} C'D'CD$ is  trapezoid.
It is known that the intersection of the diagonals, intersection point of the lines containing the lateral sides of the trapezoid and the midpoints of two parallel sides are collinear.
vladimir.shelomovskii@gmail.com, vvsss