Skip to main content

Calkin-Wilf Tree

I gave this talk at CMI STEMS final camp 2024.

Definitions

Before proceeding, we must be clear about what our title means.

What do you mean by Counting?

What do we mean by the term counting? We are going to prove that Rational numbers are countable. That is, there is a bijection between natural numbers and rational numbers.
A bijective function $f:X\rightarrow Y$ is a one-to-one (injective) and onto (surjective) mapping of a set $X$ to a set $Y$.
Note that every bijection from set $X$ to a set $Y$ also has an inverse function from set $Y$ to set $X$. But how are we going to create the bijection? We will first create a bijection between the Natural numbers and Positive rationals. Let $f(1),f(2),\dots $ be the mapping from natural numbers from $\Bbb{N}\rightarrow +\Bbb{Q}$. Then, note that there is also a bijection from $\Bbb{N}\rightarrow -\Bbb{Q}$ by simply mapping $i\in \Bbb{N}\rightarrow -f(i)$. And to create the bijection from $g:\Bbb{N} \rightarrow \Bbb{Q}$, consider \begin{equation} g(n)= \begin{cases} f(k) & \text{if } n=2k, k\in \Bbb{N}\\ -f(k) & \text{if } n=2k+1, k\in \Bbb{N}, k>1\\ 0 & \text{if } n=1 \end{cases} \end{equation} Great! So we know how to create a bijection between $\Bbb{N}\rightarrow\Bbb{Q}$ if we are given the bijection between $\Bbb{N}\rightarrow+\Bbb{Q}$. But how can we create the bijection between $\Bbb{N}\rightarrow+\Bbb{Q}$? We use the Cute tree!

Cute tree

Every node of this binary tree is assigned a positive fraction.And the starting node is $\frac{1}{1}$. If the positive fraction is $\frac{p}{q}$, then we define it's left child as $\frac{p}{p+q}$ and the right child as $\frac{p+q}{q}$. We call the fraction $\frac{p}{q}$ as the parent of $\frac{p}{p+q}$ and $\frac{p+q}{q}$.

Introduction

In general, if we have the fraction as $x$, then note that it's left child is $\frac{x}{x+1}$ and the right child is $x+1$. However, before proceeding, we shall prove this.
If the parent is $x$, then it's left child is $\frac{x}{x+1}$ and the right child is $x+1$.
Let $x=\frac{p}{q}$. Then by definition, $$\text{ the right child is }\frac{p+q}{q}=\frac{p}{q}+1=x+1. $$ And by definition, $$\text{ the left child is }\frac{p}{p+q}=\frac{1}{\left(\frac{p+q}{q}\right)}\cdot \frac{p}{q}=\frac{x}{x+1}.$$

Infinite cute tree

We start with $\frac{1}{1}$ and proceed to make the left child and right child. Note that this process is infinite and hence the name.
$$\vdots$$
Define the $1$st row has $1/1$. The second row has childs of $1/1$. The $n+1$st row is the row which has childs of $n$th row fractions.

Some properties

Here are a few properties of the infinite cute tree which we will proceed to prove in the talk.
Every positive rational number appears in the tree and appears uniquely on the tree.
Assuming this proposition is true, we can simply number every node in every row systematically. But how are we numbering? Start numbering from the first row and then number starting from the right side of the next row and continue. We get $$f(1)\rightarrow \frac{1}{1}$$ $$f(2)\rightarrow \frac{1}{2}$$ $$f(3)\rightarrow \frac{2}{1}$$ $$f(4)\rightarrow \frac{1}{3}$$ $$f(5)\rightarrow \frac{3}{2}$$ $$\vdots$$
All the fractions in the infite cute tree are in reduced form.
We can prove this using induction.
If $\frac{p}{q}$ is reduced then so is $\frac{p}{p+q},\frac{p+q}{q}$.
Note that $$(p,q)=1\implies (p+q,p)=1,(q,p+q)=1\implies \frac{p}{p+q},\frac{p+q}{q}\text{ are in reduced form if }$$ $\frac{p}{q}\text{ is in reduced form }. $ Clearly elements of row $1$ are reduced. Say elements are reduced for $k$th row. Then by our above claim, we get that $k+1$th row is reduced, and by induction, we are done.
The left child of any vertex is always strictly less than $1$.
Let $\frac{p}{q}$ is the parent, then the left child is $\frac{p}{p+q}$ which is less than $\frac{p}{p}=1$.
For example, the left child of $\frac{20}{23}$ is $\frac{20}{43}$ which is less than $1$.
The right child is always strictly greater than $1$.
Let $\frac{p}{q}$ is the parent, then the right child is $\frac{p+q}{q}$ which is greater than $\frac{q}{q}=1$.
For example, the right child of $\frac{20}{23}$ is $\frac{43}{23}$ which is greater than $1$.
Every vertex is the product of its childs.
For any node, the childs are $\frac{p}{q}$ are $\frac{p}{p+q}$ and $\frac{p+q}{q}$. And the clearly, the product of the children are $\frac{p}{p+q}\times \frac{p+q}{q}= \frac{p}{q}$.

Cool sequence Algorithm

This algorithm can be used to find the unique path from any given reduced fraction to $1/1$. Moreover, this algorithm also proves proposition. \begin{equation} \text{For any fraction } a/b, \text{ the parent is} \begin{cases} a/b-a & \text{if } b>a\\ a-b/b & \text{if } a>b \end{cases} \end{equation} For example, take any fraction, $\frac{13}{47}$ then the parent of $\frac{13}{47}$ is $\frac{13}{34}$. We will now trace it back to $1/1$ as all fractions originate from $1/1$. So we have $$13/47\rightarrow 13/34\rightarrow 13/21\rightarrow13/8 \rightarrow5/8\rightarrow5/3\rightarrow 2/3\rightarrow2/1\rightarrow1/1. $$
Let Cool sequence path denote the path which take any fraction $p/q$ to $1/1$.
Note that for any fraction which appears in the tree will have a unique parent and hence a unique cool sequence path. Hence, any fraction appearing in the cute tree appears only once. Now, we claim that any reduced fraction appears on this tree. However, note that our algorithm works for any reduced fraction.

More Properties

Number of elements in $n$th row is $2^{n-1}$.
We can prove this by induction. The base case is true. Suppose it's true for $k$th row, then by definition of $k+1$th row, the $k+1$th row will contain childs of $k$th row. Note that these childs will be unique and distinct by the first proposition, we get that the number of elements in the $k+1$th row is $2$ times the number of elements in the $k$th row, which by induction is $2^{k-1}$. And we are done.
The $i$th node from the left in any given row is the reciprocal of $i$th vertex from the right of the tree of that row.
We proceed with induction. True for the first row. Say it is true for the $k$th row. Then say the $i$th node from the left is $p/q$ and the $i$th node from the left is $q/p$. Then we consider the children. The right child of $p/q$ is the $2i-1$th from left in row $k+1$ and the left child of $q/p$ is the $2i-1$th from right in row $k+1$. However, The right child of $p/q$ is $p/p+q$ and the left child of $q/p$ is $q+p/p$, and both are reciprocal of each other. Similarly, the left child of $p/q$ and the right child of $q/p$ are the $2i$th element from left and right, respectively, in row $k+1$. And the left child of $p/q$ is $p/p+q$ and the right child of $q/p$ is $p+q/p$, which are clearly reciprocal of each other. And our hypothesis is true for $k+1$th row. So, we are done by induction!
The product of all the elements in a given row is $1$.
True for the first row. For any $k>1$th row, we get that there are even number of elements. Using the above proposition, we get that every $i$th element from the left can be paired with the $i$th element from the right. Note that both these elements are reciprocal of each other, and hence the product of them is $1$. And hence the product is $1$.
The $1$st node from the left in $n$th row is $1/n$ and the $1st$ node from right in $n$th row is $n/1$.
True for the first row. Say it is true for the $k$th row. Then the leftest node must be $1/k$ and rightest node is $k/1$. Note that the leftest node in the $k+1$th row is the left child of the leftest node in $k$th row. Hence it must be $1/(k+1)$. Similarly, we get that the rightest node in the $k+1$th row is the right child of the rightest node in $k$th row. Hence it must be $(k+1)/1$.
Sum of all elements in $n$th row is $3\cdot 2^{n-2}-\frac{1}{2}$.
We proceed with induction. It is true for $n=1$ row. Say it's true for $k$th row. Now consider the $k+1$ row. For any fraction, we know it's reciprocal is there. So for $a/b$ in the $k$th row, we know that $b/a$ is there too. We consider the children which are in the $k+1$th row and the sum. So we get $$a/(a+b)+(a+b)/b+b/(a+b)+(a+b)/a= 3+a/b+b/a.$$ Hence, we get the sum of elements in $k+1$th row is $$3\times 2^{k-2}+3\cdot 2^{k-2}-\frac{1}{2}=3\times 2^{k-1}-\frac{1}{2}.$$ And we are done by induction.

Binary preimage

Using our cool sequence algorithm, we showed that our function $f$ covers all positive rational numbers uniquely. Now, we will show that given any fraction, how we can find its preimage (which is obviously unique). Remember our Cool sequence algorithm? We will do the same thing, except now we will also care about the left and right child. For example, we know that $13/47$ is leftchild of $13/34$ and so on. So we get $$\frac{13}{47}\overset{\text{L}}{\rightarrow} \frac{13}{34}\overset{\text{L}}{\rightarrow} \frac{13}{21}\overset{\text{L}}{\rightarrow}\frac{13}{8} \overset{\text{R}}{\rightarrow}\frac{5}{8}\overset{\text{L}}{\rightarrow}\frac{5}{3}\overset{\text{R}}{\rightarrow}\frac{2}{3}\overset{\text{L}}{\rightarrow}\frac{2}{1}\overset{\text{R}}{\rightarrow}\frac{1}{1}. $$ We define a new function, $g(n)$ which is basically the same as $f(n)$ but we define $g(n)$ as the following.
Note that $$f(n)=g(2^{\log_2(n)}+2^{\log_2(n)+1}-1-n).$$ Note that if the number $g(n)$ is the parent, then its right child is $g(2n)$ and the left child is $g(2n+1)$. Now consider Now, consider the binary representation of $n,2n$ and $2n+1$. If the $n=(a_1a_2\dots a_k)_2$ then note that $2n=(a_1\dots a_k0)_2$ and $2n+1=(a_1\dots a_k1)_2$. So we add $1$ at the end of the binary reprsentation whenever we go to the left child and $0$ if right. Hence, for the above example, we start with $1/1$. Since $2/1$ is right child, we add $1$ to binary expression. Hence $(11)_2$. And we proceed like this. We get that $$13/47=g((110101000)_2)=g(424)=f(512+256-1-424)=f(343).$$ Note that, using our above results, we get that there is a bijection between naturals and positive rationals. And hence by our discussion in \textbf{section 1.2}, we get that there is a bijection between naturals and rational numbers. Hence, rationals are countable.

Connection with Euclidean algorithm

We consider $13/47$ as the example. Recall, we had $$\frac{13}{47}\overset{\text{L}}{\rightarrow} \frac{13}{34}\overset{\text{L}}{\rightarrow} \frac{13}{21}\overset{\text{L}}{\rightarrow}\frac{13}{8} \overset{\text{R}}{\rightarrow}\frac{5}{8}\overset{\text{L}}{\rightarrow}\frac{5}{3}\overset{\text{R}}{\rightarrow}\frac{2}{3}\overset{\text{L}}{\rightarrow}\frac{2}{1}\overset{\text{R}}{\rightarrow}\frac{1}{1}. $$ Note that $$47=3\times 13+8\text{ hence three times L}$$ $$13=1\times 8+5\text{ hence one time R}$$ $$8=1\times5+3\text{ hence one time L}$$ $$5=1\times 3+2\text{ hence one time R}$$ $$3=1\times 2+1\text{ hence one time L}$$ $$2=2\times 1+0$$ Note that at every step, our $L,R$ are alternating. This is because if $a=qb+r$ was say $L$, then that implies the fraction was $b/a$ and then after $qL$'s we get to $b/r$, but we have $b>r$ by euclidean algorithm. So we get that $b/r$ must be a right child. Hence they are alternating. Moreover, whenever we get the equation of the form $n=n\times 1+0$ at the end of the euclidean algorithm ( note that we are supposed to get this as the fractions are in reduced form), we write $n-1$ times the symbol. Hence, for our current example, we have $n-1=2-1=1$ times $R$. Since we can connect euclidean algorithm and finite continued fractions, we can also connect the fractions with finite continued fractions.

Address formula

Using the binary preimage, we can now figure out the actuall address for any fraction. For any fraction $a/b$, we figure out the $n$ such that $f(n)=a/b$. The the row $f(n)$ belongs to is ${[\log_2(n)]}+1$ as in the $k$th row, $f(2^{k-1}),\dots, f(2^{k}-1)$ are there. And then the fraction would be $n-2^{[\log_2(n)]}$th element from left.

Algebraic formula

We claim the following.
We have the following recursive formula $$f(n+1)=\dfrac{1}{[f(n)]+1-\{f(n)\}}$$ with $f(1)=1/1=1$.
We firstly simplify the formula.
Note that $$f(n+1)=\dfrac{1}{[f(n)]+1-\{f(n)\}}=\dfrac{1}{2[f(n)]+1-f(n)}.$$
As we have $f(n)=[f(n)]+\{f(n)\}$, we get that $$[f(n)]+1-\{f(n)\}=[f(n)]+1-(f(n)-[f(n)])=2[f(n)]+1-f(n).$$
Note that for any fraction $f(n+1)$ where $f(n+1)$ is the left child, we can say that $f(n+1)=\dfrac{1}{[f(n)]+1-\{f(n)\}}$.
For any fraction $f(n+1)$ where $f(n+1)$ is the left child, we can say that $f(n+1)=\dfrac{1}{2[f(n)]+1-f(n)}$
We get that the left child is $f(n)=\frac{x}{x+1}$ and right child is $f(n+1)=x+1$ for any vertex $x$. We have to show that $$\dfrac{1}{2[f(n)]+1-f(n)}=f(n+1)$$ or show that $$2f(n+1)[f(n)]+f(n+1)-f(n)f(n+1)=1.$$ But note that $f(n)$ is a left child, so we get that $2f(n+1)[f(n)]=0.$ Moreover, we get that $$f(n+1)-f(n)f(n+1)=x+1-x=1.$$ And we are done!
So our theorem holds true whenever $f(n)$ is a left child. Now, we see the case when $f(n)$ is the right child. Since $f(n)$ is the right child, we have $f(n+1)$ is the left child of some other parent. Since all fractions are getting generated by $1/1$, the fraction $f(n),f(n+1)$ must have same parent some rows ago. Let $a/b$ be that common parent fraction $k+1$ rows. Then note that $f(n)$ is generated by taking $k$ consecutive right childs after one left child from $a/b$ and $f(n+1)$ is generated by taking $k$ consecutive left child after one right child from $a/b$. Now, before proceeding further, we present a lemma.
For any number $x = p/q$, the rightmost child after $n$ rows is $(p + nq)/q = x + n$, and the leftmost child is $p/(np + q) = x/(nx + 1)$.
The proof is just induction. It is true for $n=1$ case. Say it is true for $n=k$. Then note that the right child of rightmost child in $k$th row is rightmost child in $k+1$th row. And right child is $(p+(k+1)q)/q=x+k+1$. And similarly for left child. And we are done by induction.
The left child of $a/b$ is $a/(a+b)$ and right child is $(a+b)/b$. As $f(n)$ is is generated by taking $k$ consecutive right childs after one left child from $a/b$, by above lemma, we have $$f(n)=a/(a+b)+k$$ and we have $$f(n+1)=[(a+b)/b]/[k(a+b)/b+1]$$ $$=(a + b)/(k(a + b) + b)=1/(k + b/(a+b)).$$ Now, note that $[f(n)]=k$. And hence we have $$f(n)-k=a/(a+b)\implies f(n)-[f(n)]=a/(a+b).$$ So note that $$f(n+1)=\frac{1}{1-a/(a+b)+k}=\frac{1}{1-f(n)+2k}=\frac{1}{1-f(n)+2[f(n)]}.$$ Hence, we prove for the right child too. I hope you liked reading it!

Comments

Post a Comment

Popular posts from this blog

Geometry ( Finally!!!)

 This is just such an unfair blog.  Like if one goes through this blog, one can notice how dominated  Algebra is!! Like 6 out of 9 blog post is Algebra dominated -_- Where as I am not a fan of Algebra, compared to other genres of Olympiad Math(as of now). And this was just injustice for Synthetic Geo. So this time , go geo!!!!!!!!!!!  These problems are randomly from A Beautiful Journey through Olympiad Geometry.  Also perhaps I will post geo after March, because I am studying combi.  Problem:  Let $ABC$ be an acute triangle where $\angle BAC = 60^{\circ}$. Prove that if the Euler’s line of $\triangle ABC$ intersects $AB$ and $AC$ at $D$ and $E$, respectively, then $\triangle ADE$ is equilateral. Solution:  Since $\angle A=60^{\circ}$ , we get $AH=2R\cos A=R=AO$. So $\angle EHA=\angle DOA.$ Also it's well known that $H$ and $O $ isogonal conjugates.$\angle OAD =\angle EAH.$ By $ASA$ congruence, we get $AE=AD.$ Hence $\triangle ADE$ is equilateral....

My experiences at EGMO, IMOTC and PROMYS experience

Yes, I know. This post should have been posted like 2 months ago. Okay okay, sorry. But yeah, I was just waiting for everything to be over and I was lazy. ( sorry ) You know, the transitioning period from high school to college is very weird. I will join CMI( Chennai Mathematical  Institue) for bsc maths and cs degree. And I am very scared. Like very very scared. No, not about making new friends and all. I don't care about that part because I know a decent amount of CMI people already.  What I am scared of is whether I will be able to handle the coursework and get good grades T_T Anyways, here's my EGMO PDC, EGMO, IMOTC and PROMYS experience. Yes, a lot of stuff. My EGMO experience is a lot and I wrote a lot of details, IMOTC and PROMYS is just a few paras. Oh to those, who don't know me or are reading for the first time. I am Sunaina Pati. I was IND2 at EGMO 2023 which was held in Slovenia. I was also invited to the IMOTC or International Mathematical Olympiad Training Cam...

Introduction

  Hey Everyone!! This is my first Blog post. So let me give a brief introduction about myself. I am Sunaina Pati. I love solving Olympiad math problems,  learning crazy astronomical facts , playing hanabi and anti-chess, listening to Kpop , love making diagrams in Geogebra and  teaching other people maths 😊 . I love geometry , number theory and Combinatorics . I am starting this blog to keep myself a bit motivated in doing studies 😎 . Right now, I am planning to write walkthroughs on some of the best problems I tried over the week which can refer for hints 'cause solutions contain some major spoilers and one learns a lot while solving the problem on his own rather than seeing solutions . Also, there will be some reviews about Kpop songs, study techniques, my day to day lifestyles,exam reviews and ofc some non-sense surprises 😂.  I am planning to  try  posting every week on Sundays or Saturdays ( most probably) ! Though there is no guarantee about when I ...

Problems I did this week [Jan8-Jan14]

Yeyy!! I am being so consistent with my posts~~ Here are a few problems I did the past week and yeah INMO going to happen soon :) All the best to everyone who is writing!  I wont be trying any new problems and will simply revise stuffs :) Some problems here are hard. Try them yourself and yeah~~Solutions (with sources) are given at the end! Problems discussed in the blog post Problem1: Let $ABC$ be a triangle whose incircle $\omega$ touches sides $BC, CA, AB$ at $D,E,F$ respectively. Let $H$ be the orthocenter of $DEF$ and let altitude $DH$ intersect $\omega$ again at $P$ and $EF$ intersect $BC$ at $L$. Let the circumcircle of $BPC$ intersect $\omega$ again at $X$. Prove that points $L,D,H,X$ are concyclic. Problem 2: Let $ ABCD$ be a convex quadrangle, $ P$ the intersection of lines $ AB$ and $ CD$, $ Q$ the intersection of lines $ AD$ and $ BC$ and $ O$ the intersection of diagonals $ AC$ and $ BD$. Show that if $ \angle POQ= 90^\circ$ then $ PO$ is the bisector of $ \angle AOD$ ...

Some problems in Olympiad Graph theory!

Hello there! It has been a long time since I uploaded a post here. I recently took a class at the European Girls' Mathematical Olympiad Training Camp 2024, held at CMI. Here are a few problems that I discussed! My main references were Po-Shen Loh's Graph theory Problem set (2008), Adrian tang's Graph theory problem set (2012) and Warut Suksompong's Graph Cycles and Olympiad Problems Handout and AoPS. I also referred to Evan Chen's Graph theory Otis Problem set for nice problems! Text Book Problems which are decent A connected graph $G$ is said to be $k$-vertex-connected (or $k$-connected) if it has more than $k$ vertices and remains connected whenever fewer than $k$ vertices are removed. Show that every $k$-connected graph of order atleast $2k$ contains a cycle of length at least $2k$. We begin with a lemma. Prove that a graph $G$ of order $n \geq 2k$ is $k$ connected then every 2 disjoint set $V_1$ and $V_2$ of $k$ distinct vertices each, there exist $k$...

Orders and Primitive roots

 Theory  We know what Fermat's little theorem states. If $p$ is a prime number, then for any integer $a$, the number $a^p − a$ is an integer multiple of $p$. In the notation of modular arithmetic, this is expressed as \[a^{p}\equiv a{\pmod {p}}.\] So, essentially, for every $(a,m)=1$, ${a}^{\phi (m)}\equiv 1 \pmod {m}$. But $\phi (m)$ isn't necessarily the smallest exponent. For example, we know $4^{12}\equiv 1\mod 13$ but so is $4^6$. So, we care about the "smallest" exponent $d$ such that $a^d\equiv 1\mod m$ given $(a,m)=1$.  Orders Given a prime $p$, the order of an integer $a$ modulo $p$, $p\nmid a$, is the smallest positive integer $d$, such that $a^d \equiv 1 \pmod p$. This is denoted $\text{ord}_p(a) = d$. If $p$ is a primes and $p\nmid a$, let $d$ be order of $a$ mod $p$. Then $a^n\equiv 1\pmod p\implies d|n$. Let $n=pd+r, r\ll d$. Which implies $a^r\equiv 1\pmod p.$ But $d$ is the smallest natural number. So $r=0$. So $d|n$. Show that $n$ divid...

Solving Random ISLs And Sharygin Solutions! And INMO happened!!

Some of the ISLs I did before INMO :P  [2005 G3]:  Let $ABCD$ be a parallelogram. A variable line $g$ through the vertex $A$ intersects the rays $BC$ and $DC$ at the points $X$ and $Y$, respectively. Let $K$ and $L$ be the $A$-excenters of the triangles $ABX$ and $ADY$. Show that the angle $\measuredangle KCL$ is independent of the line $g$ Solution: Note that $$\Delta LDK \sim \Delta XBK$$ and $$\Delta ADY\sim \Delta XCY.$$ So we have $$\frac{BK}{DY}=\frac{XK}{LY}$$ and $$\frac{DY}{CY}=\frac{AD}{XC}=\frac{AY}{XY}.$$ Hence $$\frac{BK}{CY}=\frac{AD}{XC}\times \frac{XK}{LY}\implies \frac{BK}{BC}=\frac{CY}{XC}\times \frac{XK}{LY}=\frac{AB}{BC}\times \frac{XK}{LY} $$ $$\frac{AB}{LY}\times \frac{XK}{BK}=\frac{AB}{LY}\times \frac{LY}{DY}=\frac{AB}{DL}$$ $$\implies \Delta CBK\sim \Delta LDK$$ And we are done. We get that $$\angle KCL=360-(\angle ACB+\angle DKC+\angle BCK)=\angle DAB/2 +180-\angle DAB=180-\angle DAB/2$$ Motivation: I took a hint on this. I had other angles but I did...

Let's complex bash Part 1

I have to learn complex bash. And almost everyone knows that I am notes taking girl so thought why not make a post on complex bash ( so that I don't get emotionally demotivated lol).😇 There wasn't any need for learning complex bash, but it was in my dream checklist i.e " To learn a bash." And since I am not loaded with exams, I think it's high time to learn Bash and new topics.  Also if anyone from the "anti-bash" community is reading, sorry in advance and R.I.P.  Notes:- 1. Complex numbers are of the form $z=a+ib,$ where $a$ and $b$ are real numbers and $i^2=-1.$ 2. In polar form, $z=r(\cos \theta+~~i\sin\theta)=~~re^{i\theta},$ where $r=~~|z|=~~\sqrt{a^2+b^2},$ which is called the magnitude. 3. Here we used euler's formula i.e $\cos \theta+~~i\sin\theta=~~e^{i\theta}.$ 4. The $\theta $ is called the argument of $z,$ denored $\arg z.$ ( $\theta$ can be considered in $\mod 360$ and it is  measured anti-clockwise). 5. The complex conjugate of $z$ is ...

IMO 2023 P2

IMO 2023 P2 Well, IMO 2023 Day 1 problems are out and I thought of trying the geometry problem which was P2.  Problem: Let $ABC$ be an acute-angled triangle with $AB < AC$. Let $\Omega$ be the circumcircle of $ABC$. Let $S$ be the midpoint of the arc $CB$ of $\Omega$ containing $A$. The perpendicular from $A$ to $BC$ meets $BS$ at $D$ and meets $\Omega$ again at $E \neq A$. The line through $D$ parallel to $BC$ meets line $BE$ at $L$. Denote the circumcircle of triangle $BDL$ by $\omega$. Let $\omega$ meet $\Omega$ again at $P \neq B$. Prove that the line tangent to $\omega$ at $P$ meets line $BS$ on the internal angle bisector of $\angle BAC$. Well, here's my proof, but I would rather call this my rough work tbh. There are comments in the end! Proof Define $A'$ as the antipode of $A$. And redefine $P=A'D\cap (ABC)$. Define $L=SP\cap (PDB)$.  Claim1: $L-B-E$ collinear Proof: Note that $$\angle SCA=\angle SCB-\angle ACB=90-A/2-C.$$ So $$\angle SPA=90-A/2-C\implies \ang...

Reflecting on past

INMO Scores are out!! I am now a two times INMO awardee :) I got 16|0|1, so 17 in total! Yes, 16 in P1 T_T. I was thinking I would lose marks because of the way I wrote.  Lemme tell ya'll what happened that day but first I should share a few thoughts I had before the exam. My thoughts Honestly, my preparation for INMO was bad. In fact, I should say I didn't work hard at all. As I have said earlier, I had lost all my hopes for INMO and Olympiads as a whole after EGMO TSTs happened.  Art by Jelena Janic EGMO TSTs i.e European Girl's Mathematical Olympiad Team selection Tests 2022.  Literally my thoughts after EGMO TSTs I feel very ashamed to share but I got 1 mark in my EGMO TSTs. Tests in which I literally gave my whole life. I did so many ISLs ( like SO MANY), I mocked EGMO 2021 TST where my score was 28/42 and I perfected Day 2. 1 mark in the TST just showed my true potential. There are way better people than me in olys. A friend even said to me, "If I wouldn't...