Wrapping up year 2022 with a few problems I did in the past week 
Edge colouring with $n$ colours $K_n$
Prove that if the edges of $K_n$ are coloured with $n$ colours, then some triangle has its edges of different colours.
Proof: We use induction. For $n=3$ it is true. Now, suppose it is true for $n=1,\dots, l$. We will show it is true for $n=l+1$. Now, consider $k_{l+1}$ with vertex $v_1,\dots,v_{l+1}$. Consider the $k_l$ with vertex $v_2,\dots, v_{l+1}$. Now note that the colours used in that $k_l$ are max $l-1$ colours (since by induction, if $l$ colours then we get a triangle with the property given.)
But since $l+1$ colours are used, at least two of the edges $v_1v_2,v_1v_3,\dots v_{l+1}$ are coloured with $2$ colours which are not used in $k_{l}$. WLOG say $v_1v_2,v_1v_3$, then $v_1v_2v_3$ is a triangle with edges of diff colour.
Russia 2011 Grade 10 P6
Given is an acute triangle $ABC$. Its heights $BB_1$ and $CC_1$ are extended past points $B_1$ and $C_1$. On these extensions, points $P$ and $Q$ are chosen, such that angle $PAQ$ is right. Let $AF$ be the height of triangle $APQ$. Prove that angle $BFC$ is a right angle.
Proof: Note that $AEC_1Q$ and $AEB_1P$ cyclic.
Claim: $C_1FB_1C$, $C_1FB_1A$ cyclic
Proof: $$180-\angle C_1EB_1=\angle QEC_1+\angle PEB_1=\angle QPC_1+\angle PAB_1=90-A=\angle C_1CB_1.$$
And we get $F\in (BC_1B_1C)\implies \angle BFC=90$.
Russia 2011 Grade 10 P2
On side $BC$ of parallelogram $ABCD$ ($A$ is acute) lies point $T$ so that triangle $ATD$ is an acute triangle. Let $O_1$, $O_2$, and $O_3$ be the circumcenters of triangles $ABT$, $DAT$, and $CDT$ respectively. Prove that the orthocenter of triangle $O_1O_2O_3$ lies on line $AD$.
Proof: Define $H$ as the orthocenter of $O_1O_2O_3$. Note that $$\angle O_2O_3T=\angle O_2O_1T\implies T\in (O_1O_2O_3)$$
Define $M,N$ as midpoints of $AT,DT$. Note that $MN$ is the simson line for $\Delta O_1O_2O_3$ and $T$. Since $H$ is the orthocenter, we get $MN$ bisects $HT$. But we have homothety at $T$ sending $M$ to $A$ and $N$ to $D$. Hence $H\in AD$. And we are done.
Additionally, since $O_2O_3\perp DT,O_1O_2\perp AT$ we have $$HO_1|| DT, HO_3||AT\implies \angle O_1HO_3=\angle DTA.$$
Polynomial in OLY-PD posted by Atul
Determine the set of all polynomials $P(x)$ with real coefficients such that the set $\{P(n) | n \in \mathbb{Z}\}$ contains all integers, except possibly finitely many of them.
Solved with Sid and Malay!
Proof: We claim that $P(x)=(x+k)/b, k,b\in \Bbb{Z}$ is the only solution.
By Lagrange interpolation construction, we get coefficients of $P(x)\in \Bbb{Q}$. If $P$ have degree greater than $2$, $|P(x+1)-P(x)|$ will eventually be greater than $1$ and start skipping infinitely many integers. Hence $P$ is linear.
Let $P(x)=\frac{ax}{d}+\frac{c}{d}$ with $\gcd(a,c,d)=1$. If $a\ne \pm 1$ then consider prime $p|a$. So $d|ax+c$. So if $p|d\implies p|c$ not possible. So $P(x)\equiv \frac{c}{d}=k\mod p$ for a fixed $k\in \Bbb{Z}_p$ which doesn’t cover infinite integers.
So $P(x)=\frac{x+c}{d}$ is the only solution.
EGMO 2019 P3
Let $ABC$ be a triangle such that $\angle CAB > \angle ABC$, and let $I$ be its incentre. Let $D$ be the point on segment $BC$ such that $\angle CAD = \angle ABC$. Let $\omega$ be the circle tangent to $AC$ at $A$ and passing through $I$. Let $X$ be the second point of intersection of $\omega$ and the circumcircle of $ABC$. Prove that the angle bisectors of $\angle DAB$ and $\angle CXB$ intersect at a point on line $BC$.
Solved with Krutarth and Malay!
Proof: Define $Y=\omega \cap AD$, $Z=\omega\cap AB$, $M=$ midpoint of arc $AB$ ( not containing $C$), $N=$ midpoint of arc $CB$ ( not containing $A$), $K=AD\cap (ABC)$, $S=$ incenter of $\Delta ABK$.
Claim: $YZ||BC$
Proof: Note that $\angle B=\angle YAC=\angle YZA\implies YZ||BC.$
Claim: $C-Y-X$
Proof: Note that $\angle CXA=\angle B=\angle YZA=\angle YXA.$
Claim: $S\in BC$
Proof: Note that $C$ is the midpoint of arc $KA$. By Fact 5, $S\in BC$.
Claim: $AISB$ cyclic
Proof: Note that $M$ is the centre of $AIB$ and $M$ is also the centre of $ASB$. So $MA=MI=MS=MB$.
Claim: $I-Y-S$ collinear
Proof: Note that$$\measuredangle AIY=\measuredangle YZA=\measuredangle SBA.$$
Now using pascal on $MCXNAK$, we get $S=NX\cap MK$. So $XS$ bisects $\angle CBX$. And we are done!
EGMO 2021 P1
The number 2021 is fantabulous. For any positive integer $m$, if any element of the set $\{m, 2m+1, 3m\}$ is fantabulous, then all the elements are fantabulous. Does it follow that the number $2021^{2021}$ is fantabulous?
Proof: We begin with the claim.
Claim: If $2021$ is fabulous then so is $1$.
Proof: If not, then let the least element be $k$. We take cases.
Case 1: If $k$ is even
Then $$2k+1\leftrightarrow 6k+3\leftrightarrow 3k+1\leftrightarrow \frac{3k}{2}\leftrightarrow \frac{m}{2}$$ is fantabulous.
Case 2:If $k$ is odd
Then $\frac{k-1}{2}$ is fantabulous.
Claim: If $1$ is fantabulous then so is every number.
We do induction. Say $1,2,\dots,n$ is fantabulous. We will show that $n+1$ is also fantabulous. But this is just similar to our above claim’s proof ( we can simply back track stuff stuff)
And yey!
Russia 2015 Grade 11 P7
A scalene triangle $ABC$ is inscribed within circle $\omega$. The tangent to the circle at point $C$ intersects line $AB$ at point $D$. Let $I$ be the center of the circle inscribed within $\triangle ABC$. Lines $AI$ and $BI$ intersect the bisector of $\angle CDB$ in points $Q$ and $P$, respectively. Let $M$ be the midpoint of $QP$. Prove that $MI$ passes through the middle of arc $ACB$ of circle $\omega$.
Proof: $ABPQ$ is cyclic ( simple angles.) Define $M_A,M_B$ as arc midpoints. So we have $$\angle APQ=\angle ABQ=\angle ABI=\angle B/2=\angle AM_AM_B\implies M_AM_B||PQ.$$
If $N$ is midpoint of $M_AM_B$ $\implies I-M-N$ collinear. Define $S$ as the midpoint of arc.
Claim: $IM_BM_AS$ is parallelogram.
Proof: Note that $M_BM_A||SC$ (As $IC\perp SC, IC\perp M_AM_B$). So $M_BS=M_AC=M_AI$. Moreover, we have $\Delta M_BIM_A$ congruent to $\Delta M_BCM_A$. So we have $M_BI=M_BC=M_AS$.
Done!
Russia 2022 Grade 11 P1
We call the $main$ $divisors$ of a composite number $n$ the two largest of its natural divisors other than $n$. Composite numbers $a$ and $b$ are such that the main divisors of $a$ and $b$ coincide. Prove that $a=b$.
Proof: Let $a=p_1^{\alpha_1}\dots p_k^{\alpha_2}$ and $b=q_1^{\beta_1}\dots q_l^{\beta_l}$.
Note that if $a$ or $b$ is a prime then clearly we are done. So supposed neither $a,b$ is prime.
Since$$\frac{a}{p_1}=\frac{b}{q_1}\implies p_1^{\alpha_1-1}\dots p_k^{\alpha_2}=q_1^{\beta_1-1}\dots q_l^{\beta_l}.$$
Claim: If $\alpha_1-1,\beta-1>0$ then $p_1=q_1$ which forces $a=b$.
Proof: If not wlog $p_1<q_1$ but $p_1|b$. Contradiction as then the biggest divisor would be $\frac{b}{p_1}$ and not $\frac{b}{q_1}$.
So either $\alpha_1-1, \beta-1$ is $0$. Wlog say $\alpha_1=1$ Then the next largest divisor is$$\frac{a}{p_2},\frac{b}{x}\implies p_1|\frac{a}{p_2}\implies p_1|\frac{b}{x}\implies p_1|b.$$
If $p_1\ne q_1$ then$$v_{p_1}(a/p_1)=0\ne v_{p_1}(b/q_1)\implies \frac{a}{p_1}\ne\frac{b}{q_1}.$$So $p_1=q_1$ and hence $a=b$.
Pumac 2019 A1
A finite graph $G$ is drawn on a blackboard. The following operation is permitted: pick any cycle $C$ of $G$, draw a new vertex $v$, connect it to all vertices of $C$, and finally erase all the edges of $C$. Prove that this operation can only be done a finite number of times.
Proof: Note that if $G$ is connected then even after we do the operation the number of edges will be same and the new graph is still connected.. look at e-v, for any n vertex, the connected graph must have atleast $n-1$ edges.. so this will stop eventually..
If $G$ is not connected, then consider the components, whenever we do the operation, the connected components still remain connected.. and the number of edges are same.. use the same argument.
ISL 2004 C3
ISL 2021 G4
Russia 2018 10.2
Indian TST D1 P2 (Practice Test)
The Euler Circuit Theorem
Now, we merge all these cycles.
Say we have a cycle, $V_1\rightarrow V_2\rightarrow \dots \rightarrow V_k\rightarrow V_1$ and we have another cycle, $V_i\rightarrow D_1\rightarrow \dots \rightarrow D_k\rightarrow V_i.$
$$V_1\rightarrow V_2\rightarrow \dots V_{i-1}\rightarrow V_i\rightarrow D_1\rightarrow \dots \rightarrow D_k\rightarrow V_i\rightarrow \dots V_k\rightarrow V_1$$
