SMO 2015 Senior Section Round 2 Questions

#2 Solution (maybe)

Note that we are trying to find the number of integers $0\le x < 1681$ such that $T_n=\dfrac{n(n+1)}{2}\equiv x\pmod{1681}$ is never satisfied for $0\le n < 1681$. First, multiply both sides by $8$, which we can do because $(8, 1681)=1$: $4n(n+1)\equiv 8x\pmod{1681}$ Now expand and add 1, factoring: $(2n+1)^2\equiv 8x+1\pmod{1681}$ Note that as $n$ cycles from $0\to 1680$, $2n+1$ goes through $0\to 1680$ too, so we can simplify further to $n^2\equiv 8x+1\pmod{1681}$ Finally, note that since $(8, 1681)=1$, there always exists an $0\le x<1681$ such that $8x+1\equiv k\pmod{1681}$ for any $0\le k < 1681$, so we can simplify to $n^2\equiv x\pmod{1681}$ Now we use the theorem that a number is a quadratic residue mod $p^k$ for odd prime $p$ iff it is a quadratic residue mod $p$. So, since $1681=41^2$, it suffices to consider the quadratic residues $\text{mod }41$ and use quadratic residue rules to deduce the number of quadratic residues mod 1681.

We bash (idk) to find that there are $21$ quadratic residues mod 41: $Q_{41}=\{0, 1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 21, 23, 25, 31, 32, 33, 36, 37, 39, 40\}$ (I'll use an integer $Q_n$ to denote that it is a quadratic residue mod n).

We now just have to consider if a number $Q_{1681}$ is a quadratic residue when $v_{41}(Q_{1681})=0\text{ or } 1$ because if $v_{41}(Q_{1681})\ge 2$ then $Q_{1681}\equiv 0\pmod{1681}$ which is a trivial quadratic residue.

If $v_{41}(Q_{1681})=0$, then we simply have the residues mod 41 due to the fact that $p^kQ_{p}= Q_{p^n}$ if $k<n$ is even, so we have: $Q_{1681}=41k+Q_{41}$ for $0\le k < 41$ which we can enumerate as $41\times 21=861$ residues.

If $v_{41}(Q_{1681})=1$, then there are no quadratic residues due to the fact that $p^kQ_{p}\ne Q_{p^n}$ if $k<n$ is odd.

finally, we see that we have $861$ total quadratic residues, which means that $1681-861 = 820$ numbers are not quadratic residues. Thus, the answer is $\boxed{820}$.

Thanks for sharing this with us! $\LARGE\ddot\smile$.

Let's first get the geos out of the way,

number 1. Let $O$ denote the center of $(ABC)$, $PM\perp AK$ at $X$. Observe that $OXQPL, XKQM$ are cyclic, using them to angle chase we have: $\angle MKQ=\angle MXQ=\angle QLP=\angle LQP=\angle LKQ$(the last equality stems from a property of tangent), $\angle MKQ=\angle LKQ$ is sufficient to prove that $M,K,L$ are collinear.

number 5. The problems essentially asks to show that $N$ lies on a fixed line, judging by a simple diagram I think it is not a bad guess that it is fixed on the radical axis of the two circles. If we want to prove this, then it only suffices to show that $M,T,S$ are collinear (can you see why?). This can be done through some angle chasing, utilizing the fact that $P,S,A,M$ are concyclic: $\angle MSA=\angle APM=arc RA/2=arc PA/2=\angle SQA=\angle TSA$. Just like the first problem, this equality is sufficient.

number 3. Starting small and focusing on one variable suggests induction could work. We first show that the problem still holds if all the product equal $-1$. Base case $n=3$: $(2,3,7)$ works. Inductive step: suppose $(a_1,...,a_n)$ satisfy the condition, then we can check that $a_1,...,a_n,a_{n+1}$ also works, where $a_{n+1}=a_1\cdot ... \cdot a_n+1$. Our main problem actually follows directly from this in that suppose $a_1,...,a_n$ satisfies the "$-1$" condition, then we can check that $a_1,...,a_n, b_{n+1}$ satisfies the "$1$" condition, where $b_{n+1}=a_1\cdot ... \cdot a_n-1$. Oh yeah and don't forget the base case $(2,3,5)$

number 4. The answer is yes, an example would be dividing the $9\times 9$ into nine $3\times 3$ and color the three diagonals black in which all colored diagonals face the same direction(slope of 1 or -1). There is only one possible value $27$ and we will prove that now.

First consider the problem with a $3\times 3$ square, we can check that there are two categories of ways to color it: one, the four corners with four blacks; two, each row and column has exactly one black with three blacks. For larger $n\times n$ we obviously cannot use the first coloring(can you see why?). Therefore, we are left with coloring each $3\times 3$ in $9\times 9$ with only three blacks. This establishes that $27$ is the only possible value with an example given.

I've reduced problem 3 to proving that $\left(\displaystyle\sum \dfrac{1}{a_i}\right) - \left(\dfrac{1}{\prod a_i}\right)=k$ has a solution for integer $k$ and $a_i \ge 2$, but I'm stuck now.