(Titu Andreescu) Prove that for each positive integer $n$, there are pairwise relatively prime integers $k_0, k_1 \dotsc, k_n$, all strictly greater than 1, such that $k_0 k_1 \dotsm k_n -1$ is the product of two consecutive integers.

We will prove the problem for each nonnegative integer $n$.  We wish to show that

for some integer $a$.  We induct on $n$.  For our base case, $n=0$, we may let $a$ be positive integer.
For the inductive step, suppose that $k_0, \dotsc, k_{n-1}$ are pairwise relatively prime integers such that

for some integer $a$.  Let $k_n = a^2 + 3a+3$.  Evidently, $k_n >1$.  Also,

Since $a^2+a+1 = a(a+1)+1$ is odd and relatively prime to $a+1$, it follows that $a^2+a+1$ and $k_n$ are relatively prime, so $k_n$ is relatively prime to each of $k_0, \dotsc, k_{n-1}$.  Finally,

This completes the induction.

Lemma.  If $p$ is prime such that $p\equiv 1 \pmod{3}$, there exists a residue $r$ such that $p \mid r^2+r+1$.
Proof. Let $g$ be a multiplicative generator of the nonzero integers mod p.  Set $r \equiv g^{(p-1)/3}$.  Then $r-1 \not\equiv 0 \pmod{p}$, but $r^3-1 \equiv 0 \pmod{p}$, so $\frac{r^3-1}{r-1} \equiv r^2 + r+1 \equiv 0 \pmod{p}$.
End Lemma
By Dirichlet's Theorem, there are infinitely many primes congruent to 1 (mod 3).  Let $p_0, \dotsc, p_n$ be $(n+1)$ such primes, and let $r_0, \dotsc, r_n$ be respective residues as described in the lemma.  By the Chinese Remainder Theorem, there is a positive integer $a$ that satisfies the relation

for each integer $i \in [0,n]$.  Then

Now, for $1 \le i \le n$, take $k_i$ to be the greatest power of $p_i$ that divides $a^2 + a +1$, and let $k_0 = (a^2+a+1)/(k_1 \dotsm k_n)$.  Since all the $k_i$ are pairwise relatively prime and are greater than 1, we are done.

Firstly, we see that there are $n + 1$ numbers $k_i$. Since $n\geq1$, there are at least 2 values of $k_i$.
Define a relatively prime partition to be a set of relatively prime numbers such that their product is equal to some natural number.
Define $P$ to be the greatest possible cardinality of a relatively prime partition for that number.
Lemma 1. All cardinalities of the relatively prime partitions of a number up to $P$ can be attained.
Proof. $P = P - 0$ satisfies the properties. For any $P - n$ which satisfies the properties, we can take any of the 2 $P - n$ numbers and multiply them together. Because they are both relatively prime to all the other numbers, their product is relatively prime to all the other numbers as well, and that results in $P - n - 1$ numbers which satisfy the conditions, unless $P - n = 1$, because there is only one number left. Therefore, all numbers of numbers of relatively prime factors from $1$ to $P - 1$ are attainable, if $P$ is attainable as well.
End Lemma
Lemma 2. $a^2 + a + 1$ can have arbitrarily many prime factors for some value of $a$.
Proof. Let $f(x) = x^2 + x + 1$. Let $a^2 + a + 1 = k$. Then $f(a + k) = a^2 + 2ak + k^2 + a + k + 1 = 2ak + k^2 + 2k$.
After factoring, we get $k(k + 2 + 2a) = (a^2 + a + 1)(a^2 + 3a + 3)$.
$a^2 + 3a + 3 \geq a^2 + a + 1$, because $a$ is strictly positive.
Let their GCD=g.
$g|2a + 2$
$g|2a^2 + 2a$
$g|a^2 - 3a - 3 + a^2 + 3a + 3, g|2a^2$
$g|2a$, and so $g|2$, but $g|a^2 + a + 3$ which is strictly odd, so g=1.
$(a^2 + a + 1)(a^2 + 3a + 3)$ therefore must contain prime factors not in $a^2 + a + 1$. Upon repeating this an arbitrary number of times, we get a number of the form $a^2 + a + 1$ which has arbitrarily many distinct prime factors.
End Lemma
Then $a(a + 1) + 1 = a^2 + a + 1$ would not have $n + 1 = P$ elements in the relatively prime partition for some value of n, and any value of a.
It is possible to choose a value of $a$ such that $a^2 + a + 1$ has arbitrarily many unique prime factors, by our second Lemma, and so it is possible for $P$ to be arbitrarily high. By our first Lemma, all numbers up to P are possible values for the cardinality of some relatively prime partition, and so there always exists some number that has an arbitrary number of elements in a relatively prime partition. Because $a^2 + a + 1 = a(a + 1) + 1$, $a(a + 1)$ is the product of 2 consecutive integers, we see that the given statement is true because if $k_0k_1...k_n = a(a + 1) + 1$, then $k_0k_1...k_n - 1 = a(a + 1)$.

Write the relation to be proved as

There are infinitely many primes for which $-3$ is a quadratic residue. Let $2 < p_0 < p_1 < \cdots < p_n$ be such primes. Using the Chinese Remainder Theorem to specify $a$ modulo $p_n$, we can find an integer $a$ such that $(2a + 1)^2 + 3 = 4p_0p_1\cdots p_nm$ for some positive integer $m$. Grouping the factors of $m$ appropriately with the $p_i$'s, we obtain $(2a + 1)^2 + 3 = 4k_0k_1\cdots k_n$ with $k_i$ pairwise relatively prime. We then have $k_0k_1\cdots k_n - 1 = a(a + 1)$, as desired.

We are supposed to show that for every positive integer $n$, there is a positive integer $x$ such that $x(x + 1) + 1 = x^2 + x + 1$ has at least $n$ distinct prime divisors. We can actually prove a more general statement.
Claim. Let $P(x) = a_dx^d + \cdots + a_1x + 1$ be a polynomial of degree $d\geq 1$ with integer coefficients. Then for every positive integer $n$, there is a positive integer $x$ such that $P(x)$ has at least $n$ distinct prime divisors.
The proof follows from the following two lemmas.
Lemma 1. The set

is infinite.
Proof. The proof is analogous to Euclid's proof that there are infinitely many primes. Namely, if we assume that there are only finitely many primes $p_1, p_2, \ldots, p_k$ in $Q$, then for each integer $m$, $P(mp_1p_2\cdots p_k)$ is an integer with no prime factors, which must equal $1$ or $-1$. However, since $P$ has degree $d\geq 1$, it takes each of the values $1$ and $-1$ at most $d$ times, a contradiction.
End Lemma
Lemma 2. Let $p_1, p_2, \ldots, p_n$, $n\geq 1$ be primes in $Q$. Then there is a positive integer $x$ such that $P(x)$ is divisible by $p_1p_2\cdots p_n$.
Proof. For $i = 1, 2, \ldots, n$, since $p_i\in Q$ we can find an integer $c_i$ such that $P(x)$ is divisible by $p_i$ whenever $x\equiv c_i\pmod{p_i}$. By the Chinese Remainder Theorem, the system of $n$ congruences $x\equiv c_i\pmod{p_i}$, $i = 1, 2, \ldots, n$ has positive integer solutions. For every positive integer $x$ that solves this system, $P(x)$ is divisible by $p_1p_2\cdots p_n$.
End Lemma

Very similar to some above solutions.
Let $k_{0}k_{1}\dots k_{n}-1=a(a+1)$. We wish to show this equation has a solution $(a,k_{0},\dots,k_{n})\in\mathbb{Z}^{n+2}$ for any $n\in\mathbb{N}$. If $a^{2}+a+1$ has at least $n+1$ distinct prime factors, we can set $a^{2}+a+1=p_{1}^{q_{1}}p_{2}^{q_{2}}\dots p_{m}^{q_{m}}$ for some $m\geq n$ where $p_{1},\dots p_{m}$ are distinct primes. Then, we let $k_{i}=p_{i+1}^{q_{i+1}}$ for all $0\leq i\leq n-1$ and set $k_{n}=p_{n+1}^{q_{n+1}}\dots p_{m}^{q_{m}}$. Thus, it remains to show $a^{2}+a+1$ can have at least $n+1$ distinct prime factors. We will do this by showing it can have arbitrarily many.
Using an induction-type argument (it isn't exactly induction though), we first show that $a^{2}+a+1$ can have $1$ prime factor by setting $a=2$. Now, assume $a^{2}+a+1$ has $n$ distinct prime factors. We wish to show there exists some $b$ such that $b^{2}+b+1$ has more than $n$ distinct prime factors (we need not show it has $n+1$, since we only wish to demonstrate that the number of prime factors can be arbitrarily large rather than any integer). Set $b=a^{2}$. Then

Suppose $p$ is a positive integer dividing both $a^{2}+a+1$ and $a^{2}-a+1$. Then $p\mid(a^{2}+a+1)-(a^{2}-a+1)=2a$, and because $(a^{2}+a+1)$ is always odd, we have $2\nmid p$ so $p\mid a$. But this yields $p\mid\gcd(a,a^{2}+a+1)=1$, so $p=1$ and thus $a^{2}+a+1$ and $a^{2}-a+1$ are coprime. Therefore, as one can make $a^{2}-a+1>1$, we see that $a^{2}-a+1$ has at least one prime factor which does not divide $a^{2}+a+1$ (which has $n$ distinct prime factors). Therefore, $b^{2}+b+1$ has more than $n$ distinct prime factors.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


(Zuming Feng) Let $ABC$ be an acute, scalene triangle, and let $M$, $N$, and $P$ be the midpoints of $\overline{BC}$, $\overline{CA}$, and $\overline{AB}$, respectively. Let the perpendicular bisectors of $\overline{AB}$ and $\overline{AC}$ intersect ray $AM$ in points $D$ and $E$ respectively, and let lines $BD$ and $CE$ intersect in point $F$, inside of triangle $ABC$. Prove that points $A$, $N$, $F$, and $P$ all lie on one circle.

Without Loss of Generality, assume $AB >AC$. It is sufficient to prove that $\angle OFA = 90^{\circ}$, as this would immediately prove that $A,P,O,F,N$ are concyclic.
By applying the Menelaus' Theorem in the Triangle $\triangle BFC$ for the transversal $E,M,D$, we have (in magnitude)

Here, we used that $BM=MC$, as $M$ is the midpoint of $BC$. Now, since $EC =EA$ and $BD=DA$, we have

Now, note that $OE$ bisects the exterior $\angle FED$ and $OD$ bisects exterior $\angle FDE$, making $O$ the $F$-excentre of $\triangle FED$. This implies that $OF$ bisects interior $\angle EFD$, making $OF \perp AF$, as was required.

Let $A=1,B=b,C=c$ where $b,c$ all lie on the unit circle. Then $O$ is 0. As noted earlier, $(FOBC)$ is cyclic. We will find the ghost point $F',$ the second intersection of $OBC$ and $ANP$.
We know that these two circles already intersect at $O$ so we can reflect over the line between their centers. The center of $ANPO$ is the midpoint of $AO$ namely $\frac12$. With the tangent formula and then taking the midpoint, we find that the center of $OBC$ is $\frac{bc}{b+c}.$ Then we want to find the reflection of 0 over the line through $\frac12$ and $\frac{bc}{b+c}.$ Then we get

Now it remains to show $\angle F'BA=\angle ABM;$ the other angle equality would follow by symmetry.
Then we get:

Thus $\measuredangle F'BA=\measuredangle BAM,$ so $F'=F$ and we're done.
~cocohearts

Without loss of generality $AB < AC$. The intersection of $NE$ and $PD$ is $O$, the circumcenter of $\triangle ABC$.
Let $\angle BAM = y$ and $\angle CAM = z$. Note $D$ lies on the perpendicular bisector of $AB$, so $AD = BD$. So $\angle FBC = \angle B - \angle ABD = B - y$. Similarly, $\angle FCB = C - z$, so $\angle BFC = 180 - (B + C) + (y + z) = 2A$. Notice that $\angle BOC$ intercepts the minor arc $BC$ in the circumcircle of $\triangle ABC$, which is double $\angle A$. Hence $\angle BFC = \angle BOC$, so $BFOC$ is cyclic.
Lemma. $\triangle FEO$ is directly similar to $\triangle NEM$
Proof.

since $F$, $E$, $C$ are collinear, $BFOC$ is cyclic, and $OB = OC$. Also

because $NE\perp AC$, and $MNP$ is the medial triangle of $\triangle ABC$ so $AB \parallel MN$. Hence $\angle OFE = \angle ENM$.
Notice that $\angle AEN = 90 - z = \angle CEN$ since $NE\perp AC$. $\angle FED = \angle MEC = 2z$. Then

Hence $\angle FEO = \angle NEM$.
Hence $\triangle FEO$ is similar to $\triangle NEM$ by AA similarity. It is easy to see that they are oriented such that they are directly similar.
End Lemma
By the similarity in the Lemma, $FE: EO = NE: EM\implies FE: EN = OE: EM$. $\angle FEN = \angle OEM$ so $\triangle FEN\sim\triangle OEM$ by SAS similarity. Hence

Using essentially the same angle chasing, we can show that $\triangle PDM$ is directly similar to $\triangle FDO$. It follows that $\triangle PDF$ is directly similar to $\triangle MDO$. So

Hence $\angle OPF = \angle ONF$, so $FONP$ is cyclic. In other words, $F$ lies on the circumcircle of $\triangle PON$. Note that $\angle ONA = \angle OPA = 90$, so $APON$ is cyclic. In other words, $A$ lies on the circumcircle of $\triangle PON$. $A$, $P$, $N$, $O$, and $F$ all lie on the circumcircle of $\triangle PON$. Hence $A$, $P$, $F$, and $N$ lie on a circle, as desired.

This solution utilizes the phantom point method. Clearly, APON are cyclic because $\angle OPA = \angle ONA = 90$. Let the circumcircles of triangles $APN$ and $BOC$ intersect at $F'$ and $O$.
Lemma. If $A,B,C$ are points on circle $\omega$ with center $O$, and the tangents to $\omega$ at $B,C$ intersect at $Q$, then $AP$ is the symmedian from $A$ to $BC$.
Proof. This is fairly easy to prove (as H, O are isogonal conjugates, plus using SAS similarity), but the author lacks time to write it up fully, and will do so soon.
End Lemma
It is easy to see $Q$ (the intersection of ray $OM$ and the circumcircle of $\triangle BOC$) is colinear with $A$ and $F'$, and because line $OM$ is the diameter of that circle, $\angle QBO = \angle QCO = 90$, so $Q$ is the point $Q$ in the lemma; hence, we may apply the lemma. From here, it is simple angle-chasing to show that $F'$ satisfies the original construction for $F$, showing $F=F'$; we are done.

By the Law of Sines, $\frac {\sin\angle BAM}{\sin\angle CAM} = \frac {\sin B}{\sin C} = \frac bc = \frac {b/AF}{c/AF} = \frac {\sin\angle AFC\cdot\sin\angle ABF}{\sin\angle ACF\cdot\sin\angle AFB}$. Since $\angle ABF = \angle ABD = \angle BAD = \angle BAM$ and similarly $\angle ACF = \angle CAM$, we cancel to get $\sin\angle AFC = \sin\angle AFB$. Obviously, $\angle AFB + \angle AFC > 180^\circ$ so $\angle AFC = \angle AFB$.
Then $\angle FAB + \angle ABF = 180^\circ - \angle AFB = 180^\circ - \angle AFC = \angle FAC + \angle ACF$ and $\angle ABF + \angle ACF = \angle A = \angle FAB + \angle FAC$. Subtracting these two equations, $\angle FAB - \angle FCA = \angle FCA - \angle FAB$ so $\angle BAF = \angle ACF$. Therefore, $\triangle ABF\sim\triangle CAF$ (by AA similarity), so a spiral similarity centered at $F$ takes $B$ to $A$ and $A$ to $C$. Therefore, it takes the midpoint of $\overline{BA}$ to the midpoint of $\overline{AC}$, or $P$ to $N$. So $\angle APF = \angle CNF = 180^\circ - \angle ANF$ and $APFN$ is cyclic.

Construct $T$ on $AM$ such that $\angle BCT = \angle ACF$. Then $\angle BCT = \angle CAM$. Then $\triangle AMC\sim\triangle CMT$, so $\frac {AM}{CM} = \frac {CM}{TM}$, or $\frac {AM}{BM} = \frac {BM}{TM}$. Then $\triangle AMB\sim\triangle BMT$, so $\angle CBT = \angle BAM = \angle FBA$. Then we have
$\angle CBT = \angle ABF$ and $\angle BCT = \angle ACF$. So $T$ and $F$ are isogonally conjugate. Thus $\angle BAF = \angle CAM$. Then
$\angle AFB = 180 - \angle ABF - \angle BAF = 180 - \angle BAM - \angle CAM = 180 - \angle BAC$.
If $O$ is the circumcenter of $\triangle ABC$ then $\angle BFC = 2\angle BAC = \angle BOC$ so $BFOC$ is cyclic. Then $\angle BFO = 180 - \angle BOC = 180 - (90 - \angle BAC) = 90 + \angle BAC$.
Then $\angle AFO = 360 - \angle AFB - \angle BFO = 360 - (180 - \angle BAC) - (90 + \angle BAC) = 90$. Then $\triangle AFO$ is a right triangle.
Now by the homothety centered at $A$ with ratio $\frac {1}{2}$, $B$ is taken to $P$ and $C$ is taken to $N$. Thus $O$ is taken to the circumcenter of $\triangle APN$ and is the midpoint of $AO$, which is also the circumcenter of $\triangle AFO$, so $A,P,N,F,O$ all lie on a circle.

Median $AM$ of a triangle $ABC$ implies $\frac {\sin{BAM}}{\sin{CAM}} = \frac {\sin{B}}{\sin{C}}$.
Trig ceva for $F$ shows that $AF$ is a symmedian.
Then $FP$ is a median, use the lemma again to show that $AFP = C$, and similarly $AFN = B$, so you're done.

Invert the figure about a circle centered at $A$, and let $X'$ denote the image of the point $X$ under this inversion. Find point $F_1'$ so that $AB'F_1'C'$ is a parallelogram and let $Z'$ denote the center of this parallelogram. Note that $\triangle BAC\sim\triangle C'AB'$ and $\triangle BAD\sim\triangle D'AB'$. Because $M$ is the midpoint of $BC$ and $Z'$ is the midpoint of $B'C'$, we also have $\triangle BAM\sim\triangle C'AZ'$. Thus

Hence quadrilateral $AB'D'F_1'$ is cyclic and, by a similar argument, quadrilateral $AC'E'F_1'$ is also cyclic. Because the images under the inversion of lines $BDF$ and $CFE$ are circles that intersect in $A$ and $F'$, it follows that $F_1' = F'$.
Next note that $B'$, $Z'$, and $C'$ are collinear and are the images of $P'$, $F'$, and $N'$, respectively, under a homothety centered at $A$ and with ratio $1/2$. It follows that $P'$, $F'$, and $N'$ are collinear, and then that the points $A$, $P$, $F$, and $N$ lie on a circle.

Let $O$ be the circumcenter of triangle $ABC$. We prove that

It will then follow that $A, P, O, F, N$ lie on the circle with diameter $\overline{AO}$. Indeed, the fact that the first two angles in $(1)$ are right is immediate because $\overline{OP}$ and $\overline{ON}$ are the perpendicular bisectors of $\overline{AB}$ and $\overline{AC}$, respectively. Thus we need only prove that $\angle AFO = 90^\circ$.
We may assume, without loss of generality, that $AB > AC$. This leads to configurations similar to the ones shown above. The proof can be adapted to other configurations. Because $\overline{PO}$ is the perpendicular bisector of $\overline{AB}$, it follows that triangle $ADB$ is an isosceles triangle with $AD = BD$. Likewise, triangle $AEC$ is isosceles with $AE = CE$. Let $x = \angle ABD = \angle BAD$ and $y = \angle CAE = \angle ACE$, so $x + y = \angle BAC$.
Applying the Law of Sines to triangles $ABM$ and $ACM$ gives

Taking the quotient of the two equations and noting that $\sin\angle BMA = \sin\angle CMA$, we find

Because $BM = MC$, we have

Applying the Law of Sines to triangles $ABF$ and $ACF$, we find

Taking the quotient of the two equations yields

so by $(2)$,

Because $\angle ADF$ is an exterior angle to triangle $ADB$, we have $\angle EDF = 2x$. Similarly, $\angle DEF = 2y$. Hence

Thus $\angle BFC = 2\angle BAC = \angle BOC$, so $BOFC$ is cyclic. In addition,

and hence, from $(3)$, $\angle AFB = \angle AFC = 180^\circ - \angle BAC$. Because $BOFC$ is cyclic and $\triangle BOC$ is isosceles with vertex angle $\angle BOC = 2\angle BAC$, we have $\angle OFB = \angle OCB = 90^\circ - \angle BAC$. Therefore,

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


(Gabriel Carroll) Let $n$ be a positive integer. Denote by $S_n$ the set of points $(x, y)$ with integer coordinates such that

A path is a sequence of distinct points $(x_1 , y_1 ), (x_2 , y_2 ), \ldots , (x_\ell, y_\ell)$ in $S_n$ such that, for $i = 2, \ldots , \ell$, the distance between $(x_i , y_i )$ and $(x_{i - 1} , y_{i - 1} )$ is $1$ (in other words, the points $(x_i , y_i )$ and $(x_{i - 1} , y_{i - 1} )$ are neighbors in the lattice of points with integer coordinates). Prove that the points in $S_n$ cannot be partitioned into fewer than $n$ paths (a partition of $S_n$ into $m$ paths is a set $\mathcal{P}$ of $m$ nonempty paths such that each point in $S_n$ appears in exactly one of the $m$ paths in $\mathcal{P}$).

Color all the points in $S_{n}$ red or black such that each row of points starts and ends with a red point, and alternates between red and black for each point in the row. This creates a checkerboard pattern, except that the middle two rows are identical.
Suppose there is a partition of $m < n$ paths that works. For each of the $m$ paths, we break a path into two separate paths wherever there are consecutive red points. This only happens only with the $n$ red pairs in the middle two rows. We now have $m + l,\, l \le n$ paths whose colors are strictly alternating. In a path with alternating colors, there can be at most one more red dot than the number of black dots (which occurs when both endpoints are red). Thus there can be no more than $m + l$ red dots than black dots in $S_n$.
There are $2n$ more red points than black points, so

which implies that $n \le m$, contradiction.

Suppose you have a partition of less than $n$ paths. Then start from $(0,n - 1)$ and work your way down to $(0, - n)$ along the right edge of $S_n$ performing the following algorithm when going from each point.
If a path already has the point you're coming from and the point you're going to as adjacent in the path, do nothing.
If not the first case, and the point you're coming from and the point you're going to are both endpoints of paths, join them (one less path).
If not the first case, and there is exactly one endpoint among the point you're coming from and the point you're going to, remove a segment from the one in the middle of a path (paths +1) and now you have two endpoints; join them (paths -1). If the point in the middle of the path is the one you're coming from, remove the segment that doesn't come from the point that came before it. The number of paths remains the same.
If not the first case, and both points are in the middle of a path, which is impossible. Since the two points are in the middle of the path, they are adjacent to two other points. But they are also adjacent to each other, so both are adjacent to at least three points. Then, no two points adjacent to at least three others are travelled consecutively.
Thus, given any configuration we can create the path shown above without increasing the number of paths. The remaining points form $S_{n - 1}$. Now suppose for some positive integer $n$, we have a partition into less than $n$ paths. Apply the algorithm to make the path shown above. Then the remaining points are partitioned into less than $n - 1$ paths. Apply the algorithm again. Repeat until we show that $S_1$ is partitioned into less than $1$ path, contradiction.

We induct on $n$ to prove that an $n - 1$-path partition is impossible. This can be restated as saying that we cannot fit $2n^2 - n + 1$ edges into the graph with each vertex having degree at most 2. The base case is trivial (2 edges when there only is 1). Suppose it was possible for $n + 1$, and we'll prove it's possible for $n$.
Call the 'complete' network (graph) of points $G_{n + 1}$ and the $n$-path partition for $n + 1$ is a subgraph of $G_{n + 1}$, $H_{n + 1}$. There are a total of $2(n + 1)^2 - n = 2n^2 + 3n + 2$ edges in $H_{n + 1}$ out of $4n^2 + 4n + 1$ in $G_{n + 1}$ (not hard to prove), and each vertex has maximum order 2. Now consider the complement of $H_{n + 1}$ in $G_{n + 1}$, that is, take all the edges in $G_{n + 1}$ that are not in $H_{n + 1}$ and of course all the vertices. Call this $F_{n + 1}$ We will trim $F_{n + 1}$ down a bit to get $H_n$.
First, call the points in $S_{n + 1}$ but not $S_n$ exterior points, and the points in $S_n$ interior points. $F_{n + 1}$ has $2n^2 + n - 1$ edges. Since the interior points have degree 4 in $G_{n + 1}$, they have degree at least 2 in $F_{n + 1}$, for a total degree of $4n^2 + m$ where $0\le m\le 2n - 2$ since the total overall degree is $2(2n^2 + n - 1) = 4n^2 + 2n - 2$. This makes the total degree of the exterior points $2n - 2 - m$. Since the exterior points are not connected in $G_{n + 1}$, these $2n - 2 - m$ edges must connect on exterior point to an interior point.
I then take away $2n - 2$ edges and the exterior points, yielding $2n^2 - n + 1$ edges and the interior points, which is $H_n$, as follows: First take away those $2n - 2 - m$ interior-exterior edges and shave off all the exterior points. Then the total degree (now just of the interior points) must be $4n^2 - 2n + 2 + 2m$.
Let the number of 0-degree vertices be $a$, 1-degree vertices be $b$, 2-degree vertices be $c$, 3-degree vertices be $d$, and 4-degree vertices be $e$. Since all the vertices began as 2-degree or higher, $2a + b\le2n - 2 - m$. Moreover, the total degree is $b + 2c + 3d + 4e = 2(2n^2) + (d + 2e) - (b + 2a) = 4n^2 - 2n + 2 + 2m$. So $d + 2e = b + 2a - (2n - 2 + 2m)\le (2n - 2 - m) - (2n - 2 - 2m) = m$ So we can use our last $m$ edges to remove any excess degree on vertices with degree 3 or 4, yielding $H_n$.

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


(Gregory Galparin) Let $\mathcal{P}$ be a convex polygon with $n$ sides, $n\ge3$. Any set of $n - 3$ diagonals of $\mathcal{P}$ that do not intersect in the interior of the polygon determine a triangulation of $\mathcal{P}$ into $n - 2$ triangles. If $\mathcal{P}$ is regular and there is a triangulation of $\mathcal{P}$ consisting of only isosceles triangles, find all the possible values of $n$.

Solution:
We label the vertices of $\mathcal{P}$ as $P_0, P_1, P_2, \ldots, P_n$. Consider a diagonal $d = \overline{P_a\,P_{a+k}},\,k \le n/2$ in the triangulation. We show that $k$ must have the form $2^{m}$ for some nonnegative integer $m$.
This diagonal partitions $\mathcal{P}$ into two regions $\mathcal{Q},\, \mathcal{R}$, and is the side of an isosceles triangle in both regions. Without loss of generality suppose the area of $Q$ is less than the area of $R$ (so the center of $P$ does not lie in the interior of $Q$); it follows that the lengths of the edges and diagonals in $Q$ are all smaller than $d$. Thus $d$ must the be the base of the isosceles triangle in $Q$, from which it follows that the isosceles triangle is $\triangle P_aP_{a+k/2}\,P_{a+k}$, and so $2|k$. Repeating this process on the legs of isosceles triangle ($\overline{P_aP_{a+k/2}},\,\overline{P_{a+k}P_{a+k/2}}$), it follows that $k = 2^m$ for some positive integer $m$ (if we allow degeneracy, then we can also let $m=0$).
Now take the isosceles triangle $P_xP_yP_z,\,0 \le x < y < z < n$ in the triangulation that contains the center of $\mathcal{P}$ in its interior; if a diagonal passes through the center, select either of the isosceles triangles with that diagonal as an edge. Without loss of generality, suppose $P_xP_y = P_yP_z$. From our previous result, it follows that there are $2^a$ edges of $P$ on the minor arcs of $P_xP_y,\, P_yP_z$ and $2^b$ edges of $P$ on the minor arc of $P_zP_x$, for positive integers $a,\,b$. Therefore, we can write
 so $n$ must be the sum of two powers of $2$.
We now claim that this condition is sufficient. Suppose without loss of generality that $a+1 \ge b$; then we rewrite this as
By induction, it follows that we can cover all the desired $n$.
For $n = 3,4$, this is trivial. For $k>1$, we construct the diagonals of equal length $\overline{P_0P_{2^{k-1}}}$ and $\overline{P_{2^{k-1}+1}P_0}$. This partitions $\mathcal{P}$ into $3$ regions: an isosceles $\triangle P_0P_{2^{k-1}}P_{2^{k-1}+1}$, and two other regions. For these two regions, we can recursively construct the isosceles triangles defined above in the second paragraph. It follows that we have constructed $2(2^{k-1}-1) + (1) = 2^k-1 = n-2$ isosceles triangles with non-intersecting diagonals, as desired.
We construct the diagonals $\overline{P_0P_2},\ \overline{P_2P_4},\ \ldots \overline{P_{2n-2}P_0}$. This partitions $\mathcal{P}$ into $n$ isosceles triangles of the form $\triangle P_{2k}P_{2k+1}P_{2k+2}$, as well as a central regular polygon with $n$ sides. However, we know that there exists a triangulation for the $n$-sided polygon that yields $n-2$ isosceles triangles. Thus, we have created $(n) + (n-2) = 2n-2$ isosceles triangles with non-intersecting diagonals, as desired.
In summary, the answer is all $n$ that can be written in the form $2^{a+1} + 2^{b},\, a,b \ge 0$. Alternatively, this condition can be expressed as either $n=2^{k},\, k \ge 2$ (this is the case when $a+1 = b$) or $n$ is the sum of two distinct powers of $2$, where $1= 2^0$ is considered a power of $2$.


(Kiran Kedlaya) Three nonnegative real numbers $r_1$, $r_2$, $r_3$ are written on a blackboard. These numbers have the property that there exist integers $a_1$, $a_2$, $a_3$, not all zero, satisfying $a_1r_1 + a_2r_2 + a_3r_3 = 0$. We are permitted to perform the following operation: find two numbers $x$, $y$ on the blackboard with $x \le y$, then erase $y$ and write $y - x$ in its place. Prove that after a finite number of such operations, we can end up with at least one $0$ on the blackboard.

Solution:
Every time we perform an operation on the numbers on the blackboard $R = \left < r_1, r_2, r_3 \right >$, we perform the corresponding operation on the integers $A = \left < a_1, a_2, a_3 \right >$ so that $R \cdot A = 0$ continues to hold.  (For example, if we replace $r_1$ with $r_1 - r_2$ then we replace $a_2$ with $a_1 + a_2$.)
It's possible to show we can always pick an operation so that $|A|^2$ is strictly decreasing. Without loss of generality, let $r_3 > r_2 > r_1$ and $a_3$ be positive. Then it cannot be true that both $a_1$ and $a_2$ are at least $\frac { - a_3}{2}$, or else $a_1r_1 + a_2r_2 + a_3r_3 > 0$. Without loss of generality, let $a_1 < \frac { - a_3}{2}$. Then we can replace $a_1$ with $a_1 + a_3$ and $r_3$ with $r_3 - r_1$ to make $|A|$ smaller. Since it is a strictly decreasing sequence of positive integers, after a finite number of operations we have $a_3 = 0$. We can now  see that this result holds for $(r_1,r_2,0)$ if and only if it holds for $(1,\frac{r_2}{r_1},0)$. We can see that $\frac{r_2}{r_1}$ is a rational number given that $a_3$ = 0. It is a well known result of the euclidean algorithm that if we continue to perform these operations, $r_1$ or $r_2$ will eventually be 0.


(Sam Vandervelde) At a certain mathematical conference, every pair of mathematicians are either friends or strangers. At mealtime, every participant eats in one of two large dining rooms. Each mathematician insists upon eating in a room which contains an even number of his or her friends. Prove that the number of ways that the mathematicians may be split between the two rooms is a power of two (i.e., is of the form $2^k$ for some positive integer $k$).

Make the obvious re-interpretation as a graph. Let $f : G \to \{0,1\}$ be an indicator function with $f(v) = 0$ if a vertex is in the first partition and $f(v) = 1$ otherwise (this corresponds, in the actual problem, to putting a mathematician in the first or second room). Then look at $f$ as a function into the field with two elements, $F_2$. Let $V$ be the vector space of all such functions. Define the linear operator $A : V \to V$ as

where $\sim$ denotes adjacency. (Note that we can also think of $A$ as a matrix, which is essentially the adjacency matrix where the diagonal is changed to be $1$ whenever the degree is odd; in more technical terms, it is the Laplacian of $G$ over $F_2$). Then $f$ is a valid partition iff $(Af)(v) = d(v)$, where $d$ is the degree of $v$, for all $v$ (this is taken over $F_2$). So we want all solution to $Af = d$. Note that if $Af = d, Ag = d$, then $A(f - g) = 0$, so $f - g$ is in the nullspace. Thus in particular the number of solutions, if non-zero, is the size of the nullspace of $A$, which is $2^{dim(Null(A))}$ by considering all linear combinations of any basis of $Null(A)$ over $F_2$. Also let $i$ be such that $i(v) = 1$ for all $v$. Then clearly $Ai = 0$, so $dim(Null(A)) > 0$, establishing that the number of ways to do this is $2^k$, $k > 0$. Thus we need only prove the existence of a solution.
Since we can add a new vertex connected to exactly one previously existing vertex without changing the problem, without loss of generality all vertices have odd degree. Then we want to show that $i \in Col(A)$. But it is a well-known fact in linear algebra that $Col(A) = Null(A^T)^{\perp} = Null(A)^{\perp}$ since $A$ is symmetric. Thus we need to show that if $f \in Null(A)$, $f$ is perpendicular to $i$ and we will be done. So let $f \in Null(A)$. Take the submatrix of $A$ consisting of the rows and columns $v$ such that $f(v) = 1$. Then, since $f \in Null(A)$, the sum of each row in this submatrix must be $0$ in $F_2$. Thus the total number of $1$s in this submatrix is even. But since it is symmetric, the total number of $1$s off of the diagonal is even, so the total number of $1$s on the diagonal is even. But since every vertex has odd degree, the entire diagonal of $A$ consists of $1$s, so this says that the size of the diagonal of this submatrix is even. But this is also the number of $v$ such that $f(v) = 1$, so $f(v) = 1$ for an even number of $v$, thus is perpendicular to $i$, and we have our result.

Define an order to be a set of instructions, one instruction given to each mathematician.  Each mathematician is told to either move or to stay (we can think of this as stay is $0$, and move is $1$).  Now take some good configuration.  Consider the set of all orders which, when performed on this configuration, give us another good configuration.  Note the identity order, $(0, 0, \ldots, 0)$, is in this set. We claim this set is an abelian group under composition.
Proof: Clearly each is its own inverse, there is the identity, and the operation is clearly associative and commutative (because it's equivalent to addition of n-dimensional vectors $\mod{2}$).  So it suffices to show this set of orders is closed under composition.
Consider any mathematician.  If, in one of these orders, he is told to stay, then the number of his friends who are told to move must be even.  Similarly, if he is told to move, then the number of his friends who are told to stay must be even.  Now just consider two orders $A$ and $B$ and you can show that in $A \times B$ the same property will hold using parity.
Now that we've shown it is a group (which we will call $G$), we'll prove it has order two.  Let $I$ be the identity.
Let $\{I, T_1\} = H_1$, where $T$ is some element of $G$.  Now pick an element $T_2$ of $G$ which is not in $H_1$.  Notice that because the elements of $H_1$ are distinct, the elements of $\{T_2X|X \in H_1\}$ are distinct (if two elements of that set were the same, multiply by each on the right by $T_2^{ - 1}$ and you have a contradiction).  Now notice that for any $A, B \in H_1$, if we were to have $T_2A = B$, then $T_2 = BA^{ - 1} \in H_1$.  Therefore, $H_1$ and $\{T_2X|X \in H_1\}$ are disjoint and of the same size.  Moreover, the product of any element in the first group and any element in the second group is a member of the second group.  Therefore, these two groups together form a group of order $2^2$.  Call this $H_2$. You progressively build larger and larger subgroups of $G$ until you get to $G$ itself, whose order must then be a power of two.  Therefore, the number of good configurations of the mathematicians was a power of two.
This, of course, was all assuming $I$ existed and was in the group.

Let $n$ be the number of participants at the conference. We proceed by induction on $n$.
If $n = 1$, then we have one participant who can eat in either room; that gives us a total of $2 = 2^1$ options.
Let $n\geq 2$. The case in which some participant, $P$, has no friends is trivial. In this case, $P$ can eat in either of the two rooms, so the total number of ways to split $n$ participants is twice as many as the number of ways to split $(n - 1)$ participants besides the participant $P$. By induction, the latter number is a power of two, $2^k$, hence the number of ways to split $n$ participants is $2\times 2^k = 2^{k+1}$, also a power of two. So we assume from here on that every participant has at least one friend.
We consider two different cases separately: the case when some participant has an odd number of friends, and the case when each participant has an even number of friends.
Claim: Some participant, $Z$, has an odd number of friends.
Remove $Z$ from consideration and for each pair $(X,Y)$ of $Z$'s friends, reverse the relationship between $X$ and $Y$ (from friends to strangers or vice versa).
Claim. The number of possible seatings is unchanged after removing $Z$ and reversing the relationship between $X$ and $Y$ in each pair $(X,Y)$ of $Z$'s friends.
Proof of the claim. Suppose we have an arrangement prior to $Z$'s departure. By assumption, $Z$ has an even number of friends in the room with him.
If this number is 0, the room composition is clearly still valid after $Z$ leaves the room.
If this number is positive, let $X$ be one of $Z$'s friends in the room with him. By assumption, person $X$ also has an even number of friends in the same room. Remove $Z$ from the room; then $X$ will have an odd number of friends left in the room, and there will be an odd number of $Z$'s friends in this room besides $X$. Reversing the relationship between $X$ and each of $Z$'s friends in this room will therefore restore the parity to even.
The same reasoning applies to any of $Z$'s friends in the other dining room. Indeed, there will be an odd number of them in that room, hence each of them will reverse relationships with an even number of individuals in that room, preserving the parity of the number of friends present.
Moreover, a legitimate seating without $Z$ arises from exactly one arrangement including $Z$, because in the case under consideration, only one room contains an even number of $Z$'s friends.
End Claim
Thus, we have to double the number of seatings for $(n - 1)$ participants which is, by the induction hypothesis, a power of 2. Consequently, for $n$ participants we will get again a power of 2 for the number of different arrangements.
Case 2: Each participant has an even number of friends.
In this case, each valid split of participants in two rooms gives us an even number of friends in either room.
Let $(A,B)$ be any pair of friends. Remove this pair from consideration and for each pair $(C,D)$, where $C$ is a friend of $A$ and $D$ is a friend of $B$, change the relationship between $C$ and $D$ to the opposite; do the same if $C$ is a friend of $B$ and $D$ is a friend of $A$. Note that if $C$ and $D$ are friends of both $A$ and $B$, their relationship will be reversed twice, leaving it unchanged.
Consider now an arbitrary participant $X$ different from $A$ and $B$ and choose one of the two dining rooms. [Note that in the case under consideration, the total number of participants is at least 3, so such a triplet $(A, B; X)$ can be chosen.] Let $A$ have $m$ friends in this room and let $B$ have $n$ friends in this room; both $m$ and $n$ are even. When the pair $(A, B)$ is removed, $X$'s relationship will be reversed with either $n$, or $m$, or $m + n - 2k$ (for $k$ the number of mutual friends of $A$ and $B$ in the chosen room), or 0 people within the chosen room (depending on whether he/she is a friend of only $A$, only $B$, both, or neither). Since $m$ and $n$ are both even, the parity of the number of $X$'s friends in that room will be therefore unchanged in any case.
Again, a legitimate seating without $A$ and $B$ will arise from exactly one arrangement that includes the pair $(A, B)$: just add each of $A$ and $B$ to the room with an odd number of the other's friends, and then reverse all the relationships between a friend of $A$ and a friend of $B$. In this way we create a one-to-one correspondence between all possible seatings before and after the $(A,B)$ removal.
Since the number of arrangements for $n$ participants is twice as many as that for $(n - 2)$ participants, and that number for $(n - 2)$ participants is, by the induction hypothesis, a power of 2, we get in turn a power of 2 for the number of arrangements for $n$ participants. The problem is completely solved.

By induction on the number of mathematicians, assuming solution exists for $n\leq k$ mathematicians. For $n=k+1$  mathematicians, if each of them has even degree then we're done. Otherwise, let $v$ be a node with odd degree, and denote its neighbors by $N(v)$. We form a new graph $G'$ by deleting $v$ and flipping all edges between members of $N(v)$. That is, for each pair of $a$ and $b$ in $N(v)$, they're connected in $G'$ if and only if they're not in $G$. By induction we know a solution $S'$ exists for $G'$, and it is easily verifiable that the similar solution $S$ exists in $G$ by adding $v$ to the side in $S'$ with even number of neighbors in $N(v)$.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Given circles $\omega_1$ and $\omega_2$ intersecting at points $X$ and $Y$, let $\ell_1$ be a line through the center of $\omega_1$ intersecting $\omega_2$ at points $P$ and $Q$ and let $\ell_2$ be a line through the center of $\omega_2$ intersecting $\omega_1$ at points $R$ and $S$.  Prove that if $P, Q, R$ and $S$ lie on a circle then the center of this circle lies on line $XY$.

Let $\omega_3$ be the circumcircle of $PQRS$, $r_i$ to be the radius of $\omega_i$, and $O_i$ to be the center of the circle $\omega_i$, where $i \in \{1,2,3\}$. Note that $SR$ and $PQ$ are the radical axises of $O_1$ , $O_3$ and $O_2$ , $O_3$ respectively. Hence, by power of a point(the power of $O_1$ can be expressed using circle $\omega_2$ and $\omega_3$ and the power of $O_2$ can be expressed using circle $\omega_1$ and $\omega_3$),

Subtracting these two equations yields that $O_1O_3^2 - r_1^2 = O_2O_3^2 - r_2^2$, so $O_3$ must lie on the radical axis of $\omega_1$ , $\omega_2$.
~AopsUser101


Let $n$ be a positive integer.  Determine the size of the largest subset of $\{ - n, - n + 1, \ldots , n - 1, n\}$ which does not contain three elements $a, b, c$ (not necessarily distinct) satisfying $a + b + c = 0$.

Let $S$ be a subset of $\{-n,-n+1,\dots,n-1,n\}$ of largest size satisfying $a+b+c\neq 0$ for all $a,b,c\in S$. First, observe that $0\notin S$. Next note that $|S|\geq \lceil n/2\rceil$, by observing that the set of all the odd numbers in $\{-n,-n+1,\dots,n-1,n\}$ works. To prove that $|S|\leq \lceil n/2\rceil$, it suffices to only consider even $n$, because the statement for $2k$ implies the statement for $2k-1$ as well. So from here forth, assume $n$ is even.
For any two sets $A$ and $B$, denote by $A+B$ the set $\{a+b\mid a\in A,b\in B\}$, and by $-A$ the set $\{-a\mid a\in A\}$. Also, let $A_+$ denote $A\cap\{1,2,\dots\}$ and $A_-$ denote $A\cap\{-1,-2,\dots\}$. First, we present a lemma:
Lemma 1: Let $A$ and $B$ be two sets of integers. Then $|A+B|\geq|A|+|B|-1$.
Proof: Write $A=\{a_1,\dots,a_n\}$ and $B=\{b_1,\dots,b_m\}$ where $a_1<\dots<a_n$ and $b_1<\dots<b_m$. Then $a_1+b_1,a_1+b_2,\dots,a_1+b_m,a_2+b_m,\dots,a_n+b_m$ is a strictly increasing sequence of $n+m-1$ integers in $A+B$.
Now, we consider two cases:
Case 1: One of $n,-n$ is not in $S$. Without loss of generality, suppose $-n\notin S$. Let $U=\{-n+1,-n+2,\dots,n-2,n-1,n\}$ (a set with $2n$ elements), so that $S\subseteq U$ by our assumption. Now, the condition that $a+b+c\neq 0$ for all $a,b,c\in S$ implies that $-S\cap(S_++S_-)=\emptyset$. Since any element of $S_++S_-$ has absolute value at most $n-1$, we have $S_++S_-\subseteq \{-n+1,-n+2,\dots,n-2,n-1\}\subseteq U$. It follows that $S_++S_-\subseteq U\setminus -S$, so $|S_++S_-|\leq 2n-|S|$. However, by Lemma 1, we also have $|S_++S_-|\geq |S_+|+|S_-|-1=|S|-1$.  Therefore, we must have $|S|-1\leq 2n-|S|$, or $2|S|\leq 2n+1$, or $|S|\leq n$.
Case 2: Both $n$ and $-n$ are in $S$. Then $n/2$ and $-n/2$ are not in $S$, and at most one of each of the pairs $\{1,n-1\},\{2,n-2\},\ldots,\{\frac n2-1,\frac n2+1\}$ and their negatives are in $S$. This means $S$ contains at most $2+(n-2)=n$ elements.
Thus we have proved that $|S|\leq n=\lceil n/2\rceil$ for even $n$, and we are done.

Let $Z_n$ be the set of subsets satisfying the $a+b+c \neq 0$ condition for $n$, and let $s_n$ be the largest size of a set in $Z_n$. Let $n = 2k$ if $n$ is even, and $n = 2k-1$ if $n$ is odd. We note that $s_n \ge 2k$ due to the following constuction:  or all of the odd numbers in the set. Then the sum of any three will be odd and thus nonzero.
Lemma 1: $s_{n+1} \le s_{n} + 2$. If $M_{n+1} \in Z_{n+1}, |M_{n+1}| = s_{n+1}$, then we note that $M_{n+1} \setminus \{-2n+1, 2n-1\} \in Z_n$, so $|M_{n+1}| - 2 \le s_n$. $\square$
Lemma 2: $s_{2k} = s_{2k-1}$. Suppose, for sake of contradiction, that $M_{2k} \in Z_{n+1}$ and $M_{2k} > s_{2k-1}$. Remove $2k,-2k$ from $M_{2k}$, and partition the rest of the elements into two sets $P_{2k-1}, Q_{2k-1}$, where $P$ and $Q$ contain all of the positive and negative elements of $M_{2k}$, respectively. (obviously $0 \not \in M_{2k}$, because $0+0+0 = 0$). WLOG, suppose $|P_{2k-1}| \ge |Q_{2k-1}|$. Then $|P_{2k-1}| + |Q_{2k-1}| \ge s_{2k-1} - 1 \ge 2k - 1$. We now show the following two sub-results:

This is sufficient, because the only two elements that may be in $M_{2k}$ that are not in $P_{2k-1}, Q_{2k-1}$ are $2k$ and $-2k$; for $M_{2k} > s_{2k-1}$, we must either have $|P_{2k-1}| + |Q_{2k-1}| = s_{2k-1} - 1 \ge 2k-1$ and both $2k,-2k \in M_{2k}$ [but by pigeonhole $|P_{2k-1}| \ge k$, see sub-lemma (A)], or $|P_{2k-1}| + |Q_{2k-1}| = s_{2k-1} \ge 2k$, and $2k \in M_{2k}$, in which case by (A) we must have $|Q_{2k-1}| < k$, violating (B).
(A): Partition $\{1,2,\ldots,2k-1\}$ into the $k$ sets $\{k\}, \{1,2k-1\}, \{2, 2k-2\}, \cdots, \{k-1, k+1\}$. Because $(k+\delta) + (k-\delta) - 2k = 0$, then if any of those sets are within $P_{2k-1}$, $-2k \not \in M_{2k}$. But by Pigeonhole at most $k-1$ elements may be in $P_{2k-1}$, contradiction.
(B): We prove this statement with another induction. We see that the statement easily holds true for $k=1$ or $2$, so suppose it is true for $k-1$, but [for sake of contradiction] false for $k$. Let $P_{2k-3} = P_{2k-1} \setminus \{2k-2, 2k-1\}$, and similarly for $Q_{2k-3}$. Again WLOG $|P_{2k-3}| \ge |Q_{2k-3}|$. Then we have $|P_{2k-1}| + |Q_{2k-1}| \le |P_{2k-3}| + |Q_{2k-3}| + 4$.
So we have $\begin{cases} s_1 &= 2 \\ s_{2k} &= s_{2k-1} \\ s_{2k-1} &\le s_{2k-2} + 2 \\  \end{cases}$ and by induction, that $s_n \le \boxed{2\left\lceil \frac n2 \right \rceil} = 2k$, which we showed is achievable above.


We define a chessboard polygon to be a polygon whose sides are situated along lines of the form $x = a$ or $y = b$, where $a$ and $b$ are integers. These lines divide the interior into unit squares, which are shaded alternately grey and white so that adjacent squares have different colors. To tile a chessboard polygon by dominoes is to exactly cover the polygon by non-overlapping $1 \times 2$ rectangles. Finally, a tasteful tiling is one which avoids the two configurations of dominoes shown on the left below. Two tilings of a $3 \times 4$ rectangle are shown; the first one is tasteful, while the second is not, due to the vertical dominoes in the upper right corner.
a) Prove that if a chessboard polygon can be tiled by dominoes, then it can be done so tastefully.
b) Prove that such a tasteful tiling is unique.

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


For $n \ge 2$ let $a_1$, $a_2$, ..., $a_n$ be positive real numbers such that
Prove that $\text{max}(a_1, a_2, ... ,a_n) \le  4 \text{min}(a_1, a_2, ... , a_n)$.

Solution:
Assume without loss of generality that $a_1 \geq a_2 \geq \cdots \geq a_n$. Now we seek to prove that $a_1 \le 4a_n$.
By the Cauchy-Schwarz Inequality,
Since $a_1 \ge a_n$, clearly $(a_1 - {a_n \over 4}) > 0$, dividing yields:

as desired.
Alternative Solution (by Deng Tianle, username: Leole)
Assume without loss of generality that $a_1 \geq a_2 \geq \cdots \geq a_n$.
Using the Cauchy–Bunyakovsky–Schwarz inequality and the inequality given,
(Note that $n-2 \ge 0$ since $n \ge 2$ as given!)
This implies that $3a_n -\frac{3a_1}{4} \ge 0 \iff 4a_n \ge a_1$ as desired.


Trapezoid $ABCD$, with $\overline{AB}||\overline{CD}$, is inscribed in circle $\omega$ and point $G$ lies inside triangle $BCD$.  Rays $AG$ and $BG$ meet $\omega$ again at points $P$ and $Q$, respectively.  Let the line through $G$ parallel to $\overline{AB}$ intersect $\overline{BD}$ and $\overline{BC}$ at points $R$ and $S$, respectively.  Prove that quadrilateral $PQRS$ is cyclic if and only if $\overline{BG}$ bisects $\angle CBD$.

We will use directed angles in this solution. Extend $QR$ to $T$ as follows:
If:
Note that
Thus, $BTRG$ is cyclic.
Also, note that $GSCP$ is cyclic because  depending on the configuration.
Next, we have $T, G, C$ are collinear since
Therefore,  so $PQRS$ is cyclic.
Only If:
These steps can be reversed.

Extend $QR$ to $T$, and let line $l \parallel AB$ intersect $\omega$ at $K$ and another point $V$, as shown:
If:
Suppose that $VP \cap CB = S'$, and $AC \cap QV = R'$. Pascal's theorem on the tuple $(V, P, A, C, B, Q)$ implies that the points $S'$, $R'$, and $G = PA \cap BQ$ are collinear. However, $AC$ and $BD$ are symmetrical with respect to the axis of symmetry of trapezoid $ABCD$, and $TQ$ and $VQ$ are also symmetrical with respect to the axis of symmetry of $ABCD$ (as $Q$ is the midpoint of $\overset{\frown}{DC}$, and $TV \parallel DC$). Since $R = BD \cap TQ$, $R$ and $R'$ are symmetric with respect to the axis of symmetry of trapezoid $ABCD$. This implies that line $R'G$ is equivalent to line $RG$. Thus, $S'$ lies on line $RG$. However, $S = BC \cap RG$, so this implies that $S' = S$.
Now note that $TVPQ$ is cyclic. Since $TV \parallel RS$, $\measuredangle VTQ = \measuredangle SRQ$. However, $\measuredangle VTQ + \measuredangle VPQ = 180^{\circ} = \measuredangle SRQ + \measuredangle SPQ$. Therefore, $PQRS$ is cyclic.
Only If:
Consider the same setup, except $Q$ is no longer the midpoint of $\overset{\frown}{DC}$. Note that $TV$ must be parallel to $RG$ in order for $PQRS$  to be cyclic. We claim that $S' = S$ and hope to reach a contradiction. Pascal's theorem on the tuple $(V, P, A, C, B, Q)$ implies that $S'$, $R'$, and $G = PA \cap BQ$ are collinear. However, there exists a unique point $Q$ such that $HQ$, $AC$, and $RG$ are concurrent. By If, $Q$ must be the midpoint of $\overset{\frown}{DC}$ in order for the concurrency to occur; hence, $R' \notin RS$. Then $R'G \cap BC = S' \neq S$, since $RG \cap BC = S$. However, this is a contradiction, so therefore $TV$ cannot be parallel to $RG$ and $PQRS$ is not cyclic.
Solution by TheBoomBox77


Let $s_1, s_2, s_3, \ldots$ be an infinite, nonconstant sequence of rational numbers, meaning it is not the case that $s_1 = s_2 = s_3 = \cdots.$  Suppose that $t_1, t_2, t_3, \ldots$ is also an infinite, nonconstant sequence of rational numbers with the property that $(s_i - s_j)(t_i - t_j)$ is an integer for all $i$ and $j$.  Prove that there exists a rational number $r$ such that $(s_i - s_j)r$ and $(t_i - t_j)/r$ are integers for all $i$ and $j$.

Solution:
Suppose the $s_i$ can be represented as $\frac{a_i}{b_i}$ for every $i$, and suppose $t_i$ can be represented as $\frac{c_i}{d_i}$. Let's start with only the first two terms in the two sequences, $s_1$ and $s_2$ for sequence $s$ and $t_1$ and $t_2$ for sequence $t$. Then by the conditions of the problem, we have $(s_2 - s_1)(t_2 - t_1)$ is an integer, or $(\frac{a_2}{b_2} - \frac{a_1}{b_1})(\frac{c_2}{d_2} - \frac{c_1}{d_1})$ is an integer. Now we can set $r = \frac{b_1 b_2}{d_1 d_2}$, because the least common denominator of $s_2 - s_1$ is $b_1 b_2$ and of $t_2 - t_1$ is $d_1 d_2$, and multiplying or dividing appropriately by $\frac{b_1 b_2}{d_1 d_2}$ will always give an integer.
Now suppose we kept adding $s_i$ and $t_i$ until we get to $s_m = \frac{a_m}{b_m}$ in sequence $s$ and $t_m = \frac{c_m}{d_m}$ in sequence $t$ so that $(t_m - t_i)(s_m - s_i)$ is an integer for all $i$ with $1 \le i < m$, where $m$ is a positive integer. At this point, we will have $r$ = $\frac{\prod_{n=1}^{m}b_n}{\prod_{n=1}^{m}d_n}$, because these are the least common denominators of the two sequences up to $m$. As we keep adding $s_i$ and $t_i$, $r$ will always have value $\frac{\prod_{n=1}^{m}b_n}{\prod_{n=1}^{m}d_n}$, and we are done.


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

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

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


There are $n$ students standing in a circle, one behind the
other. The students have heights $h_1 < h_2 < \ldots < h_n$. If a
student with height $h_k$ is standing directly behind a student
with height $h_{k-2}$ or less, the two students are permitted to
switch places. Prove that it is not possible to make more than
$\binom{n}{3}$ such switches before reaching a position in which
no further switches are possible.

We adopt the usual convention that $\binom{i}{j} = 0$ unless $0 \le j \le i$.
With this, the binomial coefficients are defined for all integers via the
recursion:
It is clear that the circle is oriented and all the students are facing in same direction (clockwise or counterclockwise). We'll call this direction forward.
In any switch consider the taller student to have moved forward and the shorter student to have remained stationary. No backward motion is allowed. With this definition of forward motion, the first two students with heights $h_1$ and $h_2$ are always stationary, while other students potentially move past them.
For $k > 2$, the student with height $h_k$ can never switch places with the student with height $h_{k-1}$, and the former can make at most $k-2$ more forward moves than the latter (when all the students of heights $h_1, \ldots h_{k-2}$ are between $h_k$ and $h_{k-1}$ in the forward direction).
Therefore, if the $(k-1)^{\mathrm{st}}$ student can make $s_{k-1}$ forward steps, the $k^{\mathrm{th}}$ student can make at most $s_{k-1} + k - 2$ steps. With $s_1 = s_2 = 0$ and $s_3 = 0 + (3-2) = 1$, and a constant second difference of $1$, we quickly see that $s_k = \binom{k-1}{2}$.
With $n$ students in all, the total number of steps is therefore at most $\sum_{i=3}^{n}\binom{i-1}{2} = \binom{n}{3}$. The sum is a telescoping sum since: $\binom{n}{3} - \binom{n-1}{3} = \binom{n-1}{2}.$

WLOG, let $h_k=k$.  Now, we find the end arrangement with the most switches possible.  We claim that the arrangement will be $n,n-1,n-2,\dots ,1$, where the left to right direction is the "backwards" direction.  To prove this makes the most switches, we show that there is always at least one more switch that can be done for any other arrangement.  This is elementary to show.  There will always be one height $x$ such that the number to its right is $2$ less than $x$, unless every number has $x-1$ to the right of $x$ (other than $2$ and $1$).  The exception occurs at our claim, so our claim is proven.  Now we want to find the maximum ways we can "undo" our arrangement.  But undoing a switch is just doing a switch from our arrangement in the opposite direction.  So, the start arrangement with the most possible switches is the reverse of the end arrangement or $1,2,3,\dots ,n$.
We want to find how many switches must be done to get from the start arrangement to the end arrangement.  We start by switching $n$ around until it cannot be switched anymore.  We find that we can switch $n$ $n-2$ times.  When we are switching (or, in other words, moving to the right) the number $k$, we can switch it $k-2$ times before it is to the left of $k-1$.  But then we can also switch each of $k+1,k+2,\dots ,n$ (in that order) $k-2$ times before they get stopped again.  Let $x=n-k+2$.  Then, the sum of the switches is $\sum\limits_{x=2}^{n-1} (n-x)(x-1)=\sum\limits_{x=1}^{n} (n-x)(x-1)$.
Rearranging and summing, we get


The $2010$ positive numbers $a_1, a_2, \ldots , a_{2010}$ satisfy
the inequality $a_ia_j \le i+j$ for all distinct indices $i, j$.
Determine, with proof, the largest possible value of the product
$a_1a_2\cdots a_{2010}$.

Solution: The largest possible value is


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

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

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

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

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


Let $q = \dfrac{3p-5}{2}$ where $p$ is an odd prime, and let
Prove that if $\dfrac{1}{p}-2S_q = \dfrac{m}{n}$ for integers
$m$ and $n$, then $m-n$ is divisible by $p$.

Solution:
Since $p$ is an odd prime, $p = 2r + 1$, for a suitable positive integer $r$, and consequently $q = 3r - 1$.
The partial-fraction decomposition of the general term of $S_q$ is:
therefore
with $a$ and $b$ positive relatively-prime integers.
Since $r < p$ and $p$ is a prime, in the final sum all the denominators are relatively prime to $p$, but all the numerators are divisible by $p$, and therefore the numerator $a$ of the reduced fraction $\frac{a}{b}$ will be divisible by $p$. Since the sought difference $m - n = (b-a) - b = -a$, we conclude that $p$ divides $m-n$ as required.


A blackboard contains 68 pairs of nonzero integers.  Suppose that for each positive integer $k$ at most one of the pairs $(k, k)$ and $(-k, -k)$ is written on the blackboard.  A student erases some of the 136 integers, subject to the condition that no two erased integers may add to 0.  The student then scores one point for each of the 68 pairs in which at least one integer is erased.  Determine, with proof, the largest number $N$ of points that the student can guarantee to score regardless of which 68 pairs have been written on the board.

Solution:
Answer: 43

Attainability: Consider 8 distinct positive numbers. Let there be 5 pairs for each of the numbers including 2 clones of that number. Let there also be 28 pairs that include the negatives of those numbers such that each negative associates with another negative once and exactly once (in graph theoretic terms, a K8). Let x be the number of positives chosen out of these 8 (assume the other chosen numbers are negatives) for erasing; then, the number of points the student scores is $28 + 5x - {x \choose 2}$, which is maximized at x=5 and x=6, and the maximum value is $43$. Choosing the first 5 numbers as positive and the other three as negative attains this. Hence, 43 is a possible maximum possible score.

Bounding: We use expected values. WLOG all the pairs of numbers with both numbers identical have only positive values. Consider flipping a weighted coin whether to choose the positive number or its negation for each positive number; it chooses positive with probability p. The pairs with both numbers same are chosen with probability p, the pairs (k, -k) are chosen with probability 1, and the pairs (x, y) for distinct x and y that sum to a nonzero number are chosen with probability $1-p^2$. We are trying to minimize the expected value, so we can assume that no pairs (k, -k) exist. Let A be the number of (k, k) pairs, and 68-A be the number of (x, y) pairs. The expected number of points scored is $Ap + (68-A)(1-p^2)$. We want to prove this is larger than 42 at all times for some choice of p. If $A < 36$, $1/2$ works for p to give this bound. If $A > 36$, $5/8$ works for p for p to give the desired bound. If $A = 36$, we can use $3/5$ for p to get the desired bound. Hence, in any case, the expected value for the number of points scored across all of these weighted processes is larger than 42, so there exists some case that gives a score of 43. Hence, bounding is complete. We are done with both parts. Q.E.D.
-Solution by thanosaops


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

Since

it is natural to consider a change of variables:

with the inverse mapping given by:

With this change of variables, the constraint becomes

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

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


An integer is assigned to each vertex of a regular pentagon so that the sum of the five integers is 2011. A turn of a solitaire game consists of subtracting an integer $m$ from each of the integers at two neighboring vertices and adding 2m to the opposite vertex, which is not adjacent to either of the first two vertices. (The amount $m$ and the vertices chosen can vary from turn to turn.) The game is won at a certain vertex if, after some number of turns, that vertex has the number 2011 and the other four vertices have the number 0. Prove that for any choice of the initial integers, there is exactly one vertex at which the game can be won.

Solution:
Let $\mathbb{F}_5$ be the field of positive residues modulo 5. We label the vertices of the pentagon clockwise with the residues 0, 1, 2, 3 and 4.
For each $i \in \mathbb{F}_5$ let $n_i$ be the integer at vertex $i$ and let $r_i \in \mathbb{F}_5$ be defined as:

Let $s = \sum_{i\in\mathbb{F}_5} n_i$. A move in the game consists of

for some vertex $i \in \mathbb{F}_5$ and integer $m$. We immediately see that $s$ is an invariant of the game. After our move the new value of $r_i$ is decreased by $3m + 2m \equiv 0 \pmod 5$ as a result of the change in the $3n_{i+2}$ and $2n_{i+3}$ terms. So $r_i$ does not change after a move at vertex $i$.
For all $i \in \mathbb{F}_5$ we have:
Therefore, the $r_i$ form an arithmetic progression in $\mathbb{F}_5$ with a difference of $s$. Since $r_k$ is unchanged by a move at vertex $k$, so are all the remaining $r_i$ as the differences are constant.
Provided $s \not\equiv 0 \pmod 5$, we see that the mapping $i \mapsto r_i$ is a bijection $\mathbb{F}_5 \to \mathbb{F}_5$ and exactly one vertex will have $r_i \equiv 0 \pmod 5$. As $r_i$ is an invariant, a winning vertex must have $r_i \equiv 0$, since in the final state each $n_k$ with $k \ne i$ is zero. So, for $s \not\equiv 0 \pmod 5$, if a winning vertex exists, it is the unique vertex with $r_i \equiv 0$.
Without loss of generality, it remains to show that if $r_0 \equiv 0 \pmod 5$, then 0 must be a winning vertex. To prove this, we perform the following moves:

We designate the new state $(n'_0, 0, n'_2, n'_3, 0)$. Since $r_0 \equiv 0$ is an invariant, and $n'_1 = n'_4 = 0$, we now have $r_0 \equiv n'_3 - n'_2 = 5p$, for some integer $p$. Our final set of moves is:

Now our chosen vertex 0 is the only vertex with a non-zero value, and since $s$ is invariant, that value is $s$ as required. Since a vertex $i$ with $r_i \equiv 0 \pmod 5$ is winnable, and with $s = 2011 \not\equiv 0 \pmod 5$ we always have a unique such vertex, we are done.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.


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

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

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

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

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


Let $P$ be a given point inside quadrilateral $ABCD$.  Points $Q_1$ and $Q_2$ are located within $ABCD$ such that $\angle Q_1 BC = \angle ABP$, $\angle Q_1 CB = \angle DCP$, $\angle Q_2 AD = \angle BAP$, $\angle Q_2 DA = \angle CDP$.  Prove that $\overline{Q_1 Q_2} \parallel \overline{AB}$ if and only if $\overline{Q_1 Q_2} \parallel \overline{CD}$.

Lemma. If $AB$ and $CD$ are not parallel, then $AB, CD, Q_1 Q_2$ are concurrent.
Proof. Let $AB$ and $CD$ meet at $R$. Notice that with respect to triangle $ADR$, $P$ and $Q_2$ are isogonal conjugates (this can be proven by dropping altitudes from $Q_2$ to $AB$, $CD$, and $AD$ or $BC$ depending on where $R$ is). With respect to triangle $BCR$, $P$ and $Q_1$ are isogonal conjugates. Therefore, $Q_1$ and $Q_2$ lie on the reflection of $RP$ in the angle bisector of $\angle{DRA}$, so $R, Q_1, Q_2$ are collinear. Hence, $AB, CD, Q_1 Q_2$ are concurrent at $R$.
Now suppose $Q_1 Q_2 \parallel AB$ but $Q_1 Q_2$ is not parallel to $CD$. Then $AB$ and $CD$ are not parallel and thus intersect at a point $R$. But then $Q_1 Q_2$ also passes through $R$, contradicting $Q_1 Q_2 \parallel AB$. A similar contradiction occurs if $Q_1 Q_2 \parallel CD$ but $Q_1 Q_2$ is not parallel to $AB$, so we can conclude that $Q_1 Q_2 \parallel AB$ if and only if $Q_1 Q_2 \parallel CD$.

First note that $\overline{Q_1 Q_2} \parallel \overline{AB}$ if and only if the altitudes from $Q_1$ and $Q_2$ to $\overline{AB}$ are the same, or $|Q_1B|\sin \angle ABQ_1 =|Q_2A|\sin \angle BAQ_2$.  Similarly $\overline{Q_1 Q_2} \parallel \overline{CD}$ iff $|Q_1C|\sin \angle DCQ_1 =|Q_2D|\sin \angle CDQ_2$.
If we define $S =\frac{|Q_1B|\sin \angle ABQ_1}{|Q_2A|\sin \angle BAQ_2} \times \frac{|Q_2D|\sin \angle CDQ_2}{|Q_1C|\sin \angle DCQ_1}$, then we are done if we can show that S=1.
By the law of sines, $\frac{|Q_1B|}{|Q_1C|}=\frac{\sin\angle Q_1CB}{\sin\angle Q_1BC}$ and $\frac{|Q_2D|}{|Q_2A|}=\frac{\sin\angle Q_2AD}{\sin\angle Q_2DA}$.
So, $S=\frac{\sin \angle ABQ_1}{\sin \angle BAQ_2}\cdot\frac{\sin \angle CDQ_2}{\sin \angle DCQ_1}\cdot\frac{\sin \angle BCQ_1}{\sin \angle CBQ_1}\cdot\frac{\sin \angle DAQ_2}{\sin \angle ADQ_2}$
By the terms of the problem, $S=\frac{\sin \angle PBC}{\sin \angle PAD}\cdot\frac{\sin \angle PDA}{\sin \angle PCB}\cdot\frac{\sin \angle PCD}{\sin \angle PBA}\cdot\frac{\sin \angle PAB}{\sin \angle PDC}$.  (If two subangles of an angle of the quadrilateral are equal, then their complements at that quadrilateral angle are equal as well.)
Rearranging yields $S= \frac{\sin \angle PBC}{\sin \angle PCB}\cdot\frac{\sin \angle PDA}{\sin \angle PAD}\cdot\frac{\sin \angle PCD}{\sin \angle PDC}\cdot\frac{\sin \angle PAB}{\sin \angle PBA}$.
Applying the law of sines to the triangles with vertices at P yields $S=\frac{|PC|}{|PB|}\frac{|PA|}{|PD|}\frac{|PD|}{|PC|}\frac{|PB|}{|PA|}=1$.


Let $A$ be a set with $|A| = 225$, meaning that $A$ has 225 elements.  Suppose further that there are eleven subsets $A_1$, $\dots$, $A_{11}$ of $A$ such that $|A_i | = 45$ for $1 \le i \le 11$ and $|A_i \cap A_j| = 9$ for $1 \le i < j \le 11$.  Prove that $|A_1 \cup A_2 \cup \dots \cup A_{11}| \ge 165$, and give an example for which equality holds.

We will count the number of ordered triples, $(A_i,A_j,x)$, where $1\le i,j\le11$ and $x\in A_i \cap A_j$. We know this is equal to $990=11\cdot10\cdot9$. We can also find that this is $\sum_{k=1}^{225}b_k^2-b_k$, where $b_k$ is the number of the $11$ subsets the $k^{\text{th}}$ element of $A$ is in. Since $\sum_{k=1}^{225}b_k=45\cdot11=495$, we know $\sum_{k=1}^{225}b_k^2=990+495=1485$. Let $n=|A_1 \cup A_2 \cup \dots \cup A_{11}|$. $n$ is equal to the number of $b_k>0$, where $1\le k\le225$. By the QM-AM inequality, we know $\frac{\sum_{k=1}^{225}b_k^2}n\ge\Bigg(\frac{\sum_{k=1}^{225}b_k}n\Bigg)^2\implies\frac{1485}n\ge\Big(\frac{495}n\Big)^2\implies n\ge165$ and that equality occurs when $b_1=b_2=b_3=\cdots=b_{165}=3,b_{166}=b_{167}=\cdots=b_{225}=0$.
$\square$
Solution by randomdude10807
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

Define $x_i$ to be the amount of elements in $A$ such that the element is contained exactly $i$ times among the $11$ subsets $A_j$. We are trying to prove that $\sum_{i=1}^{11}x_i\ge 165$. Now, note that $\sum_{i=1}^{11}ix_i$ is equivalent to the total amount of not necessarily distinct elements among the subsets $A_j$, thus $\sum_{i=1}^{11}ix_i=11|A_j|=495$. Furthermore, note that $\sum_{i=1}^{11}\binom{i}{2}x_i$ is equivalent to the total amount of not necessarily distinct pairs of subsets such that the subsets share an element. In other words, each subset pair should be counted $9$ times in this sum, and there are $\binom{11}{2}$ total distinct pairs of subsets, so $\sum_{i=1}^{11}\binom{i}{2}x_i=9*\binom{11}{2}=495$. Noting that $2\binom{i}{2}+i=i^2$ for all nonnegative integers, we note

Finally, CS inequality gives us
as desired.
One equality case occurs when $x_i=0$ if $i$ is not $3$, and $x_3=165$. Choose any $165$ elements, and represent each with a unique combination of $3$ of the $11$ subsets ($\binom{11}{3}=165$). It is then obvious that each subset has $45$ distinct elements, because after each subset is chosen, there are $\binom{10}{2}=45$ ways to choose the other two subsets to produce a unique element. Similarly, each pair of subsets shares exactly $9$ elements, because after choosing the two subsets, we can choose one of the remaining $9$ subsets to produce the unique element. Hence, proved. $\blacksquare{}$
~SigmaPiE


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

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

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

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


A circle is divided into 432 congruent arcs by 432 points.  The points are colored in four colors such that some 108 points are colored Red, some 108 points are colored Green, some 108 points are colored Blue, and the remaining 108 points are colored Yellow.  Prove that one can choose three points of each color in such a way that the four triangles formed by the chosen points of the same color are congruent.

Solution:
If you rotate the red points 431 times, they will overlap with blue points $108\times 108$ times, for an average of $\frac{108\times 108}{431}$ per rotation. Note that this average is slightly greater than 27. Therefore at some point 28 red points overlap with blue points. In other words, there exist 28 red and blue points such that the convex 28-gons formed by them are congruent.
Rotate these 28 red points 431 times. They will overlap with green points $108\times 28$ times, for an average of $\frac{108\times 28}{431}$ per rotation. This average is slightly greater than 7, so at some point 8 of those red points overlap with green points. In other words, there exist 8 red points, 8 blue points, and 8 green points such that the convex octagons formed by them are congruent.
Rotate these 8 red points 431 times. They will overlap with yellow points $108\times 8$ times, for an average of $\frac{108\cdot 8}{431}$ per rotation. This average is slightly greater than 2, so at some point 3 of those red points will overlap with yellow points. In other words, there exist 3 red points, 3 blue points, 3 green points, and 3 yellow points such that the triangles formed by them are congruent.


Determine which integers $n > 1$ have the property that there exists an infinite sequence $a_1$, $a_2$, $a_3$, $\dots$ of nonzero integers such that the equality

holds for every positive integer $k$.

(Since Bertrand's is well known and provable using elementary techniques, I see nothing wrong with this-tigershark22)
For $n=2$, $|a_1| = 2 |a_2| = \cdots = 2^m |a_{2^m}|$ implies that for any positive integer $m$, $|a_1| \ge 2^m$, which is impossible.
We proceed to prove that the infinite sequence exists for all $n\ge 3$.
First, one notices that if we have $a_{xy} = a_x a_y$ for any integers $x$ and $y$, then it is suffice to define all $a_x$ for $x$ prime, and one only needs to verify the equation (*)

for the other equations will be automatically true.
To proceed with the construction, I need the following fact: for any positive integer $m>2$, there exists a prime $p$ such that $\frac{m}{2} <p \le m$.
To prove this, I am going to use Bertrand's Postulate ([1]) without proof. The Theorem states that, for any integer $n>1$, there exists a prime $p$ such that $n<p\le 2n-1$. In other words, for any positive integer $m>2$, if $m=2n$ with $n>1$, then there exists a prime $p$ such that $\frac{m}{2} < p <  m$, and if $m=2n-1$ with $n>1$, then there exists a prime $p$ such that $\frac{m+1}{2} <p\le m$, both of which guarantees that for any integer $m>2$, there exists a prime $p$ such that $\frac{m}{2} <p \le m$.

Go back to the problem. Suppose $n\ge 3$. Let the largest two primes not larger than $n$ are $P$ and $Q$, and that $n\ge P > Q$. By the fact stated above, one can conclude that $2P > n$, and that $4Q = 2(2Q) \ge 2P > n$. Let's construct $a_n$:
Let $a_1=1$. There will be three cases: (i) $Q>\frac{n}{2}$,  (ii) $\frac{n}{2} \ge Q > \frac{n}{3}$, and (iii) $\frac{n}{3} \ge Q > \frac{n}{4}$.
Case (i): $2Q>n$. Let $a_x = 1$ for all prime numbers $x<Q$, and $a_{xy}=a_xa_y$, then (*) becomes:

Case (ii): $2Q\le n$ but $3Q > n$. In this case, let $a_2=-1$, and $a_x = 1$ for all prime numbers $2<x<Q$, and $a_{xy}=a_xa_y$, then (*) becomes:

or

Case (iii): $3Q\le n$. In this case, let $a_2=3$, $a_3=-2$, and $a_x = 1$ for all prime numbers $3<x<Q$, and $a_{xy}=a_xa_y$, then (*) becomes:

or
In each case, by Bezout's Theorem, there exists non zero integers $a_P$ and $a_Q$ which satisfy the equation. For all other primes $p > P$, just let $a_p=1$ (or any other non-zero integer).
This construction is correct because, for any $k> 1$,

Since Bertrand's Theorem is not elementary, we still need to wait for a better proof.
--Lightest 21:24, 2 May 2012 (EDT)


Find all functions $f : \mathbb{Z}^+ \to \mathbb{Z}^+$ (where $\mathbb{Z}^+$ is the set of positive integers) such that $f(n!) = f(n)!$ for all positive integers $n$ and such that $m - n$ divides $f(m) - f(n)$ for all distinct positive integers $m$, $n$.

Solution:
By the first condition we have $f(1)=f(1!)=f(1)!$ and $f(2)=f(2!)=f(2)!$, so $f(1)=1$ or $2$ and similarly for $f(2)$.  By the second condition, we have

for all positive integers $n$.
Suppose that for some $n \geq 2$ we have $f(n) = 1$.  We claim that $f(k)=1$ for all $k\ge n$. Indeed, from Equation (1) we have $f(n+1)!\equiv 1 \mod n\cdot n!$, and this is only possible if $f(n+1)=1$; the claim follows by induction.
We now divide into cases:
Case 1: $f(1)=f(2)=1$
This gives $f(n)=1$ always from the previous claim, which is a solution.
Case 2: $f(1)=2, f(2)=1$
This implies $f(n)=1$ for all $n\ge 2$, but this does not satisfy the initial conditions. Indeed, we would have

and so $2\mid -1$, a contradiction.
Case 3: $f(1)=1$, $f(2)=2$
We claim $f(n)=n$ always by induction. The base cases are $n = 1$ and $n = 2$. Fix $k > 1$ and suppose that $f(k)=k$.  By Equation (1) we have that

This implies $f(k+1)<2k$ (otherwise $f(k+1)!\equiv 0 \mod k\cdot k!$). Also we have

so $f(k+1)\equiv 1 \mod k$. This gives the solutions $f(k+1)=1$ and $f(k+1)=k+1$. The first case is obviously impossible, so $f(k + 1) = k + 1$, as desired.  By induction, $f(n) = n$ for all $n$.  This also satisfies the requirements.
Case 4: $f(1)=f(2)=2$
We claim $f(n)=2$ by a similar induction. Again if $f(k)=2$, then by (1) we have

and so $f(k+1)<2k$.  Also note that

and

so $f(k+1)\equiv 2 \mod k(k-1)$. Then the only possible solution is $f(k+1)=2$. By induction, $f(n) = 2$ for all $n$, and this satisfies all requirements.
In summary, there are three solutions: $\boxed{f(n)=1, f(n)=2, f(n)=n}$.


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

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

so

Similarly,

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

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

Similarly,

Therefore,

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

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

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

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


For integer $n \ge 2$, let $x_1$, $x_2$, $\dots$, $x_n$ be real numbers satisfying

For each subset $A \subseteq \{1, 2, \dots, n\}$, define

(If $A$ is the empty set, then $S_A = 0$.)
Prove that for any positive number $\lambda$, the number of sets $A$ satisfying $S_A \ge \lambda$ is at most $2^{n - 3}/\lambda^2$.  For what choices of $x_1$, $x_2$, $\dots$, $x_n$, $\lambda$ does equality hold?

For convenience, let $N=\{1,2,\dots,n\}$.
Note that $2\sum_{1\leq i<j\leq n} x_ix_j=\left(\sum_{i=1}^{n}x_i\right)^2-\left(\sum_{j=1}^{n} x_i^2\right)=-1$, so the sum of the $x_i$ taken two at a time is $-1/2$. Now consider the following sum:

Since $S_A^2\geq 0$, it follows that at most $2^{n-2}/\lambda^2$ sets $A\subseteq N$ have $|S_A|\geq \lambda$.
Now note that $S_A+S_{N/A}=0$. It follows that at most half of the $S_A$ such that $|S_A|\geq\lambda$ are positive. This shows that at most $2^{n-3}/\lambda^2$ sets $A\subseteq N$ satisfy $S_A\geq \lambda$.
Note that if equality holds, every subset $A$ of $N$ has $S_A\in\{-\lambda,0,\lambda\}$. It immediately follows that $(x_1,x_2,\ldots , x_n)$ is a permutation of $(\lambda,-\lambda,0,0,\ldots , 0)$. Since we know that $\sum_{i=1}^{n} x_i^2=1$, we have that $\lambda=1/\sqrt{2}$.

Let $x_i=x_1,x_2,...,x_n$ It is evident that $x_i = \frac{(-1)^i}{\sqrt{n}}$ for evens because of the second equation and $x_i=\frac{(-1)^i}{\sqrt{n-1}}$ for odds(one term will be 0 to maintain the first condition).
We may then try and get an expression for the maximum number of sets that satisfy this which occur when $\lambda = \frac{1}{\sqrt{n}}$:
since it will be

for any choice of A we pick, it will have to be greater than $\frac{1}{\sqrt{n}}$ which means we can either pick 0 negative $x_m$ or $j-1$ negatives for j positive terms. Since we also have that there are $\frac{n}{2}$ positive and negative terms for evens. Which then gives us:

and

For odd values, let it be the same as the last even valued sequence where n is even(i.e. the same as the sequence before it but with an extra 0 in one of the spots). Then, the following is apparent:
Thus, we may say that this holds to be true for all $n \ge 2$ since $n2^{n-3}$ grows faster than the sum. Note that equality holds when $S_A \in \{\lambda,0,-\lambda\}$ for all i which occurs when $x_i= \frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}},0,....$ and $\lambda = \frac{1}{\sqrt{2}}$ since $S_A=\frac{1}{\sqrt{2}}$ is the only choice for $S_A \ge \lambda$
$\blacksquare$


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

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

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

In addition, we have

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

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

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

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

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

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

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