Angle chasing with ellipses [Part 2]

by p_square, Jun 13, 2021, 8:51 AM

As promised, this post will mainly feature in-ellipses, and isogonal conjugates in quadrilaterals.

This post is going to be slightly hi-tech, pre-requisites include miquel points, inversion, and my previous post.

Before we dive right in, let's prove a quick lemma about the configuration we had before.
Let the tangents at $A$ and $B$ to an ellipse intersect at $P$ . If $O$ is the centre of the ellipse, then $[APO] = [BPO]$ . (Over here, [] denotes the area)

When one looks at the figure, the point $O$ really stands out. We know absolutely nothing about this point so far. Thus, it is only natural to try and convert these areas into the areas involving $F_1$ and $F_2$ instead of $O$ . Then, remembering how nice reflections of focii across tangents were, we add in $G$ which is $F_1$ reflected across $PA$ , and $H$ which is $F_2$ reflected across $PB$ . These points just make the whole proof come together:
$2[APO] = [APF_1] + [APF_2] = [APG] + [APF_2] = [GPF_2]$ Similarly,
$2[BPO] = [BPF_1] + [BPF_2] = [BPF_1] + [BPH] = [F_1PH]$
$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(70); real maj = 1.3, min = 1, a = 1.4, b=0.3; path el = ellipse((0,0),maj,min); draw(el, fuchsia); pair F1 = (sqrt(maj*maj - min*min),0); pair F2 = -F1; pair A = point(el,a), B = point(el,b); pair P = extension(A+dir(el,a), A, B, B+dir(el, b)); pair G = 2*foot(F2, P, A) - F2, H = 2*foot(F1, P, B) - F1; pair O = (F1 + F2)/2; draw(F1--P--G--F1, royalblue); draw(F2--P--H--F2, purple); draw(P--O--A--P--B--O, brown); dot("$O$",O,S); dot("$F_2$",F1,S); dot("$F_1$", F2, S); dot("$P$",P, dir(P)); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); dot("$H$", H, dir(H)); dot("$G$", G, dir(G)); [/asy]$

All that is left to show, is that $[APF_2] = [BPF_1]$ , but that's clear, the two triangles are simply congruent.

Consider any quadrilateral $ABCD$ with an in-ellipse tangent to sides $AB, BC, CD, DA$ at $X, Y, Z, W$ respectively.
Let $F_1, F_2$ and $O$ , be the focii and centre of the ellipse respectively. The first interesting result is that $\angle AF_1B + \angle CF_1D = \pi$ and the second is that $O$ lies on the gauss line of quadrilateral $ABCD$ .

Slightly restated, we want to show that $\angle AF_1B + \angle CF_1D = \angle AF_1D + \angle BF_1C$ , and that $[AOB] + [COD] = [AOD] + [BOC]$ .

The proofs of both of these results are pretty similar. The idea in a nutshell is to split and rearrange. [Another eerily similar idea is used to prove that the sums of opposite sides of a quadrilateral which has an incircle are equal]

$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(70); real maj = 1.15, min = 1, w = 3.0, x=1.9, y = 1.3, z = 0.3; path el = ellipse((0,0),maj,min); draw(el, fuchsia); pair F1 = (sqrt(maj*maj - min*min),0); pair F2 = -F1; pair W = point(el,w), X = point(el,x), Y = point(el, y), Z = point(el, z); pair A = extension(X, X+dir(el,x), W+dir(el,w),W); pair B = extension(dir(el,x)+X,X,Y,Y+dir(el,y)); pair C = extension(Z, Z+dir(el,z), Y+dir(el,y), Y); pair D = extension(dir(el,z) + Z, Z, W, W+dir(el, w)); draw(A--B--C--D--A, royalblue); draw(A--F2--B, purple); draw(C--F2--D, purple); draw(W--F2--Y, brown); draw(X--F2--Z, brown); draw(anglemark(B,F2,A), orange); draw(anglemark(D,F2,C), orange); draw(anglemark(C,F2,B)); draw(anglemark(A,F2,D)); dot("$W$", W, dir(W)); dot("$X$", X, dir(X)); dot("$Y$", Y, dir(Y)); dot("$Z$", Z, dir(Z)); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); dot("$C$", C, dir(C)); dot("$D$", D, dir(D)); dot("$F_1$", F2, S); [/asy]$

For the first theorem:
$\begin{align*} \angle AF_1B + \angle CF_1D &= \angle AF_1X + \angle XF_1B + \angle CF_1Z + \angle ZF_1D \\ &= \angle AF_1W + \angle YF_1B + \angle CF_1Y + \angle WF_1Z \\ &= \angle AF_1D + \angle BF_1C \end{align*}$
$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(70); real maj = 1.15, min = 1, w = 3.0, x=1.9, y = 1.3, z = 0.3; path el = ellipse((0,0),maj,min); draw(el, fuchsia); pair F1 = (sqrt(maj*maj - min*min),0); pair F2 = -F1; pair W = point(el,w), X = point(el,x), Y = point(el, y), Z = point(el, z); pair A = extension(X, X+dir(el,x), W+dir(el,w),W); pair B = extension(dir(el,x)+X,X,Y,Y+dir(el,y)); pair C = extension(Z, Z+dir(el,z), Y+dir(el,y), Y); pair D = extension(dir(el,z) + Z, Z, W, W+dir(el, w)); pair O = (0,0); draw(A--B--C--D--A, royalblue); draw(A--O--B, purple); draw(C--O--D, purple); draw(W--O--Y, brown); draw(X--O--Z, brown); dot("$W$", W, dir(W)); dot("$X$", X, dir(X)); dot("$Y$", Y, dir(Y)); dot("$Z$", Z, dir(Z)); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); dot("$C$", C, dir(C)); dot("$D$", D, dir(D)); dot("$O$",O, dir(D-C)); [/asy]$
For the second theorem:
$\begin{align*} [AOB] + [COD] &= [AOX] + [XOB] + [COZ] + [ZOD] \\ &= [AOW] + [YOB] + [COY] + [EOD] \\ &= [AOD] + [BOC] \end{align*}$
Also, something that follows from the triangle case, is that the $8$ points which are the feet of altitudes from $F_1$ and $F_2$ to $AB, BC, CD, DA$ are all concyclic, and are centred around the $O$ . The proof is also exactly the same. In fact, for any tangent, the foot of $F_1$ to that tangent has some fixed distance to $O$ .

We'll now discuss a few seemingly unrelated things.
Let $ABCD$ be a quadrilateral, and let point $E$ be arbitrary. Suppose $(AEB), (CED)$ meet at $F$ and $(AED), (CEB)$ meet at $G$ . Then, circles $(AGB), (CGD), (AFD), (CFB)$ concur. This concurrency point is called the clawson schmidt conjugate of $E$ with respect to $ABCD$ .

$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(110); pair A = dir(205), B = 0.7*dir(155), C = 0.8*dir(70), D = dir(-25); pair E = (-0.34, -0.2), F, G, H; F = 2*foot(E, circumcenter(E,A,B), circumcenter(E,C,D)) - E; G = 2*foot(E, circumcenter(E,A,D), circumcenter(E,B,C)) - E; H = 2*foot(F, circumcenter(B,F,C),circumcenter(A,F,D)) - F; draw(A--B--C--D--A, royalblue); draw(circumcircle(A,H,B), purple); draw(circumcircle(B,E,C), springgreen); draw(circumcircle(A,E,D), springgreen); draw(circumcircle(D,H,C), purple); draw(circumcircle(D,E,C), fuchsia); draw(circumcircle(A,F,D), brown); draw(circumcircle(A,E,B), fuchsia); draw(circumcircle(B,F,C), brown); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); dot("$C$", C, dir(C)); dot("$D$", D, dir(D)); dot("$E$", E, dir(E)); dot("$F$", F, dir(F)); dot("$G$", G, dir(G)); dot("$H$", H, dir(H)); path square = (-1.8, -1) -- (1.8, -1) -- (1.8, 1.2) -- (-1.8, 1.2) -- cycle; clip(currentpicture, square); [/asy]$

We first prove that the schmidt conjugate exists.
The main thing to notice in the diagram is that there are many circles. In fact there are wayy too many circles. Seeing so many circles, we realize we just _need_ to invert, and since we need to pick a point, let's just invert across $E$ with arbitrary radius. The result is surprising, let me let the diagram speak for itself:

$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(60); pair A = dir(205), B = 0.9*dir(155), C = 0.3*dir(70), D = 0.4*dir(-25); pair E = (-0.34, -0.2), F, G = (0,0), H = (0,0); F = extension(A,B,D,C); G = extension(A,D,B,C); H = 2*foot(F, circumcenter(B,F,C),circumcenter(A,F,D)) - F; draw(B--G--A,springgreen); draw(A--F--D, fuchsia); draw(circumcircle(H,B,C), brown); draw(circumcircle(H,A,D), brown); draw(circumcircle(H,D,C), purple); draw(circumcircle(H,A,B), purple); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); dot("$C$", C, dir(C)); dot("$D$", D, dir(D)); dot("$E$", E, dir(E)); dot("$F$", F, dir(F)); dot("$G$", G, dir(G)); dot("$H$", H, dir(H)); [/asy]$
(In case someone can't speak diagram-ese, $H$ just turns out to be the miquel point of $ABCD$ in the inverted figure! Also I've colour coded it so that it is hopefully easy to see which circle/line is the inverse of which circle)

Keeping in mind that the clawson-schmidt conjugate exists, we now turns towards _yet_ another seeming unrelated thing. Yes, I promise that we're getting somewhere and it's not just a wild goose chase.

There is a common inversion/reflection that often appears in quadrilateral olympiad geometry :-
Take quadrilateral $ABCD$ , with miquel point $M$ . Then, the transformation is as follows: for a point $P$ , invert it with radius $\sqrt{MA \cdot MC}$ , and reflect it across the bisector of $\angle AMC$ . The nice thing about this, is that since $M$ is the spiral centre of $AB \to DC$ , that $\sqrt{MA*MC} = \sqrt{MB*MD}$ , and that $\angle AMC, \angle BMD$ share an angle bisector. Thus in this transformation, $A$ and $C$ swap, $B$ and $D$ swap, and the other vertices of the complete quadrilateral also swap. We say call this transformation as "miquel inverting"

$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(60); pair A = dir(205), B = 0.7*dir(155), C = 0.8*dir(70), D = dir(-25); pair E = (-0.34, -0.2), F, G = (0,0), H = (0,0); F = extension(A,B,D,C); G = extension(A,D,B,C); H = 2*foot(F, circumcenter(B,F,C),circumcenter(A,F,D)) - F; draw(C--G--D, royalblue); draw(A--F--D, royalblue); draw(circumcircle(H,B,C), brown+dotted); draw(circumcircle(H,A,D), brown+dotted); draw(circumcircle(H,D,C), brown+dotted); draw(circumcircle(H,A,B), brown+dotted); draw(A--H--C, fuchsia); draw(B--H--D, orange); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); dot("$C$", C, dir(C)); dot("$D$", D, dir(D)); dot("$M$", H, dir(H)); [/asy]$

Now that we've introduced enough seemingly random things ~~and probably hopelessly confused whoever is reading this~~, let's actually relate some of them.
The first surprising result; Miquel inverting is the same as taking the clawson schmidt conjugate!!

Suppose after inverting $E$ went to the point $H'$ , we'll show that both $H$ and $H'$ satisfy some set of properties that uniquely determine the point, i.e. that will show that $H'$ is $H$ . Despite the short length of the proof, it is somewhat tricky, since one needs to choose the angle condition carefully.
For instance, if we simply suppose we pick $\angle HCB$ . From the inversion, we know that that $\angle H'CB = \angle H'CM - \angle BCM = \angle AEM - \angle BCM$ . However, if we try to show that $\angle HCB = \angle AEM - \angle BCM$ , we'll get hopelessly stuck. This is because, (as of now at least), we have absolutely no way of talking about $\angle AEM$ , or really any angle which involves line segment $EM$ .

$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(110); pair A = dir(205), B = 0.7*dir(155), C = 0.8*dir(70), D = dir(-25); pair E = (-0.36, -0.2), F, G, H; F = 2*foot(E, circumcenter(E,A,B), circumcenter(E,C,D)) - E; G = 2*foot(E, circumcenter(E,A,D), circumcenter(E,B,C)) - E; H = 2*foot(F, circumcenter(B,F,C),circumcenter(A,F,D)) - F; draw(A--B--C--D--A, royalblue); pair P, Q = (0,0), M = (0,0); P = extension(A,B,D,C); Q = extension(A,D,B,C); M = 2*foot(P, circumcenter(B,P,C),circumcenter(A,P,D)) - P; draw(circumcircle(D,E,C), fuchsia); draw(circumcircle(A,F,D), brown); draw(circumcircle(A,E,B), fuchsia); draw(circumcircle(B,F,C), brown); draw(D--H--C, springgreen); draw(M--H, springgreen); draw(A--E--B, purple); draw(E--M, purple); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); dot("$C$", C, dir(C)); dot("$D$", D, dir(D)); dot("$E$", E, dir(E)); dot("$F$", F, dir(F)); dot("$H$", H, dir(H)); dot("$M$", M, dir(M)); path square = (-1.8, -1) -- (1.8, -1) -- (1.8, 1.2) -- (-1.8, 1.2) -- cycle; clip(currentpicture, square); [/asy]$

Instead, the key idea is to try and evaluate $\angle H'CB + \angle H'DA$ and compare it to $\angle HCB + \angle HDA$ . (or try and get $\angle DH'C = \angle DHC$ ).
$\begin{align*} \angle H'CB + \angle H'DA &= \angle H'CM - \angle BCM + \angle H'DM + \angle MDA \\ &= \angle AEM - \angle BCM + \angle BEM + \angle MDA \\ &= \angle AEB + \angle MDA - \angle ADM \\ &= \angle AEB \end{align*}$
On the other hand,
$\begin{align*} \angle HCB + \angle HDA &= \pi - \angle HFB + \pi - \angle HFA \\ &= \angle AFB \\ &= \angle AEB \end{align*}$
Thus these two angles are equal. Since this must be true when any other side of the quadrilateral is picked, (Not just $CD$ ), we get that $H' = H$ . QED.
This means that clawson schmidt conjugation, and miquel inversion are the same transformation.

Now, we're finally ready for the main result.
Suppose a point $E$ in quadrilateral $ABCD$ has an isogonal conjugate. Then, it's isogonal conjugate must be its clawson schmidt conjugate!
The proof is similar to the above one. Suppose $H'$ is the isogonal conjugate of $E$ , and $H$ is the clawson schmidt conjugate. As we've shown above, $\angle HCB + \angle HDA = \angle AEB$ . On the other hand, $\angle H'CB + \angle H'DA = \angle ECD + \angle EDC = \pi - \angle CED = \angle AEB$ . This, and the other symmetric equations prove the desired result!

It's pretty astounding, how isogonal conjugation, clawson schmidt conjugation, and miquel inverting appear very different at first sight, but they are actually identical.

_______________________________________________________________________________________________

A couple of misc things about the above setup; especially the section provides a new interesting way to think about miquel points. Suppose we have a set of pairs $(X_1, Y_1), (X_2, Y_2), \dots$ , of size at least $2$ . We say that $M$ is the miquel point of the above set, if there is some inversion across $M$ followed by reflection across the line through $M$ , which swaps $X_i$ and $Y_i$ . The nice thing about this definition is that $M$ is themiquel point of quadrilateral $X_jY_kY_jX_k$ as per the usual definition. This is because $M$ is the centre of the spiral similarity taking $X_jY_k$ to $X_kY_j$ . Also, $X_tY_t$ are clawson schmidt conjugates in quadrilateral $X_jY_kY_jX_k$ . Of course, the set needn't be finite or even countable.

One interesting corollary of this is 'miquel nesting'
Suppose quadrilateral $ABCD$ has pairs of clawson conjugates $(P, Q), (U, V)$ and $(X, Y)$ . Then $(X, Y)$ are clawson conjugates in $PUQV$ as well.

We can go along this thought process a little further, and talk about isogonal nesting.
Suppose we have a set of pairs $(X_1, Y_1), (X_2, Y_2), \dots$ , of size at least $2$ , for which a miquel point exists. We call this as isogonal pair set, if the midpoints of $X_iY_i$ all lie on a straight line. The reason for this will become clear shortly.
Consider any pairs $X_1, Y_1$ , $X_2, Y_2$ and $X_3, Y_3$ from this isogonal set. Note that $X_3, Y_3$ are clawson schmidt conjugates in $X_1X_2Y_1Y_2$ . Further since their midpoint lies on the gauss line, by the converse of the first theorem we showed (We haven't proved the converse, but it should not be too hard), $X_3, Y_3$ are isogonal conjugates in $X_1X_2Y_1Y_2$ .
Again, one interesting corollary of this is 'isogonal nesting'
Suppose quadrilateral $ABCD$ has pairs of isogonal conjugates $(P, Q), (U, V)$ and $(X, Y)$ . Then $(X, Y)$ are isogonal conjugates in $PUQV$ as well.

__________________________________________________________________________________________________

I'll also soon (after IOI tgh) post a part 3 of this, where I showcase some oly problems which fall to these methods.

This post has been edited 2 times. Last edited by p_square, Jun 13, 2021, 3:18 PM

Angle chasing with ellipses [Part 1]

by p_square, May 24, 2021, 4:48 PM

Let's start with a classic puzzle. Imagine the following scenario. You stand at a point $F_1$ on the Euclidean plane. A picturesque straight river lies within your view, its nearer shore some line $PQ$ . A thirsty cat longs for water at some point $F_2$ on the same side of the river as you. What's the shortest path you can take to aid the cat with some water? A bit more mathematically, what's the shortest path from $F_1$ to $F_2$ which touches some line $PQ$ ?
$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(60); pair C = dir(30), P = dir(180), Q = dir(0), F2 = dir(-30), F1 = dir(-110); pair A = extension(F1, C, P, Q); pair A1 = A + (-0.3, 0); pair P1 = P + (0,0.1), Q1 = Q + (0,0.1), P2 = P+(0,0.05), Q2 = Q+(0,0.05); draw(P--Q, blue); draw(P1--Q1, blue); draw(P2--Q2, blue); dot("$F_1$",F1,N); dot("$F_2$",F2,N); label("You",F1 - (0,0.2)); label("Cat",F2 - (0,0.2)); dot("$P$",P,W); dot("$Q$",Q,E); [/asy]$
First observe that the path can be broken down into two straight lines, your trip to some point on the river (let's call that point $A$ ), and then the rush back towards the cat.
There are two very fundamentally different ways to approach this question.
Let's start with the more common one, and the one that provides the more satisfactory answer. Assume that there is another cat which stands at the reflection of $F_2$ across $PQ$ . (on the other side of the river). Let's denote this point by $C$ . There's an interesting correspondence between paths that bring the original cat water, and paths to this new cat $C$ : The correspondence being to reflect the portion of the path where you're carrying water across $PQ$ . Any path from $F_1$ to $F_2$ which crosses $PQ$ is the same length as a path from $F_1$ to $C$ .This implies that the length of your path is at least the distance between $F_1$ and $C$ . Conversely, it's easy to come up with a path that has a length $F_1C$ . Take the straight line $F_1C$ , and simply reflect the section of it lying on the other side of the river across $PQ$ .
$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(70); pair C = dir(30), P = dir(180), Q = dir(0), F2 = dir(-30), F1 = dir(-110); pair A = extension(F1, C, P, Q); pair A1 = A + (-0.3, 0); pair P1 = P + (0,0.1), Q1 = Q + (0,0.1); draw(P--Q, blue); draw(F1--A--F2, fuchsia); draw(A--C, fuchsia + dashed); draw(F1--A1--F2, springgreen); draw(A1--C, springgreen + dashed); dot("$F_1$",F1,dir(F1)); dot("$F_2$",F2,dir(F2)); dot("$C$",C,dir(C)); dot("$P$",P,N); dot("$Q$",Q,N); [/asy]$
As a side, note that since $AF_2$ is the reflection of $AF_1$ in $PQ$ , that $PQ$ is the external angle bisector of $F_1AF_2$ , that is $\angle PAF_1 = \angle QAF_2$ .

There's a completely different way of trying to find what the point $A$ on line $PQ$ should be. Let's pick a real number $d$ , and see if there is a point $A$ on line $PQ$ , such that $F_1A + F_2A = d$ (ie if your path length could possibly have distance $d$ ). Or, slightly rephrased, whether the ellipse with focii $F_1, F_2$ and focal distance $d$ , intersect $PQ$ . The smallest $d$ for which it does intersect line $PQ$ , is the shortest path length possible. Notice however, that for the smallest such $d$ , the ellipse will intersect the path at precisely one point, i.e. $PQ$ will be tangent to the ellipse!
This gives us an interesting setup. An ellipse with focii $F_1, F_2$ is tangent to $PQ$ at some point $A$ . And since we know that $A$ is the point on $PQ$ with distance $F_1A + AF_2$ minimal, from the first part, we know that $PQ$ is the external angle bisector of $F_1AF_2$ . And since by choosing $F_1, F_2$ , the ellipse could be arbitrary, this angle bisector property is true for every ellipse and tangent to that ellipse! Some people might recognize this as the so-called 'optical property'. It's pretty amazing how this tiny co-incidence, that just offers one pair of unexpected equal angles in an ellipse, paves way for many more.
$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(70); real maj = 1.3, min = 1, a = 0.8, b; path el = ellipse((0,0),maj,min); draw(el, fuchsia); pair F1 = (sqrt(maj*maj - min*min),0); pair F2 = -F1; pair A = point(el,a); pair P =A+1.3*dir(el, a), Q = A-1.3*dir(el,a); pair G = 2*foot(F1, P, Q)-F1; draw(P--Q, blue); draw(A--G, dashed+brown); draw(F1--G, orange); draw(F2--A--F1, brown); draw(anglemark(P,A,F2)); draw(anglemark(F1,A,Q)); dot("$F_2$",F1,S); dot("$F_1$", F2, S); dot("$Q$", Q, dir(Q)); dot("$P$",P, dir(P)); dot("$A$", A, dir(A)); dot("$G$", G, dir(G)); [/asy]$

If there's one thing to take away from the previous thought experiment, it's that thirsty cats will themselves walk towards the river to drink water, if you delay too long lost in mathematical thought. Another, equally profound, more mathematical take away could be that reflections of the focii over tangents to an ellipse are nice and deserve further investigation. Let's try a similar trick, this time with two tangents.
In the diagram below, the two tangents are $AP$ and $BP$ , and $G,H$ are the reflections of $F_1$ over these lines respectively. From the previous setup we see that $F_2AG$ and $F_2BH$ are collinear.
There's a lot of stuff going on in this diagram. Since $G$ and $H$ were reflections, we know that $PG = PF_1 = PH$ . Also, again from the previous diagram we had that $F_2G = F_2A + AF_1 = F_2B + BF_1 = F_2H$ . these together imply that $PF_2$ is the angle bisector of $GH$ !! The neat angle condition that arises from this, is that $\angle AF_2P = \angle BF_2P$ ! The result also of course holds for the other focus as well, that is $\angle AF_1P = \angle BF_1P$ .

$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(70); real maj = 1.3, min = 1, a = 1.3, b=0.6; path el = ellipse((0,0),maj,min); draw(el, fuchsia); pair F1 = (sqrt(maj*maj - min*min),0); pair F2 = -F1; pair A = point(el,a), B = point(el,b); pair P = extension(A+dir(el,a), A, B, B+dir(el, b)); pair G = 2*foot(F2, P, A) - F2, H = 2*foot(F2, P, B) - F2; draw(H--F1--G, brown); draw(H--F2--G, royalblue); draw(F1--P, purple); draw(P--((G+H)/2), purple+dashed); draw(G--H, springgreen); draw(P--foot(F2,A,P), fuchsia); draw(B--foot(F2,B,P), fuchsia); draw(G--P--H, orange); draw(F2--P, orange); draw(anglemark(P,F1,A)); draw(anglemark(B,F1,P)); dot("$F_2$",F1,S); dot("$F_1$", F2, S); dot("$P$",P, dir(P)); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); dot("$H$", H, dir(H)); dot("$G$", G, dir(G)); [/asy]$

A brief side before we look at the third angle property, we see that $F_1P, AP, BP, F_2P$ are respectively the angle bisectors of $BF_1A, F_1AF_2, AF_2B, F_2BF_1$ respectively, or $P$ is the incentre (excentre?) of self intersecting quadrilateral $F_1AF_2B$ . That's in itself quite a cool result.

$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(80); real maj = 1.3, min = 1, a = 1.3, b=0.6; path el = ellipse((0,0),maj,min); draw(el, fuchsia); pair F1 = (sqrt(maj*maj - min*min),0); pair F2 = -F1; pair A = point(el,a), B = point(el,b); pair P = extension(A+dir(el,a), A, B, B+dir(el, b)); draw(A--F2--B--F1--A, royalblue); draw(A--foot(P,A,F2), royalblue); draw(B--foot(P,B,F1), royalblue); draw(circumcircle(foot(P,A,F1),foot(P,A,F2),foot(P,B,F1)), brown); dot("$F_2$",F1,S); dot("$F_1$", F2, S); dot("$P$",P, dir(P)); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); [/asy]$

This also gives a very rich configuration when $AB$ passes though $F_1$ ! The excentre result translates to $PF_1 \perp AB$ , and to $P$ being the excentre of $F_2AB$ .

$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(70); real maj = 1.3, min = 1, a = 1.1, b=0.6; path el = ellipse((0,0),maj,min); draw(el, fuchsia); pair F1 = (sqrt(maj*maj - min*min),0); pair F2 = -F1; pair A = point(el,a); real ipt[] = intersect(el, (F2--(6F2-5A))); b = ipt[0]; pair B = point(el, b); pair P = extension(A+dir(el,a), A, B, B+dir(el, b)); draw(circumcircle(foot(P,A,F1),foot(P,A,F2),foot(P,B,F1)), brown); draw(A--B--F1--A, royalblue); draw(P--F2, orange); dot("$F_1$",F1,S); dot("$F_2$", F2, S); dot("$P$",P, dir(P)); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); [/asy]$

Last time, we reflected the same focus across both the tangents. This time we will reflect $F_1$ across one tangent ( $AP$ ) to get $G$ , and $F_2$ across the other ( $BP$ ) to get $H$ . The surprise lying in store for us this time, is a pair of congruent triangles. In particular, it turns out that $GPF_2$ is congruent to $F_1PH$ . [the respective sides can easily be shown to be equal]
What's even more interesting is the pair of equal angles that emerges from this. Since $\angle F_1PH = \angle GPF_2$ , we know that $\angle GPF_1 = \angle F_2PH$ , and dividing by $2$ , $\angle APF_1 = \angle F_2PB$ !

$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(70); real maj = 1.3, min = 1, a = 1.4, b=0.3; path el = ellipse((0,0),maj,min); draw(el, fuchsia); pair F1 = (sqrt(maj*maj - min*min),0); pair F2 = -F1; pair A = point(el,a), B = point(el,b); pair P = extension(A+dir(el,a), A, B, B+dir(el, b)); pair G = 2*foot(F2, P, A) - F2, H = 2*foot(F1, P, B) - F1; draw(F1--P--G--F1, royalblue); draw(F2--P--H--F2, purple); draw(A--P--B, brown); draw(anglemark(G,P,A)); draw(anglemark(B,P,H)); draw(anglemark(A,P,F2)); draw(anglemark(F1,P,B)); dot("$F_2$",F1,S); dot("$F_1$", F2, S); dot("$P$",P, dir(P)); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); dot("$H$", H, dir(H)); dot("$G$", G, dir(G)); [/asy]$

Here's all three angles conditions in a master diagram. Make sure that you're fairly comfortable with the diagram; For the rest of the post, I'll freely use all the three angle properties.

$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(70); real maj = 1.3, min = 1, a = 1.4, b=0.3; path el = ellipse((0,0),maj,min); draw(el, fuchsia); pair F1 = (sqrt(maj*maj - min*min),0); pair F2 = -F1; pair A = point(el,a), B = point(el,b); pair P = extension(A+dir(el,a), A, B, B+dir(el, b)); pair Pa = 2*A - P, Pb = 2*B - P; draw((1.4B-0.4P)--P--(1.5A-0.5P), fuchsia); draw(A--F2--B--F1--A, royalblue); draw(F2--P--F1, brown); draw(anglemark(A,P,F2), royalblue); draw(anglemark(F1,P,B), royalblue); draw(anglemark(P,F2,A), springgreen); draw(anglemark(B,F1,P), fuchsia); draw(anglemark(P,F1,A), fuchsia); draw(anglemark(B,F2,P), springgreen); draw(anglemark(Pa, A, F2), brown); draw(anglemark(F1, A, P), brown); draw(anglemark(P, B, F2)); draw(anglemark(F1, B, Pb)); dot("$F_2$",F1,S); dot("$F_1$", F2, S); dot("$P$",P, dir(P)); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); [/asy]$

The last property in particular, helps immensely when we seek characteristics of in-ellipses of polygons. Before we dive into what in-ellipses of triangles look like, a few definitions. Consider an arbitrary angle, say $\angle BAC$ . Two points $F_1$ and $F_2$ are said to be isogonal in $\angle BAC$ , iff $F_2$ lies on the reflection of $AF_1$ over the angle bisector of $BAC$ . The isogonal of $AF_1$ in $\angle BAC$ is the the reflection of $AF_1$ across the bisector of $\angle BAC$ .
A point $F_2$ the isogonal conjugate of $F_1$ with respect to triangle $ABC$ , if it lies on all three isogonals i.e. $F_2$ is the unique point which lies on the

reflection of $AF_1$ over bisector of $\angle BAC$ ,
reflection of $BF_1$ over bisector of $\angle CBA$ , and
reflection of $CF_1$ over bisector of $\angle ACB$ .

The slick thing is that in a triangle, isogonal conjugates always exist - the above three lines always concur. Why do they concur? You guessed it - Ellipses.

Let the $B$ -isogonal of $BF_1$ , and $C-$ isogonal of $CF_1$ meet at $F_2$ . We'll show that $F_2$ also lies on the third isogonal. For this, consider the ellipse with foci $F_1$ and $F_2$ tangent to $BC$ at some point $X$ . Let the other tangent from $B$ to the ellipse touch the ellipse at $Y$ , and let the other tangent from $C$ to the ellipse touch the ellipse at $Z$ . Since we have that $\angle ABF_1 = \angle XBF_2 = \angle YBF_1$ , we see that $AYB$ are collinear, and similarly $AZC$ are collinear. $A$ is the intersection of tangent from $Y$ to the ellipse, and $Z$ to the ellipse. This literally spells out $\angle YAF_1 = \angle ZAF_2$ , this is exactly the third isogonality which we wanted to prove!

$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(70); real maj = 1.2, min = 1, a = 2.8, b=0.3, c = 1.5; path el = ellipse((0,0),maj,min); draw(el, fuchsia); pair F1 = (sqrt(maj*maj - min*min),0); pair F2 = -F1; pair X = point(el,a), Y = point(el,b), Z = point(el, c); pair A = extension(Y, dir(el, b)+Y, dir(el, c) + Z, Z); pair B = extension(Z, dir(el, c) + Z, X+dir(el, a), X); pair C = extension(X, X+dir(el, a), Y+dir(el, b), Y); draw(A--B--C--A, royalblue); draw(F2--A--F1, orange); draw(F2--B--F1, brown); draw(F2--C--F1, brown); dot("$F_1$",F1,S); dot("$F_2$", F2, S); dot("$C$",C, dir(C)); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); dot("$X$",X, dir(X)); dot("$Y$", Y, dir(Y)); dot("$Z$", Z, dir(Z)); [/asy]$

The above also gives a nicer definition of the isogonal conjugate. The isogonal conjugate of a point $F_1$ in triangle $BAC$ , is the unique point $F_2$ , such that there is an inellipse of $ABC$ with foci $F_1$ and $F_2$ .

We'll also now claim, that the 6 feet of altitudes, from the two foci to the three the sides of a triangle lie on a circle. (This is called the pedal circle). We'll further show that this circle is centered at the centre of the ellipse, $O$ .
$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(70); real maj = 1.4, min = 1, a = 2.9, b=0.3, c = 1.5; path el = ellipse((0,0),maj,min); draw(el, fuchsia); pair F1 = (sqrt(maj*maj - min*min),0); pair F2 = -F1; pair X = point(el,a), Y = point(el,b), Z = point(el, c); pair A = extension(Y, dir(el, b)+Y, dir(el, c) + Z, Z); pair B = extension(Z, dir(el, c) + Z, X+dir(el, a), X); pair C = extension(X, X+dir(el, a), Y+dir(el, b), Y); pair U = foot(F1,B,C); pair V = 2*U - F1; pair O = (0,0); draw(A--B--C--A, royalblue); draw(F2--A--F1, orange); draw(F2--B--F1, orange); draw(F2--C--F1, orange); draw(O--U, brown); draw(F2--V, purple); draw(circumcircle(U, foot(F1,A,B), foot(F1,A,C)), brown); draw(F1--foot(F1,C,A), dotted); draw(F1--foot(F1,B,A), dotted); draw(F1--V, dotted); draw((-maj,0)--(maj,0), brown); draw(F2--foot(F2,C,A), dotted); draw(F2--foot(F2,B,A), dotted); draw(F2--foot(F2,C,B), dotted); dot("$F_1$",F1,S); dot("$F_2$", F2, S); dot("$C$",C, dir(C)); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); dot("$X$",X, dir(X)); dot("$Y$", Y, dir(-Y)); dot("$Z$", Z, dir(-Z)); dot("$O$",O, dir(90)); dot("$U$", U, dir(U)); dot("$V$", V, dir(V)); [/asy]$
Let $V$ be the reflection of $F_1$ in $BC$ and let $U$ be the foot of altitude from $F_1$ onto $BC$ . Remember that $F_2VX$ are collinear, and that $F_2X = F_2X + XV = F_2X + F_1X$ . Dilating by $\frac12$ from $F_1$ , we see that $OU = \frac{F_1X + F_2X}{2}$ . Since this quantity will be constant whichever focus we take, and whichever side we drop the altitude to, we get that all six points fomed by dropping a perpendicular from the focii to the sides are concyclic.

Isogonal conjugates and inellipses become even more interesting in quadrilaterals (and I'll definitely write a post on those too soon!), but let's come back to those later.
Let's for now move on to a few more elementary properties. Suppose that we have two parallel chords $AB$ and $CD$ . Let $M$ and $N$ be the midpoints of $AB$ and $CD$ . Then, $MN$ passes through the centre of the ellipse!
To see this, we first need a new way of thinking about ellipses. It's popularly known that an ellipse can be formed by cutting a cone with a plane. [this is probably the most standard definition] What's slightly less commonly heard of, but as neat, is that the intersection of a cylinder and plane is also an ellipse! This intuitively ought to be true, because in a sense, an infinite cylinder is the limiting case of a cone, just imagine taking the top vertex of a cone and sliding it to infinity. The proof that the figure that emerges is an ellipse is also exactly the same.

$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(60); real maj = 1.2, min = 1, a = 2.85, b=1.35, c = 0.4, d; path el = ellipse((0,0),maj,min); draw(el, fuchsia); pair F1 = (sqrt(maj*maj - min*min),0); pair F2 = -F1; pair A = point(el, a), B = point(el, b), C = point(el, c); real ipt[] = intersect(el, (C+0.1A-0.1B)--(C+5A-5B)); d = ipt[0]; pair D = point(el, d), O = (0,0); pair M = (A+B)/2; pair N = (C+D)/2; draw(A--B, brown); draw(C--D, brown); draw(M--N, royalblue); dot("$F_1$",F1,S); dot("$F_2$", F2, S); dot("$C$",C, dir(C)); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); dot("$D$",D, dir(D)); dot("$O$",O,S); [/asy]$

Now that we have that, let's think of our ellipse as being such an intersection, and let's consider projecting the ellipse down to a plane perpendicular to the cylinder. The ellipse gets projected down to a circle, and the parallel chords remain parallel chords. It's also easy to check that midpoints go to midpoints, and so does the line through the midpoints. To finish, we just need to show the theorem for a circle. This luckily is really easy. The line joining the midpoints of parallel chords in a circle is just the perpendicular bisector and that definitely passes through the centre of the circle.

$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(60); real maj = 1, min = 1, a = 2.85, b=1.35, c = 0.4, d; path el = ellipse((0,0),maj,min); draw(el, fuchsia); pair F1 = (sqrt(maj*maj - min*min),0); pair F2 = -F1; pair A = point(el, a), B = point(el, b), C = point(el, c); real ipt[] = intersect(el, (C+0.1A-0.1B)--(C+5A-5B)); d = ipt[0]; pair D = point(el, d), O = (0,0); pair M = (A+B)/2; pair N = (C+D)/2; draw(A--B, brown); draw(C--D, brown); draw(M--N, royalblue); dot("$C$",C, dir(C)); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); dot("$D$",D, dir(D)); dot("$O$",O,S); [/asy]$
In case the 3d-geo above was difficult to follow, there's a nice alternative way of thinking about the transformation we just did. Take the ellipse and it's chords, and forcefully squish it down into a circle. More formally, first ensure that the major axis of the ellipse is parallel to the $x-$ axis. We'll pick some constant $c$ , and send the point with co-ordinates $(x, y)$ to the point with co-ordinates $(cx, y)$ . Wisely picking $c$ changes the ellipse to a circle, and the definition of every other point in the figure remains the same.

Leaving ellipses aside, let's now consider parabolas.
Formally, a parabola is the locus of points which are equidistant from some point $P$ and some line $l$ . In an informal non-rigorous sense, a parabola is an ellipse, with one focus at infinity ~~Don't quote me on this, ok?~~. If we take $Q$ to be the point at infinity along the line perpendicular to $l$ , and let $Z$ be a variable point on the parabola, speaking informally, $QZ + PZ$ should be the fixed distance from $Q$ to line $l$ . [As an interesting side note, this intuition about parabolas being the same as ellipses can actually be realized by shifting to the projective plane]
Formalities set aside however, the various angle conditions and various properties we discussed for ellipses also hold true for parabolas too!
Here is a figure with all three angle properties. Convince yourself that all marked pairs of angles are the same.

$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(80); import graph; real f(real x) { return x*x; } path el = graph(f, -1.2, 1.2); pair F1 = (0, 0.25); pair D1 = (-1.4, -0.25), D2 = (1.4, -0.25); path d = D1--D2; draw(el, fuchsia); draw(d, fuchsia); real a = 20, b = 95; pair A = point(el,a), B = point(el,b); pair P = extension(A+dir(el,a), A, B, B+dir(el, b)); pair P0 = 1.4*F1 - 0.4*P; pair Af = foot(A,D1,D2), Bf = foot(B, D1, D2), Ff = foot(F1, D1, D2), Pf = foot(P, D1, D2); draw(A--Af, dashed); draw(P--Pf, dashed); draw(B--Bf, dashed); draw(A--P--B, royalblue); draw(A--F1--B, orange); draw(P--P0, brown); draw(anglemark(P,A,F1), brown); draw(anglemark(P,B,Bf), brown); draw(anglemark(P0,F1,A), springgreen); draw(anglemark(B,F1,P0), springgreen); draw(anglemark(F1,P,A), fuchsia); draw(anglemark(B,P,Pf), fuchsia); dot("$F_1$", F1, N); dot("$P$",P, dir(P)); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); [/asy]$

In fact, since a parabola in some sense is a very special ellipse, some additional properties are true too! [and some previously stated properties become even nicer]
Let $X, Y, Z$ be arbitrary points on some parabola with focus $F_1$ , and directrix $l$ , and let the tangents create some triangle $ABC$ . For convenience, let the point at infinity along line perpendicular to $l$ be $F_2$ . Remember that $F_1$ is the isogonal conjugate of $F_2$ in triangle $ABC$ ? Since in a parabola $F_2$ is at infinity, $F_1ABC$ are concyclic! Further, by Simson line, the reflections of F_1 across $AB, BC, CA$ and the orthocenter of $ABC$ are collinear. Since by optical property and definition of a parabola, the first three points lie on the directrix, we see that the orthocenter of $ABC$ lies on the directrix.

$[asy] defaultpen(fontsize(10pt)); import math; import olympiad; unitsize(80); import graph; real f(real x) { return x*x; } path el = graph(f, -1.3, 1.3); pair F1 = (0, 0.25); pair D1 = (-1.5, -0.25), D2 = (1.5, -0.25); path d = D1--D2; draw(el, fuchsia); draw(d, fuchsia); real a = 55, b = 94, c = 10; pair X = point(el,a), Y = point(el,b), Z = point(el, c); pair A = extension(Y, dir(el, b)+Y, Z, dir(el, c) + Z); pair B = extension(Z, dir(el, c) + Z, X+dir(el, a), X); pair C = extension(X, X+dir(el, a), Y, Y+dir(el, b)); draw(circumcircle(A,B,C), brown); pair H = orthocenter(A,B,C); draw(A--foot(A,B,C),dotted); draw(B--foot(B,A,C),dotted); draw(C--foot(C,B,A),dotted); draw(Z--A--Y, royalblue); draw(B--C, royalblue); dot("$F_1$", F1, N); dot("$C$",C, dir(C)); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); dot("$Z$",Z, dir(Z)); dot("$X$", X, dir(X)); dot("$Y$", Y, dir(Y)); dot("$H$", H, dir(H)); [/asy]$

To be truthful, this topic isn't very relevant to olympiad geometry and readers will at best stumble across 3-4 questions which have a solution using the theory discussed here. I still think that the topic is quite fun and interesting though, hence the blog post.

To me, when I first saw all of this, it was surprising that angle conditions could be true in conics at all, since I used to feel that projective geometry was the only way of dealing with conics. There might be few applications of this ~~apart from maybe giving thirsty cats water in an optimal way~~, but it's still a pretty beautiful piece of math.
That said, it's not completely useless, and in the following post, I'll definitely showcase a few oly geo problems where knowing angle chasing in conics helps. (Including IMO 18/6!)

To end with, a couple of exercises/theorems on ellipses/parabolas that will lead into part 2. There are some fancy names in this part which I have not bothered to define, just look those up if necessary.

Show that any in-ellipse of a quadrilateral has its centre on the Newton-Gauss line
Hint
Consider the setup as part of a tilted plane, and project it onto a perpendicular plane to convert the ellipse into a circle. [Similar to how we proved the theorem involving the line through midpoints of parallel chords.]
Prove that the focus of the parabola tangent to four sides of a quadrilateral, is the quadrilateral's Miquel point.
Hint
Simply show that it lies on the corresponding 4 circles.
Prove that the directrix of a parabola tangent to four sides of a quadrilateral is the Gauss-Bodenmiller line.
Hint
4 orthocentres lie on the gauss-bodenmiller line. Find them.

This post has been edited 2 times. Last edited by p_square, Jun 13, 2021, 3:05 PM

geometry

ellipse

conic

Some Disguised Bi-partite Graphs

by p_square, May 23, 2019, 11:25 AM

This blog post will feature grids and a popular technique involving bipartite graphs to solve some grid related questions.

The main idea will be to treat every row and column of a grid as a vertex of a graph and join two vertices representing a row and a column by an edge depending on their intersection.

Since the exact technique is hard to rigourize in such a manner, I'll present a problem and its solution to convey the main idea.

IMO 1986/6 wrote:

Given a finite set of points in the plane, each with integer coordinates, is it always possible to color the points red or white so that for any straight line $L$ parallel to one of the coordinate axes the difference (in absolute value) between the numbers of white and red points on $L$ is not greater than $1$ ?

Let us reformulate the problem into a statement that involves a bipartite graph.
Let $U$ be the set of vertical lines passing through at least one point of the set.
Let $V$ be the set of horizontal lines passing through at least one point of the set.
Consider the bipartite graph $G$ with consisting of lines with the bipartition $U$ and $V$ .
Let two lines in $U$ and $V$ be neighbours if they intersect at a point in the given set of points.
We wish to colour the edges in such a manner that the differences between red edge degree an white edge degree of a vertex is at most $1$ .

First of all, note that all cycles have even length.
What this means, is that we can remove an arbitrary cycle by colouring its edges red and white in an alternating manner.

We are left with a forest.
Consider any tree of the forest. Give it an arbitrary root.
It can be seen inductively that given any tree rooted at $r$ and a weight $w$ which is either $-1,0$ or $1$ we can colour the edges of the tree red and white in such a way that
number of red edges to $r$ - number of white edges to $r \in \{w-1, w, w+1\}$
(This is because we can first make sure that the root is happy

).
for every other vertice v, the difference between red and white edges is in $\{-1, 0, 1\}$ . \blacksquare

The next example in store is from PSE.

Infected Checkerboard Variant wrote:

There are $14$ bacteria on a checkerboard. If in a 2x2 sub-board, 3 cells are infected, the 4th cell gets infected from the next second. Infected cells remain infected. Is it possible that eventually the whole checkerboard gets infected?

~~Note that there are finitely many possibilities for the initial configuration of bacteria. This reduces the problem to a simple application of Govind's lemma~~

The solution provided in the link is quite ingenious and quite hard to come up with. Here is a more natural way to solve the problem.
Create a bipartite graph whose vertices are rows and columns of the chessboard and join two vertices by an edge iff they intersect at an infected cell.
Since there are only 14 edges, observe that the graph is disconnected.
Every second, we add some edge to the graph.
However observe that if two vertices were in different components, we cannot add an edge joining them! Whenever we add an edge between two vertices, there must have been a path of length 3 connecting these 2 vertices.
Since initially our graph was disconnected, it will stay disconnected forever; it can never become a complete bipartite graph.. \blacksquare

For the informatics variant and a minor generalisation, check here
pro yaar god yaar. Found white text yaar
While grid bipartition did come useful when solving the previous two questions, it's true power was not revealed.
Grid bipartition can let us turn all of the powerful theorems on graphs quickly to our advantage just by reformulating the question slightly.
It isn't hard to come up with questions like this.
For example (mine)

Tweaked Konig's wrote:

Some stones were places in a rectangular grid. Let $n$ be the smallest natural number such that given any $n+1$ stones, some two are either in the same row or same column. In one step, Petya removes all stones in row or column. Prove that the minimum number of steps required by Petya to remove all the stones is $n$ .

Another example (again mine)

Tweaked edge coloring wrote:

Some rooks were placed on a $n \times n$ ~~chess~~board, such that no row or column contained more than $m$ rooks. Prove that we can assign each rook one of $m$ colours such that no two rooks of the same color attack each other (For this problem, assume that rooks can attack over other rooks)

___________________________________________________________________
These grid based questions also combine well with the study of matching's in graph theory.

An example can be seen in this question here.

AoPS post wrote:

Some cells of a rectangular table with $n$ rows and $m$ columns ( $n<m$ ) is filled with stones such that there is at least $1$ stone in any column. Prove that there is a stone such that the number stones of row has it greater than the number stones of column has it.

Let the columns and rows represent vertices of a bipartite graph $G(V,E)$ with vertices $V=X\cup Y$ and $|X|<|Y|$ . The edge $\{x_i,y_j\}\in E$ iff there is a stone at the intersection of the $i^{\text{th}}$ row and $j^{\text{th}}$ column. Notice that the degree of a vertex in $X$ or $Y$ is the number of stones in that row or column respectively. We need to show that there exists an edge $\{x_i,y_j\}$ such that $d(x_i)>d(y_j)$ .

Assume the contrary and consider the counter example that minimises $|X|+|Y|$ . If $\{x_i,y_j\} \in E$ then $d(x_i) \le d(y_j)$ . We can assume $G$ is connected else we would be done by the minimality of our counter example. We will show that there is a matching of $X$ onto $Y$ . (that is, a set of $|X|$ edges, such that each vertex in $X$ is adjacent with exactly one edge).

Suppose we have a matching, $M$ with maximum number of edges. If the matching is not complete from $X\to Y$ , then $X\backslash M$ and $Y\backslash M$ are non-empty. Suppose $y_1 \in Y\backslash M$ , by the condition, $y_1$ must be adjacent to some other vertex in $x_1\in X$ . If $x_1\in X\backslash M$ we're done. Otherwise $x_1\in M$ , let $y_2$ be the corresponding edge of $x_1$ in $M$ . We see that $x_1$ has degree at least $2$ , so $y_2$ has degree at least $2$ , by the condition, so $y_2$ is adjacent to another vertex $x_2$ .

We continue in the manner. Since $G$ is finite and connected we must eventually reach a vertex $x_n \in X\backslash M$ . We can assume the path $y_1 \to x_n$ passes each vertex only once, else we contract any closed loop. Since the path is odd, say length $2m+1$ , there are exactly $m$ edges on the path that are in $M$ . Then if we delete those edges we are left with $m+1$ disjoint edges; that is, another matching with more edges. this contradicts the maximality of $M$ . It follows that we can find a complete matching $X\to Y$

Now each edge $\{x_i,y_j\}\in M$ satisfies $d(x_i)\le d(y_j)$ . But since $|X| < |Y|$ there is some $y\in Y\backslash M$ , and $d(y)\ge 1$ . Hence $\sum_{x\in X} d(x) < \sum_{y\in Y} d(y)$ , but this is absurd. So there is no counter example, and we're done.
[Credits of the solution to Ocha]

Hall's marriage lemma (put simply without symbols) states that in a bipartite graph, iff for every subset of vertices which are of the same colour, the size of the set that consists of ala their neighbours is greater than the original size of the set, then there is a perfect matching on the graph.
Hall's marriage lemma (put simply with symbols) states that in a graph $G=(V,E)$ with bipartition $A,B$ $\forall S \subset A$ or $S \subset B, |N(S)|>|S| \Rightarrow \exists$ a perfect matching.

This too is a formidable tool in the powerful arsenal of grid bipartition. India TST 2017/1/3 falls prey to this.

India TST 2017/1/3 wrote:

Let $n \ge 1$ be a positive integer. An $n \times n$ matrix is called good if each entry is a non-negative integer, the sum of entries in each row and each column is equal. A permutation matrix is an $n \times n$ matrix consisting of $n$ ones and $n(n-1)$ zeroes such that each row and each column has exactly one non-zero entry.

Prove that any good matrix is a sum of finitely many permutation matrices.

We will induct on the common sum of all rows/columns.
Define the bipartite multi(!)-graph G in a manner similar to the start of every problem ever in this post. [join with size of intersection]
Given any $k$ rows/columns $km$ edges emanate and since each column/row swallows at most $m$ , we see that by Hall's matching thm. a perfect matching exists.

The last example [again delving into Hall's thm] is RMM 2017/5.

RMM 2017/5 wrote:

Fix an integer $n \geq 2$ . An $n\times n$ sieve is an $n\times n$ array with $n$ cells removed so that exactly one cell is removed from every row and every column. A stick is a $1\times k$ or $k\times 1$ array for any positive integer $k$ . For any sieve $A$ , let $m(A)$ be the minimal number of sticks required to partition $A$ . Find all possible values of $m(A)$ , as $A$ varies over all possible $n\times n$ sieves.

The answer as one learns after drawing a lot of sieves is $2n - 2$ .
The construction for $2n-2$ is easy, irrelevant and left to the reader as an exercise. The interesting part is the proof for minimality..
There are easier 'local' proofs where one can delete a row or column but we present a better, more elegant proof ~~no, I'm not biased at all~~.

~~Don't~~ Create a bipartite graph ~~for once~~.
Let $U$ be the set of $2n-2$ sticks that are either to the left of a removed cell (and stretch till the left edge) or to the right (and stretch till the end of a removed cell) of a removed cell.
Let $V$ be the set of $2n-2$ sticks that are either above a removed cell (and stretch till he top edge) or below a removed cell (and stretch till the bottom edge).
Connect a pair of vertices in $U,V$ with an edge if they intersect.

Each edge corresponds to an unblocked cell.
We will now demonstrate Hall's criterion to show that perfect matching exists between vertices in $U,V$ .
This will finish the problem as then select the $2n-2$ cells that correspond to edges of the perfect matching. No pair of these $2n-2$ cells can lie on the same stick.
For any $m \le n$ and $m$ vertices in $U$ , there must be some $x$ sticks that terminate at the right edge of the $n \times n$ grid and $m-x$ sticks terminating at the left edge.
Thus, the $(m-x)^{th}$ leftmost columns each must have a stick in $V$ that intersects with the largest of the $m-x$ sticks terminating at the left edge.
Similarly, each of the $x^{th}$ rightmost columns each must have a stick in $V$ that intersects wit the largest of the $x$ sticks terminating at the right edge.
Thus, there must be at least $m$ vertices in $V$ that are connected to at least one of the vertices in $U$ .

For any $m \ge n$ , and any subset of $U$ with size $m$ , it is not hard to see that the subset of $V$ in which each vertex is connected to at least one of the $m$ sticks in $U$ has size greater than $m$ by looking at the vertices in $U$ with which the compliment of this subset of $V$ and doing the same this as the case when $m < n$ ~~and creating a record for the longest and most confusing sentence~~.

___________________________________________________________________
Practice Problems:

EGMO 2013/3
Let $m$ be a positive integer. Consider a $4m\times 4m$ array of square unit cells. Two different cells are related to each other if they are in either the same row or in the same column.No cell is related to itself.Some cells are coloured blue, such that every cell is related to at lest two blue cells.Determine the minimum number of blue cells.
Kazakhstan 2012 9.6
The cell of a $(2m + 1) \times (2n + 1)$ board are painted in two colors - white and black. The unit cell of a row (column) is called dominant on the row (the column) if more than half of the cells that row (column) have the same color as this cell. Prove that at least $m + n - 1$ cells on the board are dominant in both their row and column.
Belarusian National Olympiad 2007/3
Given a $2n \times 2m$ table $(m,n \in \mathbb{N})$ with one of two signs ”+” or ”-” in each of its cells. A union of all the cells of some row and some column is called a cross. The cell on the intersection of this row and this column is called the center of the cross. The following procedure we call a transformation of the table: we mark all cells which contain ”−” and then, in turn, we replace the signs in all cells of the crosses which centers are marked by the opposite signs. (It is easy to see that the order of the choice of the crosses doesn’t matter.) We call a table attainable if it can be obtained from some table applying such transformations one time.
Find the number of all attainable tables.

I actually haven't done the third problem, so don't blame me if there is no solution :oops:

___________________________________________________________________

PS I recently read a book 'All the Light We Cannot See' by 'Anthony Doerr' which turned out to be really good. People should try it if they can. To provide some motivation: It won the Pulitzer Prize for fiction in 2015.

This post has been edited 5 times. Last edited by p_square, May 23, 2019, 1:23 PM

graphs

combinatorics

An ode to generalise-ation

by p_square, Dec 19, 2018, 2:56 PM

Today's I'll attempt to discuss ~~ELMO 2018/2~~ the merits and demerits of attempting to generalise questions in order to prove their statements. Generlisation is a often very useful and perhaps counter-intuitively, many problems are actually harder to solve than a more general form of their statements.
Typical examples for this include induction style arguments and splitting one variable into 2. You'll get what this means in the example. A good example for this is the following problem.

*Note: I don't precisely remember the source, so anyone who does is requested to please comment below.

Unknown source; yagami1728 wrote:

There are $n^2$ lights of some $n$ colours (not necessarily $n$ of each colour). Prove that they can be arranged on $n$ christmas trees with $n$ lights per christmas tree, such that no tree has lights of three or more different types.

The more general version is this:

generalised yagami1728 wrote:

There are $nm$ lights of some $n$ colours. Prove they can be arranged on $n$ christmas trees such that each tree has $m$ lights and no tree has ornaments of three or more different colours.

For any fixed constant $m$ , this version can be solved via induction on $n$ .

The base case, ( $n=1$ ) is easy to see.
Now, assume it is possible for some $n$ .
Given any set of ornaments of $n+1$ colours, there is a colour which appears at most $m$ times (call such a colour sparse) and another colour which appears at least $m$ times (call such a colour abundant).
We can use all lights of a sparse colour on a tree and use lights of an abundant colour to fill in the incomplete spots, such that the tree finally has $m$ ornaments.
Observe that this reduces to the $n$ case and we're done by induction. $\blacksquare$

Here is another example of a problem (albeit ~~a little~~ much harder) in which a more general version is easier to solve.

ISL 2017 C6 wrote:

Let $n > 1$ be a given integer. An $n \times n \times n$ cube is composed of $n^3$ unit cubes. Each unit cube is painted with one colour. For each $n \times n \times 1$ box consisting of $n^2$ unit cubes (in any of the three possible orientations), we consider the multi-set of colours present in that box. This way, we get $3n$ sets of colours, split into three groups according to the orientation.

It happens that for every set in any group, the same set appears in both of the other groups. Determine, in terms of $n$ , the maximal possible number of colours that are present.

~~Since I'm too lazy to type the solution again~~ Here is the official solution from v_enhance's post which can be found here

The answer turns out to be $\dfrac{n(n+1)(2n+1)}{6}$
There does exist a messy solution which does not strengthen the problem statement in any way. However, much more is revealed about the problem by a different inductive, elegant solution which also explains the identity $\dfrac{n(n+1)(2n+1)}{6} = \sum_{i=1}^n i^2$ .

The following modifications on the original problem do not change the solution

we allow cubes to be invisible (i.e. to not have any color).
we still require every plate $S$ to be present in all three directions, unless $S = \varnothing$ .

The base case $n = 1$ is easy. For the inductive step, unless the entire cube is invisible (and hence has no colors at all), we can take an $S$ -plate ( $S \neq \varnothing$ ). Now suppose delete three $S$ -plates (one in each direction), then turn all those colours which appeared anywhere in $S$ invisible. This resulting $(n-1) \times (n-1) \times (n-1)$ cube that still satisfies the conditions! Since $S$ had at most $n^2$ distinct colors in it, it follows that $f(n) \le n^2 + f(n-1)$ and so $f(n) \le \frac16 n(n+1)(2n+1)$ as desired.

We can construct an example where $\frac16 n(n+1)(2n+1)$ colours are used as follows

We add $n$ colors, 1 for each point $(i,i,i)$ .
We then add $3 \binom n2$ . For any $1 \le i < j \le n$ , we have three colors; one on $(i,j,j)$ and $(j,j,i)$ ; one on $(i,j,i)$ and $(j,i,j)$ ; and one on $(j,i,i)$ and $(i,j,j)$ .
Lastly, we add $2 \binom n3$ colors. For any $1 \le i < j < k \le n$ , we have two colors: one on $(i,j,k)$ , $(j,k,i)$ , and $(k,i,j)$ ; and one on $(k,j,i)$ , $(i,k,j)$ , and $(j,i,k)$ .

Both of these question display the advantages of generalising questions but this art is a fickle friend. Many a time has an innocent person been lured by these gifts and overlooked the obvious. Here is an example of such an occurrence with an extremely overkill proof of ELMO 2018/2.

The original question statement is this

ELMO 2018/2 wrote:

Consider infinite sequences $a_1,a_2,\dots$ of positive integers satisfying $a_1=1$ and $a_n \mid a_k+a_{k+1}+\dots+a_{k+n-1}$ for all positive integers $k$ and $n.$ For a given positive integer $m,$ find the maximum possible value of $a_{2m}.$

There is a simple proof which can be easily found, but what follows is what I was able to come up with. If someone still wants to go through the simple proof, ~~get out of my blog~~, check here
Also, please if possible, go through my proof and tell me if there are any mistakes.

Some notation:
Call a natural number $n$ important if $a_n > 1$ and call $n$ esteemed if $a_n = \sum_{i=1}^{n-1} a_i$

We first demonstrate a few preliminaries about these sequences

Fact $1$ : $a_{k + n} \equiv a_k \pmod {a_n}$
Proof: For, the proof observe that we have $a_n|a_k + a_{k+1} + ..... + a_{n+k-1}$ On the other hand, we also know $a_n|a_{k+1} + ..... + a_{n+k}$ Subtracting, we obtain $a_n|a_{n+k} - a_k$

By induction $a_{k + mn} \equiv a_k \pmod {a_n}$ and more specifically every multiple of an important number is important. $a_m | a_{mn}$

Also, it's worth noting that $a_xa_{x+1} \mid (a_1+a_2 \cdots + a_x)$
Since $a_{x+1} \equiv 1 \pmod {a_x}$ , we know that $a_x,a_{x+1}$ are coprime.
By the condition on $a$ ,
$a_x \mid a_1 + a_2+ \cdots +a_x$ $a_{x+1} \mid a_1 + a_2+ \cdots +a_x + a_{x+1} - a_{x+1}$
The sum of two important numbers is important
Assume $i,j$ are important and WLOG $a_i \ge a_j$
Simply observe that $a_{i+j} \equiv a_j \pmod {a_i}$ which finishes the proof.
By induction, the sum of any finite multiset of important numbers is important

We will now deliberate over something we call the characteristic of the sequence

If $k$ is the largest number that divides every important number, call $k$ as the characteristic of the sequence $a$ .
Symbolically, $\mathbb{C}(a) := max(k)$ where $k$ varies over the set of numbers that divide all important numbers.
As an exception, define $\mathbb{C}(a) = 0$ , $\forall x, a_x = 1$

We first show that every sufficiently large multiple of $\mathbb{C}(a)$ is important.
From our assumption that there is no natural number greater than $\mathbb{C}(a)$ that divides all important numbers, we observe that there is a finite set $S$ of important numbers whose greatest common divisor is $\mathbb{C}(a)$ . ( Suppose you have checked all the important numbers upto $M$ and the gcd is something like $k\mathbb{C}(a)$ , where $k$ is some positive integer greater than $1$ (if not, then we are done!). But we know that the gcd of all important number is $\mathbb{C}(a)$ , thus there must exist some important number(maybe humongous) which is not divisible by $k\mathbb{C}(a)$ . Thus we include those numbers in our set $S$ and after adding finitely many numbers we are done!)
We are now done, since the sum of a finite multiset of important numbers was important.

Call a sequence $a$ primitive if $a_{\mathbb{C}(a)} = 1$

We will now attempt to use some bounding arguments to figure out what all the primitive sequences are.
We'll first show that $a_{r+\mathbb{C}(a)} > 2a_{r}$ for sufficiently large important $r$ .
Note that $a_{2\mathbb{C}(a)} | 2\mathbb{C}(a) - 1$ , so $a_{2\mathbb{C}(a)} \ne 2$
To prove the claim, consider the following congruences
$a_{r+\mathbb{C}(a)} \equiv a_{\mathbb{C}(a)} \equiv 1 \pmod {a_r}$ $a_r \equiv a_{\mathbb{C}(a)} \equiv 1 \pmod {a_{r-\mathbb{C}(a)}}$ $a_{r+\mathbb{C}(a)}\equiv a_{2\mathbb{C}(a)}\not\equiv 2\pmod {a_{r-\mathbb{C}(a)}}$
These together imply the result.

We now show that every sufficiently large multiple of $\mathbb{C}(a)$ is esteemed in a primitive sequence.

Proof: Observe that
$a_{r+\mathbb{C}(a)}-\sum_{i=1}^{r+1-\mathbb{C}(a)}a_i<a_r-\sum_{i=1}^{r-1}a_i+\mathbb{C}(a)$
We now show that $\mathbb{C}(a) \ne 1$ . That is not every natural number can be important.
Assume to the contrary.
Taking $x$ to be sufficiently large, we see that.
$a_xa_{x+1} \mid a_1 + a_2+ \cdots +a_x$ $a_xa_{x+1} \le a_1 + a_2+ \cdots +a_x = a_{x+1}~~~(because~~x+1 ~~is~~ esteemed)$ This is a contradiction to our assumption that $\mathbb{C}(a) = 1$ .

Now, we have developed enough machinery to determine all possible primitive sequences.

In any primitive sequences, since every sufficiently large multiple of $\mathbb{C}(a)$ is esteemed, if $r$ is sufficiently large $a_{r\mathbb{C}(a)} > \mathbb{C}(a)$
$a_{(r+1)\mathbb{C}(a)} = 2a_{r\mathbb{C}(a)} + \mathbb{C}(a) - 1$ $\mathbb{C}(a) - 1 \equiv 1 \pmod {a_{r\mathbb{C}(a)}}$ $\mathbb{C}(a) \equiv 2 \pmod {a_{r\mathbb{C}(a)}}$
Thus, $\mathbb{C}(a) = 2$
There is only 1 primitive sequence which is defined by
$a_x := \begin{cases} 1 & when~ x\equiv 1 \pmod 2\\ 2^{\frac{x}{2}} - 1 & when~x\equiv0\pmod2 \\ \end{cases}$ We know that $\exists$ $r, y$ ( $r$ is sufficiently large, $y = a_{2r}+1$ ) such that
$a_x := \begin{cases} 1& when~x=2m+1\\ y2^m-1&where~ x=2r+2m\\ \end{cases}$
Observe the bound $a_{2m} < 2^{2m}$ , which can be proved by induction.
${2} a_{2m} \equiv a_{2r+4m} \pmod {a_{2r+2m}}$ $a_{2m} \equiv y2^2m - 1 \equiv 2^{m}-1 \pmod {y2^m - 1}$
$a_{2r+2m} > a_{2m}$ yields $y = 1$ and $a_{2m} = 2^m - 1$ .

And now, we have enough machinery to figure out all possibilities for such sequences.
We will show that ll sequences fall into the following three types.
$a_x := 1$ $a_x := \begin{cases} k\mathbb{C}(a) & a_x = m\\ \text{else} & a_x = 1\\ \end{cases}$ where $m \mid \mathbb{C}(a) - 1$ , or
$a_x := \begin{cases} k\mathbb{C}(a) & a_x = (2^k-1)(\mathbb{C}(a)-1)\\ \text{else} & a_x = 1\\ \end{cases}$
We will prove this using infinite descent.
Consider a sequence $a$ not of this type with minimal characteristic $\mathbb{C}(a)$ . We'll find a sequence $b$ not of this type with smaller characteristic.
Clearly $y = a_{\mathbb{C}(a)} > 1$ , as the only primitive sequence was of this type.
Every term with an important index in $a$ is divisible by $y$ .
Also, clearly $y=a_{\mathbb{C}(a)}\mid \mathbb{C}(a)-1$
Define $b$ by
$b_x = \begin{cases} k\left(\frac{\mathbb{C}(a)-1}{y}+1\right) & b_x = a_{k\mathbb{C}(a)}\\ \text{else} & b_x = 1\\ \end{cases}$ It is easy to verify that $b$ also does not belong to the $3$ types and $\mathbb{C}(b) < \mathbb{C}(a)$

This post has been edited 6 times. Last edited by p_square, Jul 2, 2022, 12:52 PM

Diagrams

by p_square, Sep 10, 2018, 10:21 AM

These are the 'complete' diagrams of the $A$ -HM point and the inverted $A$ -HM point.

1) The $A$ -HM point
$[asy] defaultpen(fontsize(9pt)); import math; import olympiad; unitsize(30); pair Z,A,B,C,D,E,F,H,T,P,Q,X,M,N,O,L,Y,R; A=(6,4); B=(7,0); C=(11,0); M=(B+C)/2; D=foot(A,B,C); E=foot(B,C,A); F=foot(C,A,B); H=orthocenter(A,B,C); dot(H); X=foot(H,A,M); P=(A+H)/2; T=orthocenter(A,P,M); Q=foot(P,A,M); O=circumcenter(A,B,C); L=circumcenter(H,B,C); N=orthocenter(B,C,X); Z=foot(M,A,T); Y = extension(F,E,C,B); draw(B--A--C--B); draw(C--F, heavygreen); draw(E--H, heavygreen); draw(A--H, heavygreen); draw(A--M, heavygreen); draw(C--H, heavygreen); draw(D--B--F, heavygreen); draw(A--T--Q, red); draw(M--Z, red); draw(A--D, dashed+red); draw(T--X--L--M,blue); draw(L--P, blue); draw(T--P, dashed+blue); draw(T--B, red); draw(F--M--E,dotted+purple); draw(E--F--Y--X--H, orange); draw(circumcircle(A,B,C),dashed+lightred); draw(circumcircle(H,B,C),blue); draw(circumcircle(L,M,T),blue); draw(circumcircle(X, H, D),dotted+lightred); draw(circumcircle(X, B, F),dotted+lightred); draw(circumcircle(X, C, E),dotted+lightred); draw(circumcircle(A,X,C),heavycyan); draw(circumcircle(A,X,B),heavycyan); draw(circle(T,4.4),orange); draw(circumcircle(A,E,F),purple); draw(circumcircle(Y,X,B),orange); draw(circumcircle(Y,X,C),orange); dot("$A$",A, dir(150)); dot("$B$",B,dir(215)); dot("$C$",C, dir(270)); dot("$X$",X,dir(30)); dot("$M$",M,dir(60)); dot("$T$",T,dir(150)); dot("$D$",D,dir(225)); dot("$E$",E,dir(0)); dot("$F$",F,dir(270)); dot("$P$",P,dir(45)); dot("$Q$",Q,dir(45)); dot("$O_A$",L,dir(310)); dot("$H$",H,dir(225)); dot("$Y$",Y,dir(300)); [/asy]$

2)The configuration inverted about the $A$ -HM point.
$[asy] defaultpen(fontsize(9pt)); import math; import olympiad; unitsize(50); pair A,B,C,M,X,O,x1,x2,x3,E,F,H,x4,x5,x6,x7,D,x8,x9,Y,x10,T,P,Oa,x11,Y; B=dir(150); X=dir(100); C=dir(30); O=circumcenter(X,B,C); A=(-1/((B+C)/2-O))+O; x1=orthocenter(X,B,C); x2=foot(x1,X,((B+C)/2)); x3 = foot(x2,B,C); M = 2*x3-x2; x4=foot(A,M,C); E=2*x4-C; x5=foot(A,M,B); F=2*x5-B; H=extension(F,E,B,C); x6 = foot(O,M,H); D = 2*x6-M; x7 = foot(O,X,H); Y = 2*x7 - X; x10 = foot(X,B,C); Oa = 2*x10 - X; x8 = foot(X,E,F); P=2*x8-X; x9 = foot(O,M,P); T=2*x9-M; x11=foot(O,X,H); Y=2*x11-X; draw(M--A--B--C--A); draw(E--M--F--H--C); draw(M--H, red); draw(C--A--B,heavygreen); draw(F--E--C--B--F,heavygreen); draw(M--P,purple); draw(B--E,blue); draw(C--F,blue); draw(A--D,blue); draw(X--H,blue); draw(circumcircle(X,C,B)); draw(circumcircle(E,F,B),heavygreen); draw(circumcircle(A,X,H),red); draw(circumcircle(F,X,C),dotted+heavycyan); draw(circumcircle(E,X,B),dotted+heavycyan); draw(circumcircle(A,X,C),dashed+orange);draw(circumcircle(A,X,B),dashed+orange); dot("$A$",A,dir(90)); dot("$B$",B,dir(200)); dot("$C$",C,dir(270)); dot("$X$",X,dir(180)); dot("$M$",M,dir(270)); dot("$E$",E,dir(20)); dot("$F$",F,dir(270));dot("$H$",H);dot("$D$",D,dir(330));dot("$T$",T,dir(125)); dot("$P$",P,dir(90)); dot("$O_A$",Oa); dot("$Y$",Y,dir(90)); [/asy]$

HM-Point

The A-Humpty point; Inversion

by p_square, Sep 9, 2018, 3:29 PM

It isn't a well known saying, that "When in doubt, invert". And there is a reason for that. It is not recommended to try and invert around points randomly without regard for rhyme or reason.
However it is generally a good idea to invert around points through which a lot of circles pass.

Inversion possesses the power to turn all these cruel complicated circles into simple lines.

Looking at the complete diagram of the $A$ -HM point, it can be seen that many circles pass through the $A$ -HM point. In this blog post I will invert around the $A$ -HM point with arbitrary radius. This turns out even better than expected.

Also, since I am not comfortable inverting the large complicated diagram at once, I shall invert it in many stages.

Stage 1; $A,B,C,X,M$
Take $XBC$ as an arbitrary triangle. We see that $A$ is the intersection of tangents from $B,C$ to the circumcircle of $XBC$ .
$M$ is the second intersection point of $AM$ and the circumcircle of $XBC$ .
Things look quite good at this point. We have a harmonic quadrilateral, with a tangent intersection point marked.
$[asy] defaultpen(fontsize(9pt)); import olympiad; unitsize(50); pair A,B,C,M,X,O,x1,x2,x3; B=(-0.766,0.643); X=(-0.174,0.985); C=(0.766,0.643); O=circumcenter(X,B,C); A=(-1/((B+C)/2-O))+O; x1=orthocenter(X,B,C); x2=foot(x1,X,((B+C)/2)); x3 = foot(x2,B,C); M = 2*x3-x2; draw(M--A--B--C--A); draw(circumcircle(X,C,B)); dot("$A$",A,dir(90)); dot("$B$",B,dir(150)); dot("$C$",C,dir(60)); dot("$X$",X,dir(90)); dot("$M$",M,dir(270)); [/asy]$

The next stage will be dealing with $H$ . We definitely cannot define it in the usual manner as the orthocentre of triangle $ABC$ . All those perpendicular lines will become orthogonal circles, a not-so-nice constraint.

Stage 2; $E,F,H$
The thing to notice over here, is that $E,F$ are much better characterized as lying on circles $XCM, XBM$ in the original figure than foot of altitudes from $B,C$ to $AC, AB$ .

$E$ and $F$ will simply become the intersection points of $CM, BM$ with circle $XAC, XAB$ .

Now, instead of thinking of $H$ as $BE$ intersection $CF$ in the original figure, we can simply remember property 2.
$H$ goes to $BC$ intersection $AEF$ .

We now have enough points for interesting things to start happening in the figure and indeed they do

$[asy] defaultpen(fontsize(9pt)); import math; import olympiad; unitsize(50); pair A,B,C,M,X,O,x1,x2,x3,E,F,H,x4,x5; B=dir(150); X=dir(100); C=dir(30); O=circumcenter(X,B,C); A=(-1/((B+C)/2-O))+O; x1=orthocenter(X,B,C); x2=foot(x1,X,((B+C)/2)); x3 = foot(x2,B,C); M = 2*x3-x2; x4=foot(A,M,C); E=2*x4-C; x5=foot(A,M,B); F=2*x5-B; H=extension(F,E,B,C); draw(M--A--B--C--A); draw(E--M--F--H--C); draw(C--A--B,heavygreen); draw(F--E--C--B--F,heavygreen); draw(circumcircle(X,C,B)); draw(circumcircle(A,X,B),blue); draw(circumcircle(A,X,C),blue); draw(circumcircle(E,F,B), heavygreen); dot("$A$",A,dir(90)); dot("$B$",B,dir(150)); dot("$C$",C,dir(60)); dot("$X$",X,dir(90)); dot("$M$",M,dir(270)); dot("$E$",E); dot("$F$",F);dot("$H$",H); [/asy]$

Interesting Property wrote:

$A$ is the center of a circle passing through $B,C,E,F$ .

We can prove this by simple angle chasing.
$\angle AEC = 180 - \angle AXC = \angle MXC = \angle CBM = 180 - \angle ACM = \angle ACE$ .
We have $AF = AB = AC = AE$ .

Also, we can redefine $E,F$ as the points on $MC,MB$ such that $AE = AB = AC = AF.$

This diagram is basically USAMO 2007/2

Stage 3: $D$
$D$ clearly becomes the intersection of circle $XBC$ and line $MH$ . $D$ also lies on the circle $AXH$ .
Observe that $\angle ADM = \angle ADH = \angle AXH = 90$ .
$[asy] defaultpen(fontsize(9pt)); import math; import olympiad; unitsize(50); pair A,B,C,M,X,O,x1,x2,x3,E,F,H,x4,x5,x6,x7,D; B=dir(150); X=dir(100); C=dir(30); O=circumcenter(X,B,C); A=(-1/((B+C)/2-O))+O; x1=orthocenter(X,B,C); x2=foot(x1,X,((B+C)/2)); x3 = foot(x2,B,C); M = 2*x3-x2; x4=foot(A,M,C); E=2*x4-C; x5=foot(A,M,B); F=2*x5-B; H=extension(F,E,B,C); x6 = foot(O,M,H); D = 2*x6-M; draw(M--A--B--C--A); draw(E--M--F--H--C); draw(M--H, red); draw(C--A--B,heavygreen); draw(F--E--C--B--F,heavygreen); draw(circumcircle(X,C,B)); draw(circumcircle(E,F,B),heavygreen); draw(circumcircle(A,X,H),red); draw(circumcircle(F,X,C),dashed+heavycyan); draw(circumcircle(E,X,B),dashed+heavycyan); draw(circumcircle(A,X,C),dashed+orange);draw(circumcircle(A,X,B),dashed+orange); dot("$A$",A,dir(90)); dot("$B$",B,dir(150)); dot("$C$",C,dir(60)); dot("$X$",X,dir(90)); dot("$M$",M,dir(270)); dot("$E$",E); dot("$F$",F);dot("$H$",H);dot("$D$",D); [/asy]$

From the usual definitions of $E,F,H,D$ we see that circle $FXCH$ is orthogonal to circle $ABEX$ , circle $EXBH$ is orthogonal to circle $ACEX$ and circle $AHDX$ is orthogonal to $XBC$ .

Stage 4: $T,P,O_A$ .
$O_A$ being the circumcentre of $XBC$ clearly becomes $X$ reflected across $BC$ ~~or the M-Humpty point of MBC~~.
After inversion, $BCXT$ is an isosceles trapezium.

$P$ was the circumcenter of $AEFHX$ , so it becomes $X$ reflected across $AEFH$ .

$[asy] defaultpen(fontsize(9pt)); import math; import olympiad; unitsize(50); pair A,B,C,M,X,O,x1,x2,x3,E,F,H,x4,x5,x6,x7,D,T,P,Oa,x8,x9; B=dir(150); X=dir(100); C=dir(30); O=circumcenter(X,B,C); A=(-1/((B+C)/2-O))+O; x1=orthocenter(X,B,C); x2=foot(x1,X,((B+C)/2)); x3 = foot(x2,B,C); M = 2*x3-x2; x4=foot(A,M,C); E=2*x4-C; x5=foot(A,M,B); F=2*x5-B; H=extension(F,E,B,C); x6 = foot(O,M,H); D = 2*x6-M; x7 = foot(X,B,C); Oa = 2*x7 - X; x8 = foot(X,E,F); P=2*x8-X; x9 = foot(O,M,P); T=2*x9-M; draw(M--A--B--C--A); draw(E--M--F--H--C); draw(M--H, red); draw(C--A--B,heavygreen); draw(F--E--C--B--F,heavygreen); draw(M--P,orange); draw(circumcircle(X,C,B)); draw(circumcircle(E,F,B),heavygreen); draw(circumcircle(A,X,H),red); dot("$A$",A,dir(90)); dot("$B$",B,dir(150)); dot("$C$",C,dir(60)); dot("$X$",X,dir(90)); dot("$M$",M,dir(270)); dot("$E$",E); dot("$F$",F);dot("$H$",H);dot("$D$",D);dot("$T$",T);dot("$P$",P);dot("$O_a$",Oa); [/asy]$

An interesting thing to note is that the $A$ -HM point configuration is partially self-inversive.

Since $A$ is the midpoint of $EF$ and $AB=AC=AE=AF$ , we see that $EB$ and $FC$ are perpendiculars to $ME, MF$ .
This further implies that $X$ is the $M$ -HM point of triangle $MEF$ .

For now, let us hop back to original diagram

We will prove a quick result or $2$ that were not touched upon in the previous entry.

Result $1$ : $HX, BC$ and $EF$ concur (Say at $Y$ ).
The simplest way to prove this is to note that $EFHX, EFDM, MDHX$ are all circles. Since we know that radical axis of $3$ circles taken pairwise concur at a point, we are done.

$[asy] defaultpen(fontsize(9pt)); import olympiad; unitsize(30); pair A,B,C,D,E,F,H,M,X,Y; B=(0,0); A=(1,4); C=(5,0); D=foot(A,B,C); E=foot(B,A,C); F=foot(C,A,B); H=orthocenter(A,B,C); M=(B+C)/2; X = foot(H,A,M); Y=extension(E,F,X,H); draw(D--A--B--C--A--M); draw(E--Y--X, blue); draw(C--F); draw(B--E); draw(Y--C,blue); draw(circumcircle(A,E,F),heavygreen); draw(circumcircle(D,E,F),heavygreen); draw(circumcircle(M,H,X),heavygreen); dot("$A$",A,dir(90)); dot("$B$",B,dir(150)); dot("$C$",C,dir(60)); dot("$D$",D,dir(250)); dot("$E$",E,dir(60)); dot("$F$",F,dir(210)); dot("$H$",H,dir(150)); dot("$M$",M,dir(300)); dot("$X$",X,dir(330)); dot("$Y$",Y); [/asy]$

Result $2$ : $X$ is the Miquel point of quadrilateral $BEFC$ (Yes, that order).
The proof of this is extremely short.
Simply note that since $BE, CF$ intersect at $H$ , and as we know, $EFHX$ and $BCHX$ are cyclic.
This further implies that $YEXC$ and $YFXB$ are cyclic.

$[asy] defaultpen(fontsize(9pt)); import olympiad; unitsize(30); pair A,B,C,D,E,F,H,M,X,Y; B=(0,0); A=(1,4); C=(5,0); D=foot(A,B,C); E=foot(B,A,C); F=foot(C,A,B); H=orthocenter(A,B,C); M=(B+C)/2; X = foot(H,A,M); Y=extension(E,F,X,H); draw(D--A--B--C--A--M); draw(E--Y--X, orange); draw(Y--C,orange); draw(B--E--F--C--B, heavygreen); draw(circumcircle(A,E,F),blue); draw(circumcircle(B,H,C),blue); draw(circumcircle(Y,B,X),heavycyan); draw(circumcircle(Y,C,X),heavycyan); dot("$A$",A,dir(90)); dot("$B$",B,dir(150)); dot("$C$",C,dir(60)); dot("$D$",D,dir(250)); dot("$E$",E,dir(60)); dot("$F$",F,dir(210)); dot("$H$",H,dir(150)); dot("$M$",M,dir(300)); dot("$X$",X,dir(330)); dot("$Y$",Y); [/asy]$

These two are actually well worth adding to our original figure.

These $2$ facts shall prove to be neat in the inverted diagram. In fact $Y$ plays a very important role.
Circles $XBC$ , $XEF$ , meet at the points on $XH$ . i.e. $XH$ is the radical axis of these two circles.
$Y$ is the orthocentre of $MEF$ .

$[asy] defaultpen(fontsize(9pt)); import math; import olympiad; unitsize(50); pair A,B,C,M,X,O,x1,x2,x3,E,F,H,x4,x5,x6,x7,D,x8,x9,Y,x10,T,P,Oa,x11,Y; B=dir(150); X=dir(100); C=dir(30); O=circumcenter(X,B,C); A=(-1/((B+C)/2-O))+O; x1=orthocenter(X,B,C); x2=foot(x1,X,((B+C)/2)); x3 = foot(x2,B,C); M = 2*x3-x2; x4=foot(A,M,C); E=2*x4-C; x5=foot(A,M,B); F=2*x5-B; H=extension(F,E,B,C); x6 = foot(O,M,H); D = 2*x6-M; x7 = foot(O,X,H); Y = 2*x7 - X; x10 = foot(X,B,C); Oa = 2*x10 - X; x8 = foot(X,E,F); P=2*x8-X; x9 = foot(O,M,P); T=2*x9-M; x11=foot(O,X,H); Y=2*x11-X; draw(M--A--B--C--A); draw(E--M--F--H--C); draw(M--H, red); draw(C--A--B,heavygreen); draw(F--E--C--B--F,heavygreen); draw(B--E,blue); draw(C--F,blue); draw(A--D,blue); draw(X--H,blue); draw(circumcircle(X,C,B)); draw(circumcircle(E,F,B),heavygreen); draw(circumcircle(A,X,H),red); dot("$A$",A,dir(90)); dot("$B$",B,dir(150)); dot("$C$",C,dir(60)); dot("$X$",X,dir(90)); dot("$M$",M,dir(270)); dot("$E$",E); dot("$F$",F);dot("$H$",H);dot("$D$",D);dot("$Y$",Y); [/asy]$

Now, we are ready for the grand finale, Presenting IMO 2015 P3.
We invert at an HM point configuration to arrive at the solution.

IMO 2015/3 wrote:

Let $ABC$ be an acute triangle with $AB > AC$ . Let $\Gamma$ be its cirumcircle, $H$ its orthocenter, and $F$ the foot of the altitude from $A$ . Let $M$ be the midpoint of $BC$ . Let $Q$ be the point on $\Gamma$ such that $\angle HQA = 90^{\circ}$ and let $K$ be the point on $\Gamma$ such that $\angle HKQ = 90^{\circ}$ . Assume that the points $A$ , $B$ , $C$ , $K$ and $Q$ are all different and lie on $\Gamma$ in this order.

Prove that the circumcircles of triangles $KQH$ and $FKM$ are tangent to each other.

The diagram looks like this:
$[asy] defaultpen(fontsize(9pt)); import math; import olympiad; unitsize(70); pair A,B,C,H,O,Q,K,F,M,x1; A = dir(70); B = dir(210); C = dir(330); O = circumcenter(A, B, C); H = orthocenter(A, B, C); M =(B+C)/2; F = foot(A, B, C); Q=foot(A,M,H); K=OP(CP((H+Q)/2,H),circumcircle(A,B,C)); draw(A--B--C--A); draw(H--A--Q--H--K--Q, red); draw(A--M--H--F,blue); draw(circumcircle(A,B,C),heavygreen); draw(circumcircle(K,F,M),heavycyan); draw(circumcircle(K,Q,H),heavycyan); dot("$A$",A); dot("$B$",B); dot("$C$",C); dot("$H$",H); dot("$M$",M); dot("$F$",F); dot("$Q$",Q);dot("$K$",K); [/asy]$
~~Since I drew the diagram, I leave the proof as an exercise to the reader~~

First of all, observe that $A$ and $Q$ are the $H$ -HM point of triangle $HBC$ respectively.
Let us invert the figure about $Q$ .
After inversion, the diagram appears like this:

$[asy] defaultpen(fontsize(9pt)); import math; import olympiad; unitsize(50); pair A,B,C,M,X,O,x1,x2,x3,E,F,H,x4,x5,x6,x7,D,x8,x9,Y,W,K,x10,x11; B=dir(215); X=dir(160); C=dir(325); O=circumcenter(X,B,C); A=(-1/((B+C)/2-O))+O; x1=orthocenter(X,B,C); x2=foot(x1,X,((B+C)/2)); x3 = foot(x2,B,C); M = 2*x3-x2; x4=foot(A,M,C); E=2*x4-C; x5=foot(A,M,B); F=2*x5-B; x8 = -1*M; x9 = foot(O,x8,A); D = 2*x9-x8; x7 = (A-M)*dir(270)+A; K = extension(A,x7,B,C); x6 = foot(O,x8,K); W = 2*x6-x8; x10 = foot(O,D,K); Y = 2*x10-D; H = extension(D,M,C,B); draw(X--A--B--C--A); draw(H--D--A--K--H--A); draw(A--H--D, red); draw(X--A--K,blue); draw(circumcircle(X,C,B),heavygreen); dot("$H$",A); dot("$B$",B); dot("$C$",C); dot("$Q$",X); dot("$M$",M); dot("$F$",D); dot("$K$",K); dot("$A$",H); [/asy]$

Now, let us erase a few unimportant points that aren't doing much and add in our very own set of points

Define $W$ as the point diametrically opposite $M$ in circle $MBC$ .
We know that $\angle HFA = 90$ (Stage $3$ ). This means that $W,M,F$ are collinear.
We can get rid of $A$ by re-defining $F$ as the second point of intersection between $WH$ and circle $MBC$ .
Let $L$ be the second intersection of $WK$ with circle $MBC$ .
Let $Y$ be the second intersection of $FK$ with circle $MBC$ .
We can also erase $Q$ from the figure.

We are left with
$[asy] defaultpen(fontsize(9pt)); import math; import olympiad; unitsize(50); pair A,B,C,M,X,O,x1,x2,x3,E,F,H,x4,x5,x6,x7,D,x8,x9,Y,W,K,x10,x11; B=dir(215); X=dir(160); C=dir(325); O=circumcenter(X,B,C); A=(-1/((B+C)/2-O))+O; x1=orthocenter(X,B,C); x2=foot(x1,X,((B+C)/2)); x3 = foot(x2,B,C); M = 2*x3-x2; x4=foot(A,M,C); E=2*x4-C; x5=foot(A,M,B); F=2*x5-B; x8 = -1*M; x9 = foot(O,x8,A); D = 2*x9-x8; x7 = (A-M)*dir(270)+A; K = extension(A,x7,B,C); x6 = foot(O,x8,K); W = 2*x6-x8; x10 = foot(O,D,K); Y = 2*x10-D; draw(A--B--C--A--M--B--C--M); draw(A--W--M--A--K--A--x8, red); draw(x8--K--D--M, blue); draw(circumcircle(M,B,C),heavygreen); draw(circumcircle(A,K,M),heavycyan); dot("$H$",A); dot("$B$",B); dot("$C$",C); dot("$M$",M); dot("$F$",D); dot("$K$",K); dot("$W$",x8); dot("$L$",W); dot("$Y$",Y); [/asy]$
$(FW;BC) = (YL;BC) = -1$ implies that $H,Y,L$ are collinear.
Also, $\angle MLK = \angle MLW = 90 = \angle MHK$ . $\therefore M,L,K,H$ are cyclic
We end by noting that $\angle HKM = \angle HLM = \angle YLM = 180 - \angle YFM = 180 - \angle KFM$ .
This means that $HK$ is tangent to circle $MKF$ .

Note: IMO 2015 P3 is actually even easier to solve via inversion at $H$ which is the $Q-HM$ point of triangle $QBC$ . Readers are 'encouraged' to also try solving it that way.

Credits go to @anantmudgal09 for telling me that IMO 2015 P3 could be done via inversion.

This post has been edited 6 times. Last edited by p_square, Feb 25, 2019, 11:19 AM

HM-Point

geometry

The A-Humpty point; Preliminaries

by p_square, Aug 18, 2018, 12:15 PM

In this blog post I will discuss the intricacies of the $A$ -HM point. Hopefully, by the end, many of its mysteries will be thrown into light.

The $A$ -HM point has several nice properties: We will randomly pick one as it's definition and derive the rest.
Define the $A$ -HM point as the foot of perpendicular from the Orthocentre $H$ of $\triangle ABC$ to the $A$ -Median.

We will also henceforth denote the $A$ -HM point by $X$ .

Anyway,

p_square wrote:

Property 1: X is the foot of perpendicular from the Orthocentre $H$ of Triangle $ABC$ to the $A$ -Median.

Well, not exactly. But that's close enough.

Property 2: $BXHC$ is a cyclic quadrilateral
Proof:
$[asy] import olympiad; unitsize(30); pair A,B,C,D,E,F,H,M,X; B=(0,0); A=(1,4); C=(5,0); D=foot(A,B,C); E=foot(B,A,C); F=foot(C,A,B); H=orthocenter(A,B,C); M=(B+C)/2; X = foot(H,A,M); draw(D--A--B--C--A--M); draw(B--E); draw(C--F); draw(H--X); draw(circumcircle(A,E,F)); draw(circumcircle(D,E,F)); draw(circumcircle(B,H,C)); dot("$A$",A,dir(90)); dot("$B$",B,dir(150)); dot("$C$",C,dir(60)); dot("$D$",D,dir(250)); dot("$E$",E,dir(60)); dot("$F$",F,dir(210)); dot("$H$",H,dir(150)); dot("$M$",M,dir(300)); dot("$X$",X,dir(330)); [/asy]$

Let $AD$ , $BE$ and $CF$ be the altitudes of the triangle $ABC$ . Let $M$ be the midpoint of $BC$ .
Observe that $XHDM$ is cyclic.
We will invert at A with radius $= \sqrt AH*AD$ .
As a fortunate co-incedence, By Power of Point, $AF*AB = AH*AD = AX*AM = AE*AC$ . ~~Actually, this is the only reason we inverted.~~
What this tells us, is that during the inversion $B \leftrightarrow F, H \leftrightarrow D, X \leftrightarrow M, E \leftrightarrow C$ .
Before inversion, Points $FDMC$ were cyclic (Nine-point circle), and as it hath been foretold, that circles shall (usually) remain circles after inversion, so $BXHC$ are cyclic. $\blacksquare$

Property 3: $BDC$ is tangential to Circles $AXB, AXC$ .
Proof:
$[asy] import olympiad; unitsize(30); pair A,B,C,D,E,F,H,M,X; B=(0,0); A=(1,4); C=(5,0); D=foot(A,B,C); E=foot(B,A,C); F=foot(C,A,B); H=orthocenter(A,B,C); M=(B+C)/2; X = foot(H,A,M); draw(D--A--B--C--A--M); draw(B--E--M); draw(C--F--M); draw(H--X); draw(circumcircle(A,E,F)); draw(circumcircle(D,E,F)); draw(circumcircle(B,H,C)); draw(circumcircle(A,X,B)); draw(circumcircle(A,X,C)); dot("$A$",A,dir(90)); dot("$B$",B,dir(130)); dot("$C$",C,dir(60)); dot("$D$",D,dir(250)); dot("$E$",E,dir(60)); dot("$F$",F,dir(210)); dot("$H$",H,dir(130)); dot("$M$",M,dir(300)); dot("$X$",X,dir(330)); [/asy]$

If we continue to work in the inverted diagram, what I wrote translates to

p_square in a complicated manner wrote:

$ME$ , $MF$ are tangent to Circle $AEHF$

This is very well known and the proof is simple angle chasing. $\blacksquare$

Property 4: Let the tangent from $A$ to the circumcircle of $ABC$ meet $BC$ at $T$ . The orthocentre of $AMT$ is the midpoint of $AH$ .
At first this doesn't seem related to $X$ at all! But on re-reading the relationship hopefully becomes clear. Say $P$ is the midpoint of $AH$ and $Q$ is the foot of perpendicular from $T$ to $AM$ .

p_square almost wrote:

$TP \perp AM! TA = TX!$

$[asy] import olympiad; unitsize(30); pair A,B,C,H,T,M,P,X,Q; A=(6,4); B=(7,0); C=(11,0); M=(B+C)/2; H=orthocenter(A,B,C); X=foot(H,A,M); P=(A+H)/2; Q=(A+X)/2; T=orthocenter(A,P,M); draw(A--T--C--A); draw(B--A--M); draw(A--H); draw(T--Q); draw(H--X); draw(circumcircle(A,B,C)); dot("$A$",A,dir(150)); dot("$B$",B,dir(210)); dot("$C$",C,dir(90)); dot("$M$",M,dir(60)); dot("$X$",X,dir(60)); dot("$H$",H,dir(180)); dot("$T$",T,dir(150)); dot("$P$",P,dir(180)); dot("$Q$",Q,dir(270)); [/asy]$
Proof:
It is ~~not~~ very easy to see that $AP \perp MT$ . It is also well known that $MH || OA \perp AT$ .
So, $P$ is indeed the orthocentre of $AMT$ .
This further implies that $TP \perp AM$
The foot of perpndicular from $P to AM$ will be the midpoint of the foot of perpendicular from $H to AM$ . i.e. $AQ = QX$
This tells us that $T$ is on the perpendicular bisector of $AX$ or $TA = TX. \blacksquare$

Many people might recognise this as ELMO 2018/4 (I also used the same notation). Quite a few ELMO geometry questions become much simpler if one knows about the $A$ -HM point.

Property 5: If $ABCZ$ is a harmonic quadrilateral, then $X$ is the reflection of $Z$ across $BC$
Proof:
It isn't hard to see that the reflection of $Z$ across $BC$ lies on circle $BHC$ . ( $BZC = BHC$ )
Also $TZ = TA = TX$ . Ignoring configuration issues (which I ~~vehemently hate~~ generally dislike), we see that $X$ must be the reflection of $Z$ across $BC$ . $\blacksquare$

Property 6: $TX$ is tangent to circle $BHXC$
Proof:
$[asy] import olympiad; unitsize(30); pair A,B,C,H,T,M,P,X,Q; A=(6,4); B=(7,0); C=(11,0); M=(B+C)/2; H=orthocenter(A,B,C); X=foot(H,A,M); P=(A+H)/2; Q=(A+X)/2; T=orthocenter(A,P,M); draw(A--T--C--A); draw(B--A--M); draw(A--H); draw(X--T--Q); draw(H--X); draw(circumcircle(A,B,C)); draw(circumcircle(B,H,C)); dot("$A$",A,dir(150)); dot("$B$",B,dir(210)); dot("$C$",C,dir(90)); dot("$M$",M,dir(60)); dot("$X$",X,dir(60)); dot("$H$",H,dir(180)); dot("$T$",T,dir(150)); dot("$P$",P,dir(180)); dot("$Q$",Q,dir(270)); [/asy]$

The power of $T$ with respect to circles $ABC$ and $HBC$ is the same ( $TB*TC$ )
Thus, The length of the tangent is same, and we have already proved that $TX = TA$ .
This finishes the proof $\blacksquare$

Property 7: $TPXM$ are cyclic
Proof:
$[asy] import olympiad; unitsize(30); pair A,B,C,H,T,M,P,X,Q,L,O; A=(6,4); B=(7,0); C=(11,0); M=(B+C)/2; H=orthocenter(A,B,C); X=foot(H,A,M); P=(A+H)/2; Q=(A+X)/2; T=orthocenter(A,P,M); L=circumcenter(B,H,C); O=circumcenter(A,B,C); draw(A--T--C--A); draw(B--A--M); draw(A--H); draw(T--Q); draw(H--X--T); draw(L--P); draw(L--M); draw(L--X); draw(circumcircle(A,B,C)); draw(circumcircle(B,H,C)); draw(circumcircle(T,M,L)); dot("$A$",A,dir(150)); dot("$B$",B,dir(210)); dot("$C$",C,dir(90)); dot("$M$",M,dir(60)); dot("$X$",X,dir(60)); dot("$H$",H,dir(180)); dot("$T$",T,dir(150)); dot("$P$",P,dir(180)); dot("$Q$",Q,dir(270)); dot("$O_A$",L,dir(320)); [/asy]$

Like many a geometry problem, this actually becomes a lot easier if you just add in one extra point.

p_square almost wrote:

Let $O_A$ be the circumcentre of $BHC$ .
$TPXMO_A$ are cyclic with diametre $TO_A$

Clearly $O_A$ lies on the perpendicular bisector of $BC$ , so $\angle TMO_A = 90$ .
By property 6, $\angle TXO_A = 90$
Also, Since $HA = 2O_AM, APO_AM$ is a parallelogram.
This tells us that $O_AP || MA \perp TP$ (Property 4) i.e. $TPO_A$ = 90. $\blacksquare$

As a corollary, note that $O_AP || XM \Rightarrow O_AMXP$ is an isosceles trapezium.

Property 8: Duality; $A$ is the $X$ -HM point of $XBC$
Proof:
Property 3 (Use Power of Point from $M$ ) finishes this off immediately.
However look at Property 2.

p_square almost wrote:

Let N be the point where the perpendicular from $X$ to $BC$ meets circle $ABC$ . Then $X$ is the orthocentre of $BCN$

which is just another way of writing Property 2, with the roles of $X$ and $A$ switched.
$X =$ orthocentre of $BCN \Rightarrow N$ is the orthocentre of $BXC$ . $\blacksquare$

Property 9: $X$ lies on the $A$ -apollonian circle
Proof:
$[asy] import olympiad; unitsize(30); pair A,B,C,D,E,F,H,M,X; B=(0,0); A=(1,4); C=(5,0); D=foot(A,B,C); E=foot(B,A,C); F=foot(C,A,B); H=orthocenter(A,B,C); M=(B+C)/2; X = foot(H,A,M); draw(D--A--B--C--A--M); draw(B--E); draw(C--F); draw(H--X); draw(circumcircle(A,E,F)); draw(circumcircle(D,E,F)); draw(circumcircle(B,H,C)); dot("$A$",A,dir(90)); dot("$B$",B,dir(150)); dot("$C$",C,dir(60)); dot("$D$",D,dir(250)); dot("$E$",E,dir(60)); dot("$F$",F,dir(210)); dot("$H$",H,dir(150)); dot("$M$",M,dir(300)); dot("$X$",X,dir(330)); [/asy]$

It is well known that upon inversion at $A$ , the $A$ -apollonian circle becomes the perpendicular bisector of the new $B,C$ .
After performing $\sqrt{AH*AD}$ inversion $X \rightarrow M$ whereas $B \rightarrow F, C \rightarrow E$ . Since $ME = MF$ , $M$ lies on the perpendicular bisector of $EF$ . $\blacksquare$

Here is a diagram encompassing most of these properties.
$[asy] import olympiad; unitsize(30); pair Z,A,B,C,D,E,F,H,T,P,Q,X,M,N,O,L,Y; A=(6,4); B=(7,0); C=(11,0); M=(B+C)/2; D=foot(A,B,C); E=foot(B,C,A); F=foot(C,A,B); H=orthocenter(A,B,C); dot(H); X=foot(H,A,M); P=(A+H)/2; T=orthocenter(A,P,M); Q=foot(P,A,M); O=circumcenter(A,B,C); L=circumcenter(H,B,C); N=orthocenter(B,C,X); Z=foot(M,A,T); draw(B--A--C--B); draw(C--F, heavygreen); draw(E--H, heavygreen); draw(A--H, heavygreen); draw(A--M, heavygreen); draw(C--H, heavygreen); draw(D--B--F, heavygreen); draw(A--T--Q, red); draw(M--Z, red); draw(A--D, dashed+red); draw(T--X--L--M,blue); draw(L--P, blue); draw(T--P, dashed+blue); draw(T--B, red); draw(F--M--E,dotted+purple); draw(circumcircle(A,B,C),dashed+lightred); draw(circumcircle(H,B,C),blue); draw(circumcircle(L,M,T),blue); draw(circumcircle(X, H, D),dotted+lightred); draw(circumcircle(X, B, F),dotted+lightred); draw(circumcircle(X, C, E),dotted+lightred); draw(circumcircle(A,X,C),heavycyan); draw(circumcircle(A,X,B),heavycyan); draw(circle(T,4.4),orange); draw(circumcircle(A,E,F),dotted+purple); dot("$A$",A, dir(150)); dot("$B$",B,dir(215)); dot("$C$",C, dir(270)); dot("$X$",X,dir(30)); dot("$M$",M,dir(60)); dot("$T$",T,dir(150)); dot("$D$",D,dir(225)); dot("$E$",E,dir(0)); dot("$F$",F,dir(270)); dot("$P$",P,dir(45)); dot("$Q$",Q,dir(45)); dot("$O_A$",L,dir(310)); [/asy]$

$~~~~~~$
For those interested, @anantmudgal09's handout which can be found here also deals with the A-HM point. @Rmo was also helpful in property 7.

This post has been edited 3 times. Last edited by p_square, Aug 19, 2018, 11:16 AM

geometry

HM-Point

Submit

thank you for teaching me the humpty point
by ihatemath123, Jun 27, 2024, 2:43 PM
ORZZZZZZZZZZ
by avisioner, Jun 19, 2024, 12:02 AM
He never had motivation to multiply out random polynomials
by the_mathmagician, Oct 25, 2023, 1:49 AM
Getting a part 3 is unlikely... anyways, if it ever gets released, it would be great if you listed some problems where this methods are useful!
by Alfombra12, Aug 13, 2023, 10:36 AM
still waiting for part 3
by kn07, Jun 14, 2023, 10:55 PM
Orz orz
by aansc1729, Mar 13, 2023, 1:13 PM
waiting for part 3 since 1 year
by anurag27826, Jul 18, 2022, 11:19 AM
pro kid moment
by the_mathmagician, Feb 15, 2022, 2:21 AM
Ded blog
by SPHS1234, Jan 31, 2022, 7:43 AM
orzity orz orz
by tigerzhang, Oct 15, 2021, 10:08 PM
congrats on IMO gold medal!
by mathlearner2357, Jul 25, 2021, 5:04 AM
orzorzorz
by PEKKA, Jul 21, 2021, 3:55 PM
Wow this is awesome!!

Waiting for part3
by lneis1, Jun 24, 2021, 5:42 PM
Part 3 hype
by NJOY, Jun 15, 2021, 9:29 AM
Ooh niceee! Waiting for part 3!
by L567, Jun 14, 2021, 4:43 AM
Something on FE's please
by Aryan-23, Feb 26, 2019, 5:33 PM
Post!!!!!!
by ELMOliveslong, Feb 22, 2019, 7:55 PM
Really amazing!! In fact you also have the skills of presenting things neatly!! waiting for more blog posts!!
by AlastorMoody, Jan 12, 2019, 7:40 AM
A good topic
by ahwawm, Dec 20, 2018, 3:22 PM
Nice post!
by Rmo, Dec 20, 2018, 2:17 PM
Great blog!!
by AhirGauss, Dec 19, 2018, 2:56 PM
@below He must have been busy these days. Have patience, boys. Legends are not made in ~~one day~~mere two months, after all.
by hansu, Dec 12, 2018, 6:52 PM
Nice blog! Please add NT
by Wizard_32, Nov 26, 2018, 12:47 PM
No.. this blog cannot die....
by enthusiast101, Nov 19, 2018, 1:14 PM
Nice blog!
by niyu, Nov 8, 2018, 5:02 AM
An "edge" was better
by anantmudgal09, Nov 1, 2018, 2:48 PM
@rajat1603_ Why do people want to know my "preparation story'??? In this blog most (all) of my posts will be mainly about math
by p_square, Aug 17, 2018, 5:10 AM
*PLEASE* let it be about your preparation story
by rajat1603_, Aug 17, 2018, 3:57 AM
I will post something during the weekend.
by p_square, Aug 16, 2018, 11:33 AM

63 shouts

A Vertex of Math

Angle chasing with ellipses [Part 2]

by p_square, Jun 13, 2021, 8:51 AM

Angle chasing with ellipses [Part 1]

by p_square, May 24, 2021, 4:48 PM

Some Disguised Bi-partite Graphs

by p_square, May 23, 2019, 11:25 AM

An ode to generalise-ation

by p_square, Dec 19, 2018, 2:56 PM

Diagrams

by p_square, Sep 10, 2018, 10:21 AM

The A-Humpty point; Inversion

by p_square, Sep 9, 2018, 3:29 PM

The A-Humpty point; Preliminaries

by p_square, Aug 18, 2018, 12:15 PM