SMO 2015 Senior Section Round 2 Questions

  1. In an acute-angled triangle ABCABC, MM is a poinr on the side BCBC, the line AMAM meets the circumcircle ω\omega of ABCABC at the point QQ distinct from AA. The tangent to ω\omega at QQ intersects the line through MM perpendicular to the diameter AKAK of ω\omega at the point PP. Let LL be the point on ω\omega distinct from QQ such that PLPL is tangent to ω\omega at LL. Prove that L,ML, M and KK are collinear.

  2. There are n=1681n = 1681 children, a1,a2,,ana_{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 a1a_{1}. She then skips one child and drops a candy behind the third child, a3a_{3}. Now she skips two children and drops a candy behind the next child, a6a_{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 n3n \ge 3 be an integer. Prove that there exist positive integers a1,a2,,an>1a_{1}, a_{2}, \ldots , a_{n} > 1 such that a1a2ai^an1(modai)a_{1}a_{2}\ldots \hat{a_{i}}\ldots a_{n} \equiv 1 \pmod{a_{i}}, for i=1,,ni = 1, \ldots , n. Here ai^\hat{a_{i}} means the term aia_{i} is omitted.

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

  5. Let AA be a point on the circle ω\omega centred at BB and Γ\Gamma a circle centred at AA. For i=1,2,3i = 1,2,3 a chord PiQiP_{i}Q_{i} of ω\omega is tangent to Γ\Gamma at SiS_{i} and another chord PiRiP_{i}R_{i} of ω\omega is perpendicular to ABAB at MiM_{i}. Let QiTiQ_{i}T_{i} be the other tangent from QiQ_{i} to Γ\Gamma, and NiN_{i} the intersection of AQiAQ_{i} with MiTiM_{i}T_{i}. Prove that N1,N2,N3N_{1},N_{2},N_{3} are collinear.

Note by Jake Lai
4 years, 4 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

#2 Solution (maybe)

Note that we are trying to find the number of integers 0x<16810\le x < 1681 such that Tn=n(n+1)2x(mod1681)T_n=\dfrac{n(n+1)}{2}\equiv x\pmod{1681} is never satisfied for 0n<16810\le n < 1681. First, multiply both sides by 88, which we can do because (8,1681)=1(8, 1681)=1: 4n(n+1)8x(mod1681)4n(n+1)\equiv 8x\pmod{1681} Now expand and add 1, factoring: (2n+1)28x+1(mod1681)(2n+1)^2\equiv 8x+1\pmod{1681} Note that as nn cycles from 016800\to 1680, 2n+12n+1 goes through 016800\to 1680 too, so we can simplify further to n28x+1(mod1681)n^2\equiv 8x+1\pmod{1681} Finally, note that since (8,1681)=1(8, 1681)=1, there always exists an 0x<16810\le x<1681 such that 8x+1k(mod1681)8x+1\equiv k\pmod{1681} for any 0k<16810\le k < 1681, so we can simplify to n2x(mod1681)n^2\equiv x\pmod{1681} Now we use the theorem that a number is a quadratic residue mod pkp^k for odd prime pp iff it is a quadratic residue mod pp. So, since 1681=4121681=41^2, it suffices to consider the quadratic residues mod 41\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 2121 quadratic residues mod 41: Q41={0,1,2,4,5,8,9,10,16,18,20,21,23,25,31,32,33,36,37,39,40}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 QnQ_n to denote that it is a quadratic residue mod n).

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

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

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

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

Daniel Liu - 4 years, 4 months ago

Log in to reply

My contribution:

Note that we only need to calculate the residues mod 4141 of the primes strictly less than 4141 in order to calculate all of the residues mod 4141, due to the fundamental theorem of arithmetic. This drastically speeds up the bashing.

Jake Lai - 4 years, 4 months ago

Log in to reply

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

Nihar Mahajan - 4 years, 4 months ago

Log in to reply

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

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

number 5. The problems essentially asks to show that NN 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,SM,T,S are collinear (can you see why?). This can be done through some angle chasing, utilizing the fact that P,S,A,MP,S,A,M are concyclic: MSA=APM=arcRA/2=arcPA/2=SQA=TSA\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-1. Base case n=3n=3: (2,3,7)(2,3,7) works. Inductive step: suppose (a1,...,an)(a_1,...,a_n) satisfy the condition, then we can check that a1,...,an,an+1a_1,...,a_n,a_{n+1} also works, where an+1=a1...an+1a_{n+1}=a_1\cdot ... \cdot a_n+1. Our main problem actually follows directly from this in that suppose a1,...,ana_1,...,a_n satisfies the "1-1" condition, then we can check that a1,...,an,bn+1a_1,...,a_n, b_{n+1} satisfies the "11" condition, where bn+1=a1...an1b_{n+1}=a_1\cdot ... \cdot a_n-1. Oh yeah and don't forget the base case (2,3,5)(2,3,5)

number 4. The answer is yes, an example would be dividing the 9×99\times 9 into nine 3×33\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 2727 and we will prove that now.

First consider the problem with a 3×33\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×nn\times n we obviously cannot use the first coloring(can you see why?). Therefore, we are left with coloring each 3×33\times 3 in 9×99\times 9 with only three blacks. This establishes that 2727 is the only possible value with an example given.

Xuming Liang - 4 years, 4 months ago

Log in to reply

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

Daniel Liu - 4 years, 4 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...