Waste less time on Facebook — follow Brilliant.

SMO 2015 Senior Section Round 2 Questions

  1. In an acute-angled triangle \(ABC\), \(M\) is a poinr on the side \(BC\), the line \(AM\) meets the circumcircle \(\omega\) of \(ABC\) at the point \(Q\) distinct from \(A\). The tangent to \(\omega\) at \(Q\) intersects the line through \(M\) perpendicular to the diameter \(AK\) of \(\omega\) at the point \(P\). Let \(L\) be the point on \(\omega\) distinct from \(Q\) such that \(PL\) is tangent to \(\omega\) at \(L\). Prove that \(L, M\) and \(K\) are collinear.

  2. There are \(n = 1681\) children, \(a_{1}, a_{2}, \ldots , a_{n}\), seated clockwise in a circle on the floor. The teacher walks behind the children in the clockwise direction. She drops a candy behind the first child \(a_{1}\). She then skips one child and drops a candy behind the third child, \(a_{3}\). Now she skips two children and drops a candy behind the next child, \(a_{6}\). She continues this way, at each stage skipping one child more than at the preceding stage before dropping a candy behind the next child. How many children will never receive a candy? Justify your answer.

  3. Let \(n \ge 3\) be an integer. Prove that there exist positive integers \(a_{1}, a_{2}, \ldots , a_{n} > 1\) such that \(a_{1}a_{2}\ldots \hat{a_{i}}\ldots a_{n} \equiv 1 \pmod{a_{i}}\), for \(i = 1, \ldots , n\). Here \(\hat{a_{i}}\) means the term \(a_{i}\) is omitted.

  4. Is it possible to colour each square on a \(9 \times 9\) board so that each \(2 \times 3\) or \(3 \times 2\) block contains exactly \(2\) black squares? If so, what is/are the possible total number(s) of black squares?

  5. Let \(A\) be a point on the circle \(\omega\) centred at \(B\) and \(\Gamma\) a circle centred at \(A\). For \(i = 1,2,3\) a chord \(P_{i}Q_{i}\) of \(\omega\) is tangent to \(\Gamma\) at \(S_{i}\) and another chord \(P_{i}R_{i}\) of \(\omega\) is perpendicular to \(AB\) at \(M_{i}\). Let \(Q_{i}T_{i}\) be the other tangent from \(Q_{i}\) to \(\Gamma\), and \(N_{i}\) the intersection of \(AQ_{i}\) with \(M_{i}T_{i}\). Prove that \(N_{1},N_{2},N_{3}\) are collinear.

Note by Jake Lai
1 year, 4 months ago

No vote yet
1 vote


Sort by:

Top Newest

#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}\). Daniel Liu · 1 year, 4 months ago

Log in to reply

@Daniel Liu My contribution:

Note that we only need to calculate the residues mod \(41\) of the primes strictly less than \(41\) in order to calculate all of the residues mod \(41\), due to the fundamental theorem of arithmetic. This drastically speeds up the bashing. Jake Lai · 1 year, 4 months ago

Log in to reply

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. Xuming Liang · 1 year, 3 months ago

Log in to reply

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. Daniel Liu · 1 year, 4 months ago

Log in to reply

Thanks for sharing this with us! \(\LARGE\ddot\smile\). Nihar Mahajan · 1 year, 4 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...