The End.

by yayups, Apr 26, 2021, 5:59 AM

It was a fun ride

Hatcher dump

by yayups, Sep 27, 2020, 8:15 PM

Section 1.1

As a general convention, $t\in I$ will be the path variable and $s\in I$ will be the homotopy variable.

1.1.1 wrote:

Show that the composition of paths satisfies the following cancellation property: If $f_0\cdot g_0 \simeq f_1\cdot g_1$ and $g_0\simeq g_1$ , then $f_0\simeq f_1$ .

Solution

1.1.2 wrote:

Show that the change-of-basepoint homomorphism $\beta_h$ depends only on the homotopy class of $h$ .

Solution

1.1.3 wrote:

For a path connected space $X$ , show that $\pi_1(X)$ is abelian iff all basepoint-change homomorphisms depend only on the endpoints of the path $h$ .

Solution

1.1.4 wrote:

A subspace $X\subseteq \mathbb{R}^n$ is said to be star-shaped if there is a point $x_0\in X$ such that, for each $x\in X$ , the line segment from $x_0$ to $x$ lies in $X$ . Show that if a subspace $X\subseteq\mathbb{R}^n$ is locally star-shaped, in the sense that every point of $X$ has a star-shaped neighborhood in $X$ , then every path in $X$ is homotopic to a piecewise linear path, that is, a path consisting of a finite number of straight line segments traversed at constant speed. Show this applies in particular when $X$ is open or when $X$ is a union of finitely many closed convex sets.

Solution

1.1.5 wrote:

Show that for a space $X$ , the following three conditions are equivalent:

Every map $S^1\to X$ is homotopic to a constant map, with image a point.
Every map $S^1\to X$ extends to a map $D^2\to X$ .
$\pi_1(X,x_0)=0$ for all $x_0\in X$ .

Deduce that a space $X$ is simply connected iff all maps $S^1\to X$ are homotopic.

Solution

1.1.6 wrote:

We can regard $\pi_1(X,x_0)$ as the set of basepoint-preserving homotopy classes of maps $(S^1,s_0)\to (X,x_0)$ . Let $[S^1,X]$ be the set of homotopy classes of maps $S^1\to X$ with no conditions on basepoints. Thus there is a natural map $\Phi:\pi_1(X,x_0)\to [S^1,X]$ obtained by ignoring basepoints. Show that $\Phi$ is onto if $X$ is path connected, and that $\Phi([f])=\Phi([g])$ iff $[f]$ and $[g]$ are conjugate in $\pi_1(X,x_0)$ . Hence $\Phi$ induces a one-to-one correspondence between $[S^1,X]$ and the set of conjugacy classes in $\pi_1(X)$ , when $X$ is path connected.

Solution

1.1.7 wrote:

Define $f:S^1\times I\to S^1\times I$ by $f(\theta,s)=(\theta+2\pi s,s)$ , so $f$ restricts to the identity on the two boundary circles of $S^1\times I$ . Show that $f$ is homotopic to the identity by a homotopy that is stationary on one of the boundary circles, but not by any homotopy that is stationary on both.

Solution

This post has been edited 2 times. Last edited by yayups, Sep 27, 2020, 8:18 PM

Animation!

by yayups, Nov 15, 2019, 9:44 PM

Enjoy!
https://artofproblemsolving.com/community/c6h1952595p13480666

Diffusion Problem

by yayups, Aug 7, 2019, 8:52 PM

In this post, we'll be solving the following very instructive physics problem.

Some Graduate Entrance Exam Problem wrote:

https://lh3.googleusercontent.com/-ezLy4V7zRAo/XUswBs9m42I/AAAAAAAAFQ0/lVdcCevgB0kDTlDLl-Le1pKsIvKOaVAGgCK8BGAs/s0/2019-08-07.png

A vessel with a small hole of diameter $d$ is place inside a chamber much larger than it that is filled with a gas of temperature $T_0$ and pressure $P_0$ . The pressure $P_0$ is very low, so in particular, the mean free path $\lambda$ of the gas is much larger than $d$ . The vessel is kept a constant temperature $T_1=4T_0$ . Once steady state is reached, what is the pressure in the vessel?

Since the chamber is much larger than the vessel, gas entering the vessel and leaving from the vessel won't affect the pressure or temperature of the chamber.

At this point, it is very easy to fall into the following trap. One may argue that steady state is reached when the pressures in the vessel and chamber are the same. After all, isn't that what happens when two gases come in equilibrium?

The issue with this reasoning is due to the fact that we are in the regime where $\lambda\gg d$ . What this means is that for particles near the hole that have a chance of passing through it, there are unlikely to be any collisions. The effect of pressure arises through particle collisions, so in this case, particles will pass through the hole not due to a pressure difference, but rather through the random chance that their velocity has an appropriate magnitude and direction to go through the hole (this is diffusion). Steady state is reached when the rate of particles going from the chamber to the vessel is the same as the rate of particles going from the vessel to the chamber.

Thus, to solve the problem, we need to calculate the rate that particles leave through a hole in a box of gas, given that the size of the hole is much smaller than the mean free path.

Lemma wrote:

Given a box with an (ideal) gas of particle mass $m$ , temperature $T$ , and number density $\eta$ (number of particles per unit volume), the number of particles leaving a small hole of area $A$ per unit time is
$\frac{\eta A}{4}\langle v\rangle=\frac{\eta A}{4}\sqrt{\frac{8k_BT}{\pi m}}$ assuming that $\sqrt{A}\ll\lambda$ .

Proof

The finish from here is easy. Suppose the particle number density in the chamber is $\eta_0$ and in the vessel is $\eta_1$ . Steady state implies the rate of particles flowing through the hole is the same from both sides, or that
$\eta_0\langle v_0\rangle = \eta_1\langle v_1\rangle\implies \eta_0\sqrt{T_0}=\eta_1\sqrt{T_1}\implies \eta_0=2\eta_1.$ The ideal gas law tells us that $p=\eta k_B T$ , so $p_0=2\eta_1 k_B T_0$ and $p_1=\eta_1 k_B (4T_0)=\boxed{2p_0}$ .

physics

Paralogic Triangles

by yayups, Jun 13, 2019, 4:00 AM

In this post, we consider Paralogic Triangles. The content of this post comes from a discussion with tastymath75025 and pinetree1. It's also mostly from Lemmas in Olympiad Geometry.

$[asy] unitsize(1.5inches); pair A,B,C,D,E,F,X,Y,Z,P,Q,H,HH,R; A=dir(105); B=dir(210); C=dir(330); F=(0.3)*A+(0.7)*B; E=(3/5)*A+(2/5)*C; D=extension(E,F,B,C); X=2*circumcenter(A,E,F)-A; Y=2*circumcenter(B,D,F)-B; Z=2*circumcenter(C,D,E)-C; P=extension(A,X,B,Y); Q=2*foot(P,circumcenter(A,B,C),circumcenter(X,Y,Z))-P; H=orthocenter(A,B,C); HH=orthocenter(X,Y,Z); R=2*foot(Q,D,E)-Q; draw(A--B--C--cycle,linewidth(1.5)+red); draw(D--B); draw(X--Y--Z--cycle,linewidth(1.5)+orange); draw(X--E,dotted); draw(circumcircle(A,B,C)); draw(D--F--E,blue); draw(A--X--P,green); draw(P--B--Y,green); draw(Z--P--C,green); draw(circumcircle(X,Y,Z)); dot("$A$",A,dir(A)); dot("$B$",B,dir(230)); dot("$C$",C,dir(C)); dot("$F$",F,1.5*dir(105)); dot("$E$",E,dir(0)); dot("$D$",D,dir(180)); dot("$X$",X,dir(-10)); dot("$Y$",Y,dir(160)); dot("$Z$",Z,dir(200)); dot("$P$",P,1.3*dir(270)); dot("$Q$",Q,1.3*dir(110)); dot("$H$",H,1.3*dir(0)); dot("$H'$",HH,1.3*dir(180)); dot("$R$",R,1.3*dir(-30)); [/asy]$

Consider $\triangle ABC$ , and let $\ell$ be an arbitrary line that intersects the sides at $D$ , $E$ and $F$ . Let $\ell_A$ be the the perpendicular to $BC$ through $D$ , and define $\ell_B$ and $\ell_C$ similarly. Finally, let $XYZ$ be the triangle determined by $\ell_A$ , $\ell_B$ and $\ell_C$ .

It's clear that $XYZ\sim ABC$ because the repsective sides are perpendicular. In fact, the triangles are perspective through $P$ which lies on $(ABC)\cap(XYZ)$ . Firstly, by Desargues's theorem, the triangles are perspective. To show that $P\in (ABC)$ , note that
$\angle BCP=\angle DCZ=\angle DEZ=\angle FEX=\angle FAX=\angle BAP,$ since $DECZ$ cyclic, so $P\in(ABC)$ . We also see that $P\in(XYZ)$ since the setup is symmetric under $ABC\leftrightarrow XYZ$ interchange.

It turns out that $(ABC)$ and $(XYZ)$ are in fact orthogonal. The key is to constuct the point $Q$ which is the other intersection of the two circles. Note that $P=YB\cap CZ$ and $Q=(PYZ)\cap(PBC)$ , so $Q$ is the spiral center sending $YZ\mapsto BC$ . Thus, $Q$ is the center of the unique spiral similarity sending $XYZ\mapsto ABC$ . Now we see that any such spiral similarity must have angle equal to $\pi/2$ since the corresponding sides of $XYZ$ and $ABC$ are perpendicular. Thus, the unique spiral similarity sending $(XYZ)$ to $(ABC)$ has angle $\pi/2$ , which implies the circles are orthogonal.

The point $Q$ turns out to be quite nice, and in fact it is the Miquel point of $DFXZEY$ and $FBCEAD$ . To see this, note that by the spiral similarity, $\angle AQX=\pi/2$ , so $(AQFXE)$ is cyclic, which implies it's the Miquel point of both quadrilaterals, since $Q$ is already on $(ABC)$ and $(XYZ)$ . In particular, this means that $Q$ has a Simson line with respect to both complete quadrilaterals, which will be useful soon.

We now prove Sondat's Theorem for Paralogic Triangles. Let $H$ be the orthocenter of $ABC$ and $H'$ the orthocenter of $XYZ$ . The theorem states that the line $\ell=DEF$ bisects $HH'$ . Note that when $DEF$ is a Simson line, then $X=Y=Z=H'=P$ , and the theorem is the classic statement that the Simson line bisects $PH$ .

Let $s$ be the Steiner line of $Q$ with respect to $(ABC)$ , which is just the Simson line scaled up by a factor of $2$ at $Q$ . By the lemma above, we see that it passes through $H$ . But since $Q$ is the Miquel point, the line $s$ also passes through the reflection of $Q$ in $DEF$ , which we'll call $R$ . Thus, line $s$ is $HR$ .

Let $s'$ be the corresponding Steiner line of $Q$ with respect to $XYZ$ . We see that $s'$ is sent to $s$ under the spiral similarity at $Q$ , so $s\perp s'$ By the above, we also have $s'=H'R$ . This implies that $\angle H'RH=\pi/2$ . Thus, $\ell=DEF$ is the perpendicular bisector of $QR$ , which implies that it passes through the center $(HH'QR)$ , which is the midpoint of $HH'$ , as desired. This completes the proof. $\blacksquare$

Projective Gauss Line

by yayups, May 13, 2019, 6:43 AM

The inspiration (and much of the content) of this post came from a discussion I was having recently with some people.

In this post, we'll outline a projective viewpoint on the Gauss Line, but first, let's give the standard presentation.

Gauss Line wrote:

For a complete quadrilateral $ABCDPQ$ ( $P=AD\cap BC$ and $Q=AB\cap CD$ ), the midpoints of $AC$ , $BD$ and $PQ$ are all collinear.

$[asy] unitsize(1inches); pair A=1.1*dir(110); pair B=1.5*dir(65); pair C=dir(-50); pair D=0.7*dir(180); pair P=extension(A,D,B,C); pair Q=extension(A,B,C,D); pair H=orthocenter(B,C,Q); pair U=foot(B,Q,C); pair V=foot(C,B,Q); pair W=foot(Q,B,C); pair X=IP(CP((A+C)/2,A),CP((D+B)/2,B)); pair Y=OP(CP((A+C)/2,A),CP((D+B)/2,B)); dot("$A$",A,dir(A)); dot("$B$",B,dir(B)); dot("$C$",C,dir(C)); dot("$D$",D,dir(230)); dot("$P$",P,dir(90)); dot("$Q$",Q,dir(180)); dot("$H$",H,1.9*dir(150)); dot("$U$",U,dir(260)); dot("$V$",V,dir(90)); dot("$W$",W,dir(-20)); draw(C--P); draw(C--Q); draw(D--P); draw(B--Q); draw(B--U,dashed+red); draw(C--V,dashed+red); draw(Q--W,dashed+red); draw(CP((A+C)/2,A),dotted+blue); draw(CP((D+B)/2,B),dotted+blue); draw(CP((P+Q)/2,P),dotted+blue); draw(X--Y,green); [/asy]$

The proof goes as follows. Let $H$ be the orthocenter of $BCQ$ , and let $UVW$ be the orthic triangle of $BCQ$ . Note that the power of $H$ with respect to $(BD)$ is $HB\cdot HU$ , the power with respect to $(AC)$ is $HC\cdot HV$ , and the power with respect to $(PQ)$ is $HQ\cdot HW$ . These are all equal, so $H$ has equal power with respect to $(AC)$ , $(BD)$ , and $(AC)$ . We may repeat a similar argument for the orthocenters of $ADQ$ , $BAP$ , and $CDP$ , and we see then that $(AC)$ , $(BD)$ , and $(PQ)$ are coaxial. Thus, their centers are collinear, and this proves the existence of the Gauss line.

Projective Gauss Line wrote:

The Gauss line is the locus of the centers of all inscribed conics to $(ABCD)$ .

There are two things to check. Firstly, by taking a limit of appropriate thin ellipses inscribed in $ABCD$ , one that approaches segment $AC$ , one for segment $BD$ , and one for $PQ$ , we see that these midpoints are on this locus. However, the main thing we need to check is that this locus is a line. Note that projectively, the center of a conic is the pole of the line at infinity with respect to the conic.

So the problem reduces to the following:

Rephrased Problem v1 wrote:

Fix some line $\ell$ , and consider the family of conics $\gamma$ inscribed in $ABCD$ . The locus of the pole of $\ell$ in $\gamma$ is a line.

It will be much easier to prove the dual statement, which we can get by letting $w=AB$ , $x=BC$ , $y=CD$ , and $z=DA$ .

Rephrased Problem v2 wrote:

Fix some point $L$ , and consider the family of conics $\Gamma$ that pass through some fixed points $WXYZ$ . The polar of $L$ in $\Gamma$ passes through a fixed point.

We'll prove this version. Let $k$ be the line tangent to $\mathrm{Conic}(W,X,Y,Z,L)$ at $L$ .

Let $\Gamma$ be some random conic passing through $WXYZ$ . By Desargue's involution theorem with line $k$ , we see that there is some fixed involution (dependent only on $WXYZ$ ) that swaps the two points $\{U,V\}:=k\cap\Gamma$ . By construction, $L$ is a fixed point of this involution, so there must be a second fixed point, call it $L'$ . We see that $L$ and $L'$ are fixed by this involution, so this involution must be harmonic conjugation in $LL'$ . Thus,
$(LL';UV)=-1$ so $L'$ lies on the polar of $L$ with respect to $\Gamma$ , as desired (note that $L'$ is only dependent on $L$ and $WXYZ$ ). $\blacksquare$

This concludes the projective classification of the Gauss Line. Note that this then trivializes the theorem that the incenter of $ABCD$ (if it exists) lies on the Gauss Line.

This post has been edited 2 times. Last edited by yayups, Aug 4, 2019, 6:59 AM

geometry

projective geometry

Projective Bary

by yayups, May 11, 2019, 6:06 AM

This solution shows a nontrivial usage of the projective nature of barycentric coordinates.

USAMO Shortlist 2014, 110 Geometery Problems #77 wrote:

Let $ABC$ be a triangle with circumcircle $\Gamma$ and incircle $\gamma$ . Let $A'$ be the mixtilinear excircle touch point, and let $A'B'$ and $A'C'$ be tangent to $\gamma$ with $B',C'\in\Gamma$ . Let $X$ be the tangency point of $B'C'$ with $\gamma$ which exists by Poncelet's Porism. Show that $(XBC)$ is tangent to $\gamma$ .

$[asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ unitsize(0.2inches); import graph; size(0cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -10, xmax = 14, ymin = -22.62, ymax = 13.46; /* image dimensions */ pen zzttqq = rgb(0.6,0.2,0); draw((0.26,7.92)--(-1.52,-2.18)--(9.54,-2.2)--cycle, linewidth(2) + zzttqq); /* draw figures */ draw((0.26,7.92)--(-1.52,-2.18), linewidth(2) + zzttqq); draw((-1.52,-2.18)--(9.54,-2.2), linewidth(2) + zzttqq); draw((9.54,-2.2)--(0.26,7.92), linewidth(2) + zzttqq); draw(circle((4.017668907550992,2.050905875698934), 6.968955550057753), linewidth(2)); draw(circle((2.278232171040842,1.001527516890443), 3.1883907164579206), linewidth(2)); draw((5.8094995867931365,8.78556876819826)--(0.07556713698788581,3.306761151157378), linewidth(2)); draw((0.07556713698788581,3.306761151157378)--(-2.791521751662705,0.5672401366735647), linewidth(2)); draw((-2.791521751662705,0.5672401366735647)--(-5.658856324457237,-2.1725156305163527), linewidth(2)); draw((-5.658856324457237,-2.1725156305163527)--(-1.52,-2.18), linewidth(2)); draw((-2.791521751662705,0.5672401366735647)--(5.215750162966643,-4.8142920649363115), linewidth(2)); draw((5.215750162966643,-4.8142920649363115)--(5.8094995867931365,8.78556876819826), linewidth(2)); /* dots and labels */ dot((0.26,7.92),dotstyle); label("$A$", (0.34,8.12), N * labelscalefactor); dot((-1.52,-2.18),dotstyle); label("$B$", (-1.44,-1.98), NE * labelscalefactor); dot((9.54,-2.2),dotstyle); label("$C$", (9.62,-2), E *3* labelscalefactor); dot((2.2724665553022745,-2.1868579865376176),linewidth(4pt) + dotstyle); label("$D$", (2.36,-2.02), NE * labelscalefactor); dot((5.215750162966643,-4.8142920649363115),linewidth(4pt) + dotstyle); label("$A'$", (5.3,-4.66), S * 4*labelscalefactor); dot((-2.791521751662705,0.5672401366735647),linewidth(4pt) + dotstyle); label("$B'$", (-3.48,0.62), NW*0.01 * labelscalefactor); dot((5.8094995867931365,8.78556876819826),linewidth(4pt) + dotstyle); label("$C'$", (5.88,8.94), NE * labelscalefactor); dot((-5.658856324457237,-2.1725156305163527),linewidth(4pt) + dotstyle); label("$T$", (-6.02,-1.92), NE * labelscalefactor); dot((0.07556713698788581,3.306761151157378),linewidth(4pt) + dotstyle); label("$X$", (0.02,3.66), N * labelscalefactor); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy]$

Firstly, the problem is clearly just asking us to show that $B'C'$ is tangent to $(XBC)$ . Letting $T=B'C'\cap BC$ , we see that this is equivalent to $TB\cdot TC=TX^2$ , but $TD=TX$ , so all we need to show is that
$TB\cdot TC=TD^2.$ We'll actually just compute the barycentric coordinates of $T$ and verify this explicitly. However, finding $B'$ and $C'$ is really messy, and this doesn't seem tractable immediately. However, the beauty of this solution is getting a simple way to find the coordinates of $T$ .

Let $P$ be a variable point on $BC$ , and define the composite map $\phi$ given by
$P\mapsto P'\mapsto P_1P_2\cap BC$ where $P'$ is the $\sqrt{bc}$ inverse of $P$ and $P_1P'$ and $P_2P'$ are tangent to $\gamma$ with $P_1,P_2\in\Gamma$ . It's not easy to see that this map $\phi$ is projective but its true.

Why?

Now, we check that
$B\mapsto C\mapsto AB\mapsto B,$ so $\phi(B)=B$ , and similarly $\phi(C)=C$ . Also,
$\infty_{BC}\mapsto A\mapsto BC,$ but uh-oh, what's $BC\cap BC$ ? The fix is that we actually have the tangent to $\gamma$ at some point infinitesimally close to $D$ , which then intersects $BC$ really close to $D$ , so we have $\phi(\infty_{BC})=D$ .

Now, use projective coordinates for $BC$ given by the last two coordinates of the barycentric coordinates of a point on $BC$ . The map $\phi$ looks like some matrix
$\begin{pmatrix}w & x\\ y& z\end{pmatrix}$ that is considered the same under scaling. We see that $B=(1:0)$ and $C=(0:1)$ map to themselves, so $x=y=0$ . The point $\infty_{BC}$ is given by $(1:-1)$ , and it maps to $D=(s-c:s-b)$ , so the matrix is
$\phi\equiv \begin{pmatrix}s-c & 0\\ 0 & -(s-b)\end{pmatrix}.$ Now, we see that $T=\phi(D)$ since $D$ and $A'$ are $\sqrt{bc}$ inverses (the incircle gets sent to the mixtilinear excircle), so
$T=\begin{pmatrix}s-c & 0\\ 0 & -(s-b)\end{pmatrix}\begin{pmatrix}s-c \\ s-b\end{pmatrix}=\begin{pmatrix}(s-c)^2 \\ -(s-b)^2\end{pmatrix},$ so $T=((s-c)^2:-(s-b)^2)$ . The rest is a boring bash which we do below.

Homogenizing, we have $D=\left(\frac{s-c}{a},\frac{s-b}{a}\right)$ , $T=\left(\frac{(s-c)^2}{a(b-c)},-\frac{(s-b)^2}{a(b-c)}\right)$ , $B=(1,0)$ , and $C=(0,1)$ . By taking simply the first coordinate, we get a coordinate system on $BC$ that preserves the lengths in the original setup, so
$TB=\frac{(s-c)^2}{(b-c)a}-1=\frac{(s-b)^2}{(b-c)a}$ and $TC=\frac{(s-c)^2}{(b-c)a}$ , and
$TD=\frac{(s-c)^2}{(b-c)a}-\frac{s-c}{a}=\frac{s-c}{a}\cdot\frac{s-b}{b-c}=\frac{(s-b)(s-c)}{a(b-c)}.$ Evidently, we have $TB\cdot TC=TD^2$ , as desired. As we showed before, this means $TB\cdot TD=TX^2$ , so $(XBC)$ is tangent to $B'C'$ , which is tangent to $\gamma$ at $X$ , so $(XBC)$ is tangent to $\gamma$ . $\blacksquare$

This post has been edited 3 times. Last edited by yayups, May 11, 2019, 10:35 PM

geometry

projective geometry

Olympiad

Combinatorial Games

by yayups, Feb 14, 2019, 2:58 AM

Here are 2 nice combinatorial games problems that I solved recently. They are very similar as explained in the remark below.

USAMO 1999/5 wrote:

The Y2K Game is played on a $1 \times 2000$ grid as follows. Two players in turn write either an S or an O in an empty square. The first player who produces three consecutive boxes that spell SOS wins. If all boxes are filled without producing SOS then the game is a draw. Prove that the second player has a winning strategy

Solution

ISL 2015 C4 wrote:

Let $n$ be a positive integer. Two players $A$ and $B$ play a game in which they take turns choosing positive integers $k \le n$ . The rules of the game are:

(i) A player cannot choose a number that has been chosen by either player on any previous turn.
(ii) A player cannot choose a number consecutive to any of those the player has already chosen on any previous turn.
(iii) The game is a draw if all numbers have been chosen; otherwise the player who cannot choose a number anymore loses the game.

The player $A$ takes the first turn. Determine the outcome of the game, assuming that both players use optimal strategies.

Proposed by Finland

Solution

Remark, also a spoiler

combinatorics

Olympiad

Mathematicians are Cleverer than Physicists

by yayups, Jan 11, 2019, 7:08 AM

USA TST 2015/3 wrote:

]A physicist encounters $2015$ atoms called usamons. Each usamon either has one electron or zero electrons, and the physicist can't tell the difference. The physicist's only tool is a diode. The physicist may connect the diode from any usamon $A$ to any other usamon $B$ . (This connection is directed.) When she does so, if usamon $A$ has an electron and usamon $B$ does not, then the electron jumps from $A$ to $B$ . In any other case, nothing happens. In addition, the physicist cannot tell whether an electron jumps during any given step. The physicist's goal is to isolate two usamons that she is sure are currently in the same state. Is there any series of diode usage that makes this possible?

Proposed by Linus Hamilton

Label the usamons $1,\ldots,n=2015$ . Let $x_i=0$ if usamon $i$ has no electron, and $x_i=1$ otherwise.

Lemma: If there exists $\sigma\in S_n$ such that the physicist's knowledge is exactly
$x_{\sigma(1)}\le x_{\sigma(2)}\le\cdots\le x_{\sigma(n)},$ then a firing of a diode does not change this fact (note that $\sigma$ may be different).

Proof of Lemma: If $i\to j$ is fired where $\sigma(i)<\sigma(j)$ , then the physicist knows the charge distribution won't change. However, if $i\to j$ is fired with $\sigma(i)>\sigma(j)$ , then the physicist knows that the charges on $i$ and $j$ will swap. Thus, if $\sigma'\in S_n$ such that $\sigma'(j)=\sigma(i)$ and $\sigma'(i)=\sigma(j)$ , and otherwise $\sigma'(x)=\sigma(x)$ , then the physicist's information is of the form
$x_{\sigma'(1)}\le x_{\sigma'(2)}\le\cdots\le x_{\sigma'(n)}.$ Thus, the lemma is proven. $\blacksquare$

This actually implies that if the physicist has information
$x_{\sigma(1)}\le x_{\sigma(2)}\le\cdots\le x_{\sigma(n)},$ then she can never win, because whatever she does, she'll end up at the information
$x_{\sigma'(1)}\le x_{\sigma'(2)}\le\cdots\le x_{\sigma'(n)}.$ At this point if she presents usamons $i$ and $j$ with $\sigma'(i)<\sigma'(j)$ , simply set $x_i=0$ and $x_j=1$ , and the physicist loses.

But the physicist starts with no information, but we showed that even if she knew the $\sigma\in S_n$ such that
$x_{\sigma(1)}\le x_{\sigma(2)}\le\cdots\le x_{\sigma(n)},$ then she still couldn't win. Therefore, with no information to start of with, she certainly cannot win. $\blacksquare$

Remarks Originally, I was trying to show that the physicist's knowledge at any time was a poset on the $x_i$ s. This proved to be very tricky, but in the process of trying to do so, I was trying to split the poset into chains and doing a similar argument to the above. Eventually, I realized that the solution was starting me in the face if I simply took the knowledge poset to be a full chain. This is not hard to guess since it is very easy to see (and was in fact the first thing I noticed while solving this problem) that the physicist can attain the knowledge that is in the form of a chain (fire diodes $i\to j$ for $i<j$ in lexicographic order on $(i,j)$ ).

Moving points tutorial

by yayups, Jan 5, 2019, 9:50 AM

I think a lot of people will really like this. (original link here https://artofproblemsolving.com/community/c6h1763036)

Hi All,

I've been getting many requests lately to explain this technique, so here is a short writeup which explains the method of projective maps from scratch. Any suggestions are welcome, and I hope it helps!

Basic familarity with projective geometry is assumed. Mainly just good intuition with cross ratios is required.

Let $\mathcal{C}$ be a conic, a line, or a pencil of lines through a fixed point (note that this last one is often ommited from the definition, but I find it to be quite important). These objects have a structure of cross ratio built into them, specifically, if $A,B,C,D\in\mathcal{C}$ , then we can talk about $(AB;CD)$ (note that if $\mathcal{C}$ is a pencil of lines, then $A,B,C,D$ are lines). The definition of a projective map is now very simple.

Definition A projective map $f$ from $\mathcal{C}_1$ to $\mathcal{C}_2$ where these are either conics, lines, or a pencil of lines is a function that preserves cross ratio. In particular, if $A,B,C,D\in\mathcal{C}_1$ , then
$(AB;CD) = (f(A)f(B);f(C)f(D)).$ And that's all!

The reason this is useful is the following theorem.

Theorem If $f,g:\mathcal{C}_1\to\mathcal{C}_2$ are projective, then $f\equiv g$ if $f$ and $g$ coincide on three different input values.

Proof: Suppose $f(A)=g(A)$ , $f(B)=g(B)$ , $f(C)=g(C)$ . Then,
$(AB;CD)=(f(A)f(B);f(C)f(D))=(g(A)g(B);g(C)g(D))=(f(A)g(B);f(C)g(D)).$ The important equation is $(f(A)f(B);f(C)f(D))=(f(A)g(B);f(C)g(D))$ . Since the cross ratio is bijective, we have $f(D)=g(D)$ , as desired. $\blacksquare$

When solving problems, if we can phrase the problem as in the theorem, then actually we only have to check the problem for 3 cases! Before doing examples, let's cover some basic transformations that are projective maps. Your intuition with cross ratios is going to be really helpful here. Firstly, note that the composition of two projective maps is projective, and the inverse of a projective map is projective (Exercise: Prove this from the definition!). Here is a list I could come up with for projective maps (not exhaustive by any means).

Given a line $\ell$ and a point $P$ , the map from $\ell$ to $\mathcal{C}_P$ (the pencil of lines through $P$ ) given by $X\mapsto PX$
Given a conic $\gamma$ and a point $P$ on the conic, the map from $\ell$ to $\mathcal{C}_P$ given by $X\mapsto PX$
Given a conic $\gamma$ and any point $P$ , the map from $\gamma$ to $\gamma$ by $X\mapsto PX\cap\gamma\not=X$
This one's a little off beat, but still useful. Given two clines $\gamma_1$ and $\gamma_2$ , any inversion (or Mobius transform for that matter) that sends $\gamma_1$ to $\gamma_2$ is projective. This is because of the famous fact that inversion preserves cross ratio.

You might be wondering where projecting from a line to a line fits in. It turns out this is actually a composition of two of the maps we listed above. In particular, if $P$ is a point and $\ell_1,\ell_2$ are lines, then we first map $\ell_1\to\mathcal{C}_P$ using the first map, then map $\mathcal{C}_P\to\ell_2$ using the inverse of the first map. Their composition is the classic perspectivity map. It's time to do some examples!

USA Winter TST for IMO 2019 Problem 1 wrote:

Let $ABC$ be a triangle and let $M$ and $N$ denote the midpoints of $\overline{AB}$ and $\overline{AC}$ , respectively. Let $X$ be a point such that $\overline{AX}$ is tangent to the circumcircle of triangle $ABC$ . Denote by $\omega_B$ the circle through $M$ and $B$ tangent to $\overline{MX}$ , and by $\omega_C$ the circle through $N$ and $C$ tangent to $\overline{NX}$ . Show that $\omega_B$ and $\omega_C$ intersect on line $BC$ .

Merlijn Staps

$[asy] size(8cm); pair A = dir(129); pair B = dir(220); pair C = dir(320); filldraw(A--B--C--cycle, invisible, black); pair M = 0.5*A + 0.5*B; pair N = 0.5*A + 0.5*C; pair O = circumcenter(A,M,N); pair Q = rotate(-90,A)*O; pair X = 4.2*Q - 3.2*A; pair Y = intersectionpoints(circle(X,abs(X-A)),circumcircle(A,M,N))[0]; pair Z = 0.5*A + 0.5*Y; filldraw(circumcircle(C,Y,N), invisible, blue+opacity(0.5)); draw(A--X,red); pair S = circumcenter(C, N, Y); pair T = foot(S, B, C); pair D = 2*T - C; pair P = extension(S, midpoint(N--C), X, N); draw(N--X); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); dot("$C$", C, dir(0)); dot("$M$", M, dir(135)); dot("$N$", N, dir(80)); dot("$X$", X, dir(X)); dot("$D$", D, dir(225)); [/asy]$

Diagram made by v_Enhance. Let $\ell_1$ be the tangent at $A$ to $(ABC)$ and let $\ell_2=BC$ . Let $f$ be the map from $\ell_1$ to $\ell_2$ given by $f(X)=D=\omega_C\cap BC$ . Note that this means $\angle XND=\angle C$ (directed angles).

So consider the map from $\mathcal{C}_N$ to $\mathcal{C}_N$ given by rotation by angle $\angle C$ . This is clearly projective. We have the map from $\ell_1\to\mathcal{C}_N$ by $X\mapsto NX$ , and we have $\mathcal{C}_N\to\ell_2$ by $w\mapsto w\cap\ell_2$ . Therefore, composing all these projective maps in the order
$\ell_1\to\mathcal{C}_N\to\mathcal{C}_N\to\ell_2,$ we have that $f$ is a projective map that maps $X\mapsto D$ .

Similarly, we define a map $f':\ell_1\to\ell_2$ that sends $f'(X)=D'=\omega_B\cap BC$ . We have again that its projective. We want to show $D=D'$ , so by the theorem, we just have to check this for three choices of $X$ . This is now a geometry problem that is left to the reader!

Note: This proof is written much shorter like this. Let $D=\omega_C\cap BC$ . Then,
$X\mapsto NX\mapsto ND\mapsto D$ is projective, so $X\mapsto D$ is projective. Similarly if $D'=\omega_B\cap BC$ , then $X\mapsto D'$ is projective. So it suffices to check for three values of $X$ .

The next example will have the proof again written nice and short like the above.

IMO 2010/2 wrote:

Given a triangle $ABC$ , with $I$ as its incenter and $\Gamma$ as its circumcircle, $AI$ intersects $\Gamma$ again at $D$ . Let $E$ be a point on the arc $BDC$ , and $F$ a point on the segment $BC$ , such that $\angle BAF=\angle CAE < \dfrac12\angle BAC$ . If $G$ is the midpoint of $IF$ , prove that the meeting point of the lines $EI$ and $DG$ lies on $\Gamma$ .

$[asy] import olympiad; import cse5; size(8cm); defaultpen(fontsize(9pt)); pair A = dir(110); dot("$A$", A, dir(A)); pair B = dir(210); dot("$B$", B, dir(B)); pair C = dir(330); dot("$C$", C, dir(C)); pair I = incenter(A, B, C); dot("$I$", I, dir(45)); pair O = origin; pair D = extension(A, I, O, B+C); dot("$D$", D, dir(225)); pair E = dir(310); dot("$E$", E, dir(E)); pair F_1 = B*C/E; pair F = extension(B, C, A, F_1); dot("$F$", F, dir(F)); pair G = midpoint(I--F); dot("$G$", G, dir(-15)); pair K = extension(E, I, D, G); dot("$K$", K, dir(K)); pair I_A = 2*D-I; pair P = extension(D, K, A, F); pair Z = extension(I, P, I_A, F); draw(A--B--C--cycle, red); draw(unitcircle, blue); draw(A--E--K--D--cycle, green); draw(I--F); [/asy]$

Diagram from v_Enhance. We will animate $E$ on $\Gamma$ , which means that we have mappings generated by varying $E$ . Let $K_1=EI\cap\Gamma$ and $K_2=DG\cap\Gamma$ . We have that $E\mapsto K_1$ is projective by the third item on our list.

We'll now show that $E\mapsto K_2$ is projective. Note that $E\mapsto AE\mapsto AF\mapsto F$ is projective since $AE\mapsto AF$ is a reflection which clearly preserves cross ratio. Also, $F\mapsto G$ is projective since it is a homothety at $I$ with factor $1/2$ (here the codomain is the scaling of $BC$ by $1/2$ at $I$ ). Thus, $E\mapsto F\mapsto G$ is projective. Projecting through $D\in\Gamma$ , we have that $G\mapsto K_2$ is projective, so $E\mapsto G\mapsto K_2$ is projective, as deisred.

Therefore, to show $K_1=K_2$ , it suffices to check three values of $E$ . It is now a geometry problem (an easy one at that) to check the problem for $E=B,D,C$ (possible hint: fact 5).

This post has been edited 1 time. Last edited by yayups, Mar 27, 2019, 11:40 PM

projective geometry

geometry

Olympiad

Submit

i searched up moving points and found this
what the actual orz
by balllightning37, Mar 24, 2024, 9:24 PM
what the orz have I seen here
by avisioner, Feb 7, 2024, 2:50 PM
yayups howsopro ORZORZ
by the_mathmagician, Oct 20, 2021, 12:09 AM
orzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorz
by 554183, Oct 18, 2021, 3:32 PM
One of the best blogs I have come across
by lneis1, Jul 26, 2021, 2:17 PM
Are u surprised by him making IMO
looking at his posts, it was very likely any way
by 554183, Jul 8, 2021, 6:05 AM
WAIT WHAT HE MADE IMO 2020

HOW TO BE SO GOD TIER

ORZORZORZORZ
by OlympusHero, Jun 6, 2021, 3:00 AM
give contrib thanqies
by RedFireTruck, May 5, 2021, 5:16 PM
hey there
by yofro, Apr 13, 2021, 1:44 AM
@below He is contestant 2
by Gaussian_cyber, Sep 20, 2020, 10:37 AM
did you make IMO 2020?
which contestant are you?
by Orestis_Lignos, Sep 18, 2020, 2:27 PM
yayups IMO 2020
by fukano_2, Sep 10, 2020, 6:30 AM
how do u know he made IMO?
by Puffer13, Sep 6, 2020, 12:12 PM
Congrats on USA IMO!
by Imayormaynotknowcalculus, Aug 15, 2020, 4:52 PM
IMO 2020
by cmsgr8er, Aug 7, 2020, 8:16 PM
Nice blog! dang you seem pretty clever
by sunfishho, Sep 6, 2017, 3:45 AM
Nice blog
by niyu, Jul 7, 2017, 10:33 PM
thanks bro
by yayups, Jul 7, 2017, 5:10 AM
Nice blog!
by pinetree1, Jul 2, 2017, 1:20 AM
thanks
by yayups, Jun 28, 2017, 2:58 AM
Nice first posts, keep it up!
by pohoatza, Jun 28, 2017, 2:39 AM
lol
we can make a collaborative blog if you want though
but I kind of want to keep this blog more of a personal blog
by yayups, Jun 28, 2017, 1:17 AM
Nice blog!

@pinetree1 He told me that he's not giving contribs on this blog
by niyu, Jun 28, 2017, 1:12 AM
hi
That problem is very cool
I was considering putting it, but then decided not to since it was a little too difficult IMO
by yayups, Jun 28, 2017, 12:54 AM
hello yayups!
by JasperL, Jun 28, 2017, 12:43 AM
Contrib?
by pinetree1, Jun 27, 2017, 6:14 PM
Thanks
You guys seem pretty good
by yayups, Jun 27, 2017, 6:04 PM
Nice blog!
by pinetree1, Jun 27, 2017, 3:28 PM
First shout, cool blog
by Ankoganit, Jun 27, 2017, 8:00 AM

93 shouts

The blog of yayups

by yayups, Apr 26, 2021, 5:59 AM

by yayups, Sep 27, 2020, 8:15 PM

by yayups, Nov 15, 2019, 9:44 PM

by yayups, Aug 7, 2019, 8:52 PM

by yayups, Jun 13, 2019, 4:00 AM

by yayups, May 13, 2019, 6:43 AM

by yayups, May 11, 2019, 6:06 AM

by yayups, Feb 14, 2019, 2:58 AM

by yayups, Jan 11, 2019, 7:08 AM

by yayups, Jan 5, 2019, 9:50 AM