Problems I did this week #1[Jan1-Jan8]

 Random thoughts but I think these days I am more into Rock? Like not metal rock but pop/indie rock. Those guitars, drums, vocals everything just attracts me. 

The Rose, TXT, N.Flying, The western ghats, Seventeen, Enhypen and Woosung are my favourites currently. 

My current fav songs are:

Oki a few problems I did this week!

Tuymaada 2018 Junior League/Problem 2

A circle touches the side $AB$ of the triangle $ABC$ at $A$, touches the side $BC$ at $P$ and intersects the side $AC$ at $Q$. The line symmetrical to $PQ$ with respect to $AC$ meets the line $AP$ at $X$. Prove that $PC=CX$.

Proof: Note that $$\angle CPX=\angle APB=\angle AQP=\angle XQC\implies PQCX\text{ is cyclic}.$$ So $$\angle XPC=\angle AQP=\angle CXP.$$ We are done.

EGMO 2020 P1

The positive integers $a_0, a_1, a_2, \ldots, a_{3030}$ satisfy $$2a_{n + 2} = a_{n + 1} + 4a_n \text{ for } n = 0, 1, 2, \ldots, 3028.$$

Prove that at least one of the numbers $a_0, a_1, a_2, \ldots, a_{3030}$ is divisible by $2^{2020}$.

Proof: Well, note that $$2|a_1,\dots,a_{3029}\implies 4|a_2,\dots,a_{3028} \dots \implies 2^{2020}|a_{1010}.$$

TSTST 2021/P1 

Let $ABCD$ be a quadrilateral inscribed in a circle with center $O$. Points $X$ and $Y$ lie on sides $AB$ and $CD$, respectively. Suppose the circumcircles of $ADX$ and $BCY$ meet line $XY$ again at $P$ and $Q$, respectively. Show that $OP=OQ$.

Proof: Let $BQ \cap (ABCD)=M$, $DP\cap  (ABCD)=N$, $BQ\cap DP=Z$. 

Note that $$\angle BQY=\angle BAD=\angle BXD\implies QP||MD.$$ Similarly, we have $$BN||QP\implies BM=DN.$$

We also have $$\angle BQY=180-\angle XPD\implies LQ=LP\implies L\in \text{ perpendicular bisector of } QP.$$

So we have $L\in \text{ perpendicular bisector of } MD,BN.$ But $O\in \text{ perpendicular bisector of } MD,BN.$

So $OL$ is perpendicular bisector of $QP$.

Iran TST 2007 Day 2

Let $\omega$ be incircle of $ABC$. $P$ and $Q$ are on $AB$ and $AC$, such that $PQ$ is parallel to $BC$ and is tangent to $\omega$. $AB,AC$ touch $\omega$ at $F,E$. Prove that if $M$ is midpoint of $PQ$, and $T$ is intersection point of $EF$ and $BC$, then $TM$ is tangent to $\omega$

Proof: Define $X$ as the tangency point from $T$ to $\omega$. Note that $(X,D;F,E)=-1\implies A-X-D$.  Define $D'$ as the antipode of $D$. So we have $\angle D'XD=90$. Define $Y'=AX\cap PQ$. We will show that $MD'=MX=MY$. Note that $\omega$ is the excircle of $\Delta APQ$, so $D'$ is the extouch point. And by homothety, $Y$ is the in-touch point. Hence $YM=MD'\implies MX=MD'$.

USAMO 2007 P1

Let $n$ be a positive integer. Define a sequence by setting $a_{1}= n$ and, for each $k > 1$, letting $a_{k}$ be the unique integer in the range $0\leq a_{k}\leq k-1$ for which $a_{1}+a_{2}+...+a_{k}$ is divisible by $k$. For instance, when $n = 9$ the obtained sequence is $9,1,2,0,3,3,3,...$. Prove that for any $n$ the sequence $a_{1},a_{2},...$ eventually becomes constant.

Proof: Define $a_1+a_2+\dots+a_k=k\times b_k$.

Claim: $b_i\ge b_{i+1}$

Proof: $$(i+1)b_{i+1}-ib_i\le i\implies (i+1)b_{i+1}\le i(b_i+1)\implies b_{i}+1>b_{i+1}.$$

Note that $\exists k$ such that $a_1+a_2+\dots+a_k=mk$ where $m\le k$ then $m=a_{k+1}=a_{k+2}=\dots$

Now the sequence $<b_i>$ is non decreasing and sequence $<i>$ is increasing. So $\exists l$ such that $b_i\le l$ and we are done. 

USAMO 2001 P4

Let $P$ be a point in the plane of triangle $ABC$ such that the segments $PA$, $PB$, and $PC$ are the sides of an obtuse triangle. Assume that in this triangle the obtuse angle opposes the side congruent to $PA$. Prove that $\angle BAC$ is acute.

Proof: Note that by Ptolemy, we have $$(AB\cdot PC)+(PB\cdot AC)\ge AP\cdot BC\implies (AB\cdot PC+PB\cdot AC)^2\ge AP^2\cdot BC^2.$$

By CS inequality, we have $$(AC^2+AB^2)(PB^2+PC^2)\ge  (AB\cdot PC+PB\cdot AC)^2.$$

Since obtuse angle, we have $$PB^2+PC^2<AP^2\implies AC^2+AB^2>BC^2$$

which shows $\angle BAC$ is acute.

USAMO 2001 P5

Let $S$ be a set of integers (not necessarily positive) such that

(a) there exist $a,b \in S$ with $\gcd(a,b)=\gcd(a-2,b-2)=1$;

(b) if $x$ and $y$ are elements of $S$ (possibly equal), then $x^2-y$ also belongs to $S$.

Prove that $S$ is the set of all integers.

Proof: We begin with the following claim.

Claim: $((a^2-a)^2-a^2,(b^2-b)^2-b^2,a^2-b^2)=1$

Proof: If $$p|(a^4-2a^3,b^4-2b^3,a^2-b^2\implies p|a^3(a-2),p|b^3(b-2),p|(a+b)(a-b).$$

Note that $p\ne 2$ as $(a,b)=1$. So if $p|a^3(a-2)\implies$ $p|a$ or $p|a-2$. WLOG $p|a\implies p|b-2$. So $p|a-b+2,p|a+b-2$. But $p|a+b$ or $p|a-b$. This forces $p=2$.

Claim: if $m,n,c\in S$ then $k(m^2-n^2)+c\in S\forall k\in \Bbb{Z}$.

Proof: $$m^2-c\in S, n^2-c\in S\implies m^2-[n^2-c]\in S$$

And we can go on.

By bezouts $\exists$ $I_1,I_2,I_3\in \Bbb{Z}$ such that $$I_1((a^2-a)^2-a^2)+I_2((b^2-b)^2-b^2)+I_3(a^2-b^2)=\pm 1$$

Since $c\in S$ we get $I_1((a^2-a)^2-a^2)+I_2((b^2-b)^2-b^2)+I_3(a^2-b^2)\in S$. This will cover all integers.  

Generalised USAMO 2000 P4

Find the smallest positive integer $m$ such that if $n$ squares of a $n \times n$ chessboard are colored, then there will exist three colored squares whose centers form a right triangle with sides parallel to the edges of the board.

Proof: The answer is $2(n-1)+1$.

The construction for $2(n-1)$ is easy. 

Suppose not. Then $\exists 2(n-1)+1$ cells, which when coloured, we do not get a right triangle. Now, we count the number of pairs of cells $[(x_1,y_1),(x_2,y_2)]$ such that $x_1\ne x_2$ and $y_1\ne y_2$. Call such pairs "good pairs".

Note that if $(x_1,y_1),(x_2,y_2)$ are coloured then we cannot have $(x_1,y_2),(x_2,y_1)$ coloured. 

Note the number of non-coloured cells $\ge \text{ the number of good pairs }+1$ because any good pair will give rise to at least one new cell which is not coloured. 

Note that for any cell in the $2(n-1)+1$ cells will form a good pair with at least $n-1$ other cells [because in worst case max $n-1$ cells share same row/colum, we can't more else we will get a right triangle]

So $$\text{ the number of good pairs }\ge \frac{(2n-1)(n-1)}{2}.$$

Note that $$n^2=\text{ no of non-coloured }+ \text{ coloured cells }$$

So $$n^2\ge \frac{(2n-1)(n-1)}{2}+1+2n-1>(n-1)^2+1+2n-1=n^2+1$$

Not possible.