assignmentutor™您的专属作业导师

*每年有6人被选入加拿大国际数学奥林匹克队，这是高中数学竞赛的顶峰。
*金、银、铜牌是根据你的分数百分位数颁发的。

## 下面是几道典型的SUMaC测试题目

Let five points on a circle be labelled $A, B, C, D$, and $E$ in clockwise order. Assume $A E=D E$ and let $P$ be the intersection of $A C$ and $B D$. Let $Q$ be the point on the line through $A$ and $B$ such that $A$ is between $B$ and $Q$ and $A Q=D P$. Similarly, let $R$ be the point on the line through $C$ and $D$ such that $D$ is between $C$ and $R$ and $D R=A P$. Prove that $P E$ is perpendicular to $Q R$.
Solution. We are given $A Q=D P$ and $A P=D R$. Additionally $\angle Q A P=180^{\circ}-\angle B A C=180^{\circ}-\angle B D C=\angle R D P$, and so triangles $A Q P$ and $D P R$ are congruent. Therefore $P Q=P R$. It follows that $P$ is on the perpendicular bisector of $Q R$.
We are also given $A P=D R$ and $A E=D E$. Additionally
$\angle P A E=\angle C A E=180^{\circ}-\angle C D E=\angle R D E$, and so triangles $P A E$ and $R D E$ are congruent.
Therefore $P E=R E$, and similarly $P E=Q E$. It follows that $E$ is on the perpendicular bisector of $P Q$.
Since both $P$ and $E$ are on the perpendicular bisector of $Q R$, the result follows.

Let $k$ be a given even positive integer. Sarah first picks a positive integer $N$ greater than 1 and proceeds to alter it as follows: every minute, she chooses a prime divisor $p$ of the current value of $N$, and multiplies the current $N$ by $p^{k}-p^{-1}$ to produce the next value of $N$. Prove that there are infinitely many even positive integers $k$ such that, no matter what choices Sarah makes, her number $N$ will at some point be divisible by $2018 .$
Solution: Note that 1009 is prime. We will show that if $k=1009^{m}-1$ for some positive integer $m$, then Sarah’s number must at some point be divisible by 2018 . Let $P$ be the largest divisor of $N$ not divisible by a prime congruent to 1 modulo 1009. Assume for contradiction that $N$ is never divisible by 2018. We will show that $P$ decreases each minute. Suppose that in the $t^{\text {th }}$ minute, Sarah chooses the prime divisor $p$ of $N$. First note that $N$ is replaced with $\frac{p^{k+1}-1}{p} \cdot N$ where
$$p^{k+1}-1=p^{1009^{m}}-1=(p-1)\left(p^{1009^{m}-1}+p^{1009^{m}-2}+\cdots+1\right)$$
Suppose that $q$ is a prime number dividing the second factor. Since $q$ divides $p^{1009^{m}}-1$, it follows that $q \neq p$ and the order of $p$ modulo $q$ must divide $1009^{m}$ and hence is either divisible by 1009 or is equal to 1 . If it is equal to 1 then $p \equiv 1(\bmod q)$, which implies that
$$0 \equiv p^{1009^{m}-1}+p^{1009^{m}-2}+\cdots+1 \equiv 1009^{m} \quad(\bmod q)$$
and thus $q=1009$. However, if $q=1009$ then $p \geq 1010$ and $p$ must be odd. Since $p-1$ now divides $N$, it follows that $N$ is divisible by 2018 in the $(t+1)^{\text {th }}$ minute, which is a contradiction. Therefore the order of $p$ modulo $q$ is divisible by 1009 and hence 1009 divides $q-1$. Therefore all of the prime divisors of the second factor are congruent to 1 modulo 1009. This implies that $P$ is replaced by a divisor of $\frac{p-1}{p} \cdot P$ in the $(t+1)^{\text {th }}$ minute and therefore decreases. Since $P \geq 1$ must always hold, $P$ cannot decrease forever. Therefore $N$ must at some point be divisible by 2018 .

Remark (no credit). If $k$ is allowed to be odd, then choosing $k+1$ to be divisible by $\phi(1009)=1008$ guarantees that Sarah’s number will be divisible by 2018 the first time it is even, which is after either the first or second minute.