Proving Collinearity

I AM BACK!

Hi guys! Sorry for the long six months hiatus. I have been involved in lots of bridge activities as well as university commitments in this six months. I realise that my brain has became quite rusty after not doing Math Olympiad for half a year. Now that I am back, I will try update as often as possible and get my brain functioning again ${>.<}$ Anyway I don’t think I will be able to update daily as I did at the start of the year. Back then updating the blog is kinda like my day job. Right now I am having my university vacation break and hopefully I can contribute as much as possible before school term starts again.

Today I want to talk about the techniques involved in proving collinearity in geometry. Proving collinearity is a central problem in MO as evident from the numerous problems which are set regarding this topic. Basically, we would like to show that three or more points in a diagram lies in a common line. Many creative problems can be set on this topic, but there are some common techniques and theorems involved in solving this type of problems. Similar to the series on proving perpendicularity, I will collate these techniques and discuss them over several posts.

Finding common angle

The first technique involves identifying a common angle between two lines. Suppose you want to prove that the three points ${A, B}$ and ${C}$ are collinear. Suppose ${B}$ and ${C}$ are on the same side of ${PA}$ and that ${\angle PAB = \angle PAC}$. If this is the case, we can conclude that ${A}$, ${B}$ and ${C}$ are collinear. This technique is useful if the conditions given in the question are related to angles. Here’s an illustration:

(China Second Round Olympiad 2012) In an acute triangle ${ABC}$, ${M, N}$ are distinct points on side ${BC}$ such that ${\angle BAM = \angle CAN}$. Let ${O_1}$ and ${O_2}$ be the circumcentres of ${\triangle ABC}$, ${\triangle AMN}$ respectively. Prove that ${O_1, O_2, A}$ are collinear.

I have always hated to draw diagrams in problems involving collinearity because the diagrams are usually very messy. Nevertheless this still has to be done. The diagram is not too hard to construct for this problem. Once constructed, it would seem that there are not clear directions in solving this problem (no similar triangles  , no application of Menalaus’ theorem, etc). However, with simple angle chasing, we might be able to prove that ${\angle O_1AB = \angle O_2 AB}$.

We start with a fact which is useful to know when it comes ti circumcircles. Given a triangle ${\triangle XYZ}$ and its circumcentre ${O}$, note that ${\angle OXY = 90^\circ - \angle XZY}$. This identity follows immediately upon the construction of the perpendicular bisector from ${O}$ to ${XY}$. We want to prove that ${\angle O_1AB = \angle O_2 AB}$. Let us start by writing ${\angle O_2AB}$ as ${\angle O_2AM + MAB}$. Using the identity mentioned, we note that ${O_2AM = 90^\circ - \angle MNA}$. We need to find a way to incorporate ${\angle NAC}$, and we can do so by writing ${\angle MNA = \angle NAC +\angle NCA}$. Hence, we have

\begin{aligned} \angle O_2AB &= \angle O_2AM + \angle MAB\\ &= 90^\circ - \angle MNA +\angle MAB\\ &= 90^\circ - \angle NCA - \angle NAC + \angle MAB\\ &= 90^\circ - \angle NCA\\ &= \angle O_1AB \end{aligned}

The last equality is achieved upon the application of the aforementioned identity.

Menalaus’ Theorem

It will be inappropriate to leave out this theorem in the discussion of collinearity. Menalaus’ theorem is one of the most powerful tools in proving collinearity, especially if triangles are involved. Simply identify the triangle and the three points on the triangle which one would like to prove is collinear, and then check if the corresponding ratios multiply to give us 1.

Here’s a problem from the recent USAMO:

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

IMO this is a relatively simple problem for USAMO P5 (The diagram is likely to be messy though ${><}$). The proof of this problem is very similar to the proof of Ceva’s theorem. Using the converse of Menalaus’ thoerem, the following relationship must hold:

$\displaystyle \frac{BA}{AC'}\times \frac{C'B'}{B'A'}\times \frac{A'C}{CB} = 1$

Next, we relate the ratios of lengths to the ratios of areas. Denote the area of ${\triangle XYZ}$ as ${S_{\triangle XYZ}}$. We have:

$\displaystyle \frac{S_{\triangle BPA}}{S_{\triangle APC'}}\times \frac{S_{\triangle C'PB'}}{S_{\triangle B'PA'}}\times \frac{S_{\triangle A'PC}}{S_{\triangle CPB}} = 1$

We can then express these areas using the sine formula, which simplifies to:

$\displaystyle \frac{\sin \angle BPA}{\sin \angle APC'}\times \frac{\sin \angle C'PB'}{\sin \angle B'PA'}\times \frac{\sin \angle A'PC}{\sin \angle CPB} = 1$

which is true based on the conditions of the question.

There are several other ways to solve the above problem. Coordinate bashing works well for this problem, although it is likely to take up much more time than the above approach. There is also an approach using Simson’s line, which I will discuss below.

Simson’s Line

The Simson’s Line approach is related to Menalaus’ theorem because it also involves collinear points on three sides of a triangle. However, this approach works better when circles are involved since the theorems involve the use of the circumcircle of the triangle.

Hmm I think I forgot to include Simson’s theorem in the geometry section above. Anyway, here’s the statement of the theorem:

Given a point ${P}$ in the plane of ${\triangle ABC}$. Suppose ${X, Y}$ and ${Z}$ are the feet of perpendiculars from ${P}$ to ${BC, CA}$ and ${AB}$ respectively. Then ${X, Y}$ and ${Z}$ are collinear if and only if ${P}$ lies on the circumcircle of ${\triangle ABC}$.

Referring to the USAMO problem above, it seems tough to apply Simson’s theorem on the problem above. Yes, we need to prove that the three points ${A', B'}$ and ${C'}$ are collinear, but there is no guarantee that the perpendiculars at ${A', B'}$ and ${C'}$ will intersect at one point. If the three perpendiculars are not concurrent, we cannot apply Simson’s theorem in this problem.

But who says that we are going to apply Simson’s theorem with regards to ${\triangle ABC}$? Clearly, we cannot use ${\triangle ABC}$ since the three perpendiculars are not concurrent. Instead, we are going to create a new triangle such that ${A', B'}$ and ${C'}$ lies on three different sides of this triangle. Also, we will guarantee that the perpendiculars from ${A', B'}$ and ${C'}$ of this new triangle will intersect at a unique point. To do so, we will need to decide on that special unique point where the perpendiculars will intersect. It comes without surprise that the point that we will choose is ${P}$. In this new triangle, which I shall call ${\triangle DEF}$, ${PA', PB'}$ and ${PC'}$ will be perpendicular to ${EF, DF}$ and ${DE}$ respectively. We can easily construct this new triangle as shown by the red lines below:

Now we just have to prove that ${P}$ is on the circumcircle of ${\triangle DEF}$. We do so by first noting that ${PB'C'D}$ and ${PA'FB'}$ are cyclic quadrilaterals, since ${\angle DC'P = \angle DB'P = 90^\circ}$ and ${\angle PB'F=\angle PA'F = 90^\circ}$. Next, note that ${\angle DPC' = \angle DB'C' = \angle A'B'F = \angle A'PF}$. Hence, ${\triangle DC'P}$ and ${\triangle PA'F}$ are similar. Finally, we have ${\angle C'DP = \angle A'FP}$ which proves that ${DEFP}$ is a cyclic quadrilateral. Voila!

This is my first time seeing this technique in applying Simson’s theorem. Although the diagram is messy, the approach is elegant and I admit that I doubt I will be able to derive this solution in my first attempt.

I will find some time to collate all geometry problems related to collinearity after describing other techniques involved. Perhaps I will do the same for other kinds of geometry problems such as perpendicularity, parallel lines, etc. It sure feels good to be back on this blog 🙂

P/S: Pfff took me two days to write this post… gotta work much harder ${><}$

Cheers,

ksj

SMO(J) Second Round Mock Paper 1

Here’s the latest mock paper for students in junior section. Based on the difficulty of the first round I guess the scores for most students will be very close. Every point in the second round will play a very important role for students to do well. I recommend students to treat these mock papers as real exams and write down all your final working to check that you don’t lose unnecessary marks for this round. You may check your workings or solutions with me if needed.

SMO(J) Second Round Mock Paper 1

I was slightly surprised when things like Cauchy Schwarz Inequality came out in junior section. It’s kinda hard to expect the kind of questions which will appear in SMO right now. Solutions are also attached in the above link.

Anyway, students in senior section should also try the problems in the above paper too, especially problem 5. I find it quite hard to find problems for junior section since most olympiads in the world are only divided into two sections instead of three, so please don’t mind if some problems are either too easy or too difficult 🙂

Cheers,

ksj

Another two interesting problems from SMO(O) First Round

IMO the paper this year is almost as hard as the paper last year because it is very computational heavy (even though there are less problems which require smart solutions)… As I was doing the paper I wasted a lot of time solving problems like P6, P14, P17, P22, etc. I think I solved around 18 problems within the 2.5 hours period, but there are many more problems which can be solved given more time. Again, the lack of pure geometry problems strongly suggest that the problem setting committee has changed… Perhaps this provides some hints for the second round of the paper?

Personally, I like problem 23 and 25 of the paper. I think I have seen both problems mentioned in some competition books before, and the solutions to these problems are pretty nice as compared to the brute nature of other problems.

(SMO(O) 2012 P23) The sequence ${(x_n)^{\infty}_{n=1}}$ is defined recursively by

$\displaystyle x_{n+1}=\dfrac{x_n+(2-\sqrt{3})}{1-x_n(2-\sqrt{3})}$

with ${x_1=1}$. Determine the value of ${x_{1001}-x_{401}}$.

My first instinct was that the answer is likely to be zero since the sequence is likely to be periodic and the two terms involved are 600 terms apart from each other, a number which is very easily divisible by lots of common factors. However I sort of doubted the accuracy of the problem when I figure out that ${x_4}$ is undefined. It was not until gc pointed out that the function resembles a tangent function that I was suddenly reminded of a similar problem which I have seen. Incidentally, the quantity ${2-\sqrt{3}}$ equals to ${\tan 15^\circ}$. If we define ${x_n=\tan \alpha_n}$, then we have

$\displaystyle \tan \alpha_{n+1}=\dfrac{\tan \alpha_n+\tan 15^\circ}{1-\tan \alpha_n \times \tan 15^\circ}=\tan(\alpha_n+15^\circ)$

Hence, we note that ${\tan \alpha_{n+12}=\tan \alpha_n}$. The period is 12 terms and hence the answer is 0.

I remember doing a similar problem to problem 25 when I was in Sec 4 on the topic of binomial expansion. Here’s the problem:

(SMO(O) 2012 P25) Evaluate ${\displaystyle{\frac{-1}{2^{2001}}\sum^{1006}_{k=0} (-1)^k3^k\binom{2012}{2k}}}$.

We need to construct a binomial expansion such that when expanded the value is equal to the expression in the problem. It seems like the binomial term is in the form of ${(1+x)^{2012}+(1-x)^{2012}}$ and we need to find a correct value for ${x}$ in solving the problem. Since the power of 3 is ${k}$, we would think that ${x}$ would resemble the number ${\sqrt{3}}$. On the other hand, the presence of ${-1}$ in the expansion strongly suggest the use of complex number. Hence, this strongly suggests that ${x=\sqrt{3}i}$ is the appropriate substitution and indeed it’s expansion gives us the summation in the problem. Upon the application of de Moivre’s theorem the problem can be cracked easily and the answer is 1.

Again you can check Lim Jeck’s blog for numerical solutions. Since the difficulty is similar to the paper last year, I would expect the cutoff point to be around 9.

Cheers,

ksj

Two interesting problems from SMO(S) First Round

I find the SMO(S) paper this year is slightly harder than the paper last year, but I guess it is still manageable by the students. The cutoff mark last year was 15 pts, and I think it will either be the same or slightly lower this year be lower this year (probably 11-13 10-11). The only disappointing thing about the paper this year is the lack of geometry problems… there’s only 3 geometry problems out of 35 questions (still I am not so concerned since geometry is a weak suit of many students.)

As I was invigilating the SMO paper this morning I spotted two very interesting problems which took me some time in finding the correct approach. Here are my two favourite problems from the paper:

(SMO(S) 2012 P29) Given that the real number $x, y$ and $z$ satisfies the condition $x+y+z=3$, find the maximum value of $f(x,y,z)=\sqrt{2x+13}+\sqrt[3]{3y+5}+\sqrt[4]{8z+12}.$

(Edit sorry the answer is not 8 because you can get really large values if $x, y, z$ can be negative, still I will leave my answer here for the case of positive numbers)

(Edit 2 NOW THIS IS REALLY FUNNY it seems like the maximum value is infinitely large when $x, z$ increases while $y$ takes a negative value… indeed by using Lagrange Multipliers it seems like 8 is not the global extremum… problem fail?)

Of course you will expect me to post an inequality problem here 🙂 My initial instinct was to use Lagrange’s Multipliers to whack this problem, since the usage of calculus is not prohibited in the first round. However it turns out that the system of equations is too nasty to be solved. It looks like this problem requires specific techniques to remove the surds. I considered Hölder’s inequality at first but the inequality is too loose and the equality case cannot be achieved. Then I turned to the use of substitution which is quite ugly but it produces the result ultimately.

Here’s a standard technique in removing surds in an inequality. We shall use the substitution $a=\sqrt{2x+13}, b=\sqrt[3]{3y+5}, c=\sqrt[4]{8z+12}$ to solve the problem. By removing the surds and standardising the coefficients for $x, y, z$, we convert the condition of the problem into $12a^2+8b^3+3c^4=304.$ The problem now requires us to maximise the quantity $a+b+c$. Somehow I was inspired when doing this problem and I realise that a very neat expression will be obtained when we multiply the condition by 27. We obtain $(18a)^2+(6b)^3+(3c)^4=8208.$ Behold… the numbers are going to be ugly from now onwards…

Now I am going to introduce 3 arbitrary constants $i, j, k$ into the condition to facilitate the usage of AM-GM inequality. We have:

$(18a)^2+i+(6b)^3+j+j+(3c)^4+k+k+k=8208+i+2j+3k.$

Using AM-GM inequality, we have:

$36\sqrt{i}a+18\sqrt[3]{j^2}b+12\sqrt[4]{k^3}c \le 8208+i+2j+3k.$

To find the maximum value of $a+b+c$, we must choose $i, j, k$ such that the coefficients of $a, b, c$ are the same. Hence, we need to find constants which satisfy the following equality:

$36\sqrt{i}=18\sqrt[3]{j^2}=12\sqrt[4]{k^3}.$

Simplifying and taking the equation to power 12 (yea, quite a lot to expect from a 2.5 hour paper…), we obtain…

$3^{12}\times 2^{12}i^6 = 3^{12} j^8 = 2^{12} k^9.$

With a bit of luck, we realise that the equality can be achieved when $i=5184, j=1728, k=1296$. Note that the equality case of AM-GM may not be achieved because we haven’t checked if the condition $x+y+z=3$ can be satisfied. But still I was very blessed because the above values of $i, j, k$ can produce us the equality case. Plugging these values back into the inequality, we obtain:

$2592(a+b+c) \le 8208+5184+3456+3888 = 20736$

and hence $a+b+c \le 8$. I admit that I have used calculators in deriving the answer… I was simply too lazy to calculate the large values. Anyway kudos to those we guessed the maximum value by plugging in the values $x=\frac{3}{2}, y=1, z=\frac{1}{2}.$ Do tell me if there’s a more elegant solution too 😀

Another very complicated but elegant problem is problem 35:

(SMO(S) 2012 P35) Let $f(n)$ be the integer nearest to $\sqrt{n}$. Find the value of

$\displaystyle{\sum_{n=1}^{\infty} \frac{(\frac{3}{2})^{f(n)}+(\frac{3}{2})^{-f(n)}}{(\frac{3}{2})^n}}$

As soon as I read the first sentence I was immediately reminded of the junior section round 2 problem which I took when I was Sec 2, which was actually a nice problem. Before that, the summation can be rearranged into the following form:

$\displaystyle{\sum_{n=1}^{\infty}\left[(\frac{2}{3})^{n-f(n)}+(\frac{2}{3})^{n+f(n)}\right]}$

Let $g(x)=x+f(x)$ and $h(x)=x-f(x)$. We consider the following values for $g(x)$ and $h(x)$:

$g(1)=2, g(2)=3, g(3)=5, g(4)=6, g(5)=7, g(6)=8, g(7)=10, \cdots.$

Basically, $g(x)$ is the sequence of positive numbers which are not squares. On the other hand,

$h(1)=0, h(2)=1, h(3)=1, h(4)=2, h(5)=3, h(6)=4, h(7)=4, \cdots.$.

So $h(x)$ is the sequence of positive numbers where the square numbers are repeated. Students can try and prove these two lemmas, and the solution can be found from the SMO 2007 solution book. As such, we have

$\displaystyle{\sum_{n=1}^{\infty}(\frac{2}{3})^{n-f(n)}+(\frac{2}{3})^{n+f(n)}=1+2\sum_{n=1}^{\infty}(\frac{2}{3})^n=1+2\times2=5}.$

So congratulations if you guessed the answer 5 🙂

Several problems in the paper are adapted from other olympiads or previous SMO problems. (How many times have I seen P32, even posted it in my algebra notess ><) I am lazy to do all questions in the paper, so for people who wants answer to the paper you can refer to Lim Jeck’s blog. I am not sure if all the answers there are correct though…

P/S: Forgot the prove that $x, y, z$ cannot be negative in problem 29 >< Gotta think for a moment bout that.

Cheers,

ksj

Solutions to SMO(S) Mock Paper 1

Here are the solutions to the previous mock paper.

SMO(S) Mock Paper 1

Just some random comments on the mock paper. The first problem is a very easy problem which can be solved without adding auxiliary lines. One shouldn’t spend too much time on this problem. In my opinion, most SMO(S) round 2 early geometry problems can be easily solved using few deductions only (except for the notorious P1 last year of course). Just be very alert to tricky similar figures and simple theorems will go a long way. Oh don’t forget Ceva’s Theorem, Menalaus’ Theorem etc are tested in senior section too. Last time when I was in Sec 4 I almost failed to solve the geom problem because I thought Menalaus’ Theorem is not covered. Oh by the way, some problems from the Russian Sharygin Geometry Olympiad closely resembles the standard of geometry problems in SMO(S) and SMO(O) so I highly recommend students to attempt them from the AoPS forum.

Students may spend more time on problem 2 in finding the pattern of the sequence. It is futile to find the general formula for the sequence since it is some complicated $n^{th}$ degree recurrence relation. The fact that the question asks for square numbers should prompt students to think about quadratic residues. Perhaps the product will give the same residue after being divided by some number? Perhaps each number of the sequence cannot be divisible by certain numbers (since 5 is in the recurrence relation, it seems natural to try mod 5). What about the greatest common divisor between any two numbers in the sequence? This are important pointers that the proposition of the problem prompts students to think about.

On the other hand, students will definitely spend a lot more time in solving the Diophantine equation in problem 3. Upon encountering this problem, I recommend students to think about the possible methods to solve Diophantine equations first before proceeding. IMO, I think this problem is screaming for students to find a bound for $n$. Once a bound is established, students just need to spend time to construct an example. Perhaps it might be easier for students to construct an example first before establishing a bound by factorising 2010 and 51. Oh speaking about 2010, students should investigate some properties of the number 2012… It certainly will appear in some round 1 questions…

Problem 4 only involves application of AM-GM inequality and Cauchy-Schwarz inequality. Personally I am slightly surprised that this question appeared in the Balkan MO this year because it is not that challenging. There are other approaches which can be used to solve this problem too. One approach is to use the substitution $a=\sqrt{x+y}$ etc to get rid of the square roots. Then I think basic expansion will solve the problem. You can also use the substitution $a=x+y$ and deduce that $a, b, c$ are sides of the triangle to solve the problem. By the way, DON’T FORGET TO STATE THE EQUALITY CASE OF THE INEQUALITY. Well in case you do not know how to solve the problem, do write down the equality case. Not sure if you will get some sympathy marks, someone else told me that it works.

Problem 5 is a fun problem which can be solved using some imagination. Personally I like my solution to the problem more than the official solution found in the APMO website. This type of problem will require good writing skills so that the readers can understand your solutions. It can be useful to define the grids as coordinates or define a process using your own terms. And of course if you are not able to solve the problem, at least construct an extreme case which you think satisfy the condition of the problem. You may get some marks anyway.

I think most students can solve problem 1, students with some experience in dealing with recurrence relations with a number theory twist can solve problem 2, problem 3 may be solved after guessing the solution, problem 4 will be tough if students follow the wrong direction, and problem 5 will be challenging especially if students have insufficient time. I guess 20-30 out of 50 marks should be a good expectation?

Will be creating a mock paper for junior section 2nd round next. I am too lazy to create mock papers for round 1 because 1) it requires 35 questions and 2) it is not fun to me. Gotta update the blog more often now since SMO is approaching…

Cheers,

ksj

SMO(S) 2nd Round Mock Paper 1

Here’s the first mock paper for SMO(S) 2nd round. I have chose all problems from recent olympiads around the world. Solutions will be posted along with the next set of problems.

SMO(S) Mock Paper 1

Cheers,

ksj

SMO(O) Mock Paper Solutions

Here are the solutions to the SMO(O) Mock Paper I posted few weeks ago. The highest score among the submissions which I received was 16/25. I haven’t finished typing the solutions though, but I will be updating the solutions soon.

SMO(O) Mock Paper

Here are the sources of the problems:

Putnam: 8

USAMO: 13

MMO: 4

ARML: 22

HMMT: 6, 10, 11, 15, 21, 23

ISL: 19, 24, 25

SMO: 17

APMO: 3, 14

I will be posting shorter mock papers on a frequent basis until SMO Round 2. Good luck for your preparations guys!

Cheers,

ksj

Junior section notes

Deadline for SMO(O) Mock Paper is approaching!

Here’s the set of geometry notes which I prepared for the junior section team. Wanted to include more details under auxiliary lines and transformation but didn’t manage to do so since I was sick…

A Review of Geometry

Here’s a mini test which I set for the junior section students:

Junior Section Mini Test

Cheers,

ksj

Combinatorics: The Next Step

Phew, finally completed the notes for the first 2 days of the Sec 2 MO course. Hope this explains the dearth of updates last week. This set of notes is probably useful for those in senior section too, especially chapter 3 in the notes. I have not included the solutions for chapter 3 yet because I do not have time to do so, will probably update it tomorrow.

Here you go:

Combinatorics: The Next Step

Yawns… Gotta run two courses during the sabbaticals, so I guess there will be less updates this week. Remember to submit your answers for the SMO mock paper! Deadline is this 20th May!

P/S: I have updated the file with the solutions for the second problem set.

Cheers,

ksj