Skip to main content

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.

Comments

Popular posts from this blog

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$ ...

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....

Just spam combo problems cause why not

This post is mainly for Rohan Bhaiya. He gave me/EGMO contestants a lot and lots of problems. Here are solutions to a very few of them.  To Rohan Bhaiya: I just wrote the sketch/proofs here cause why not :P. I did a few more extra problems so yeah.  I sort of sorted the problems into different sub-areas, but it's just better to try all of them! I did try some more combo problems outside this but I tried them in my tablet and worked there itself. So latexing was tough. Algorithms  "Just find the algorithm" they said and they died.  References:  Algorithms Pset by Abhay Bestrapalli Algorithms by Cody Johnson Problem1: Suppose the positive integer $n$ is odd. First Al writes the numbers $1, 2,\dots, 2n$ on the blackboard. Then he picks any two numbers $a, b$ erases them, and writes, instead, $|a - b|$. Prove that an odd number will remain at the end.  Proof: Well, we go $\mod 2$. Note that $$|a-b|\equiv a+b\mod 2\implies \text{ the final number is }1+2+\dots ...

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...

Problems with meeting people!

Yeah, I did some problems and here are a few of them! I hope you guys try them! Putnam, 2018 B3 Find all positive integers $n < 10^{100}$ for which simultaneously $n$ divides $2^n$, $n-1$ divides $2^n - 1$, and $n-2$ divides $2^n - 2$. Proof We have $$n|2^n\implies n=2^a\implies 2^a-1|2^n-1\implies a|n\implies a=2^b$$ $$\implies 2^{2^b}-2|2^{2^a}-2\implies 2^b-1|2^a-1\implies b|a\implies b=2^c.$$ Then simply bounding. USAMO 1987 Determine all solutions in non-zero integers $a$ and $b$ of the equation $$(a^2+b)(a+b^2) = (a-b)^3.$$ Proof We get $$ 2b^2+(a^2-3a)b+(a+3a^2)=0\implies b = \frac{3a-a^2\pm\sqrt{a^4-6a^3-15a^2-8a}}{4}$$ $$\implies a^4-6a^3-15a^2-8a=a(a-8)(a+1)^2\text{ a perfect square}$$ $$\implies a(a-8)=k^2\implies a^2-8a-k^2=0\implies \implies a=\frac{8\pm\sqrt{64+4k^2}}{2}=4\pm\sqrt{16+k^2}. $$ $$ 16+k^2=m^2\implies (m-k)(m+k)=16.$$ Now just bash. USAMO 1988 Suppose that the set $\{1,2,\cdots, 1998\}$ has been partitioned into disjoint pairs $\{a_i,b_i\}$ ($1...

IMO Shortlist 2021 C1

 I am planning to do at least one ISL every day so that I do not lose my Olympiad touch (and also they are fun to think about!). Today, I tried the 2021 IMO shortlist C1.  (2021 ISL C1) Let $S$ be an infinite set of positive integers, such that there exist four pairwise distinct $a,b,c,d \in S$ with $\gcd(a,b) \neq \gcd(c,d)$. Prove that there exist three pairwise distinct $x,y,z \in S$ such that $\gcd(x,y)=\gcd(y,z) \neq \gcd(z,x)$. Suppose not. Then any $3$ elements $x,y,z\in S$ will be $(x,y)=(y,z)=(x,z)$ or $(x,y)\ne (y,z)\ne (x,z)$. There exists an infinite set $T$ such that $\forall x,y\in T,(x,y)=d,$ where $d$ is constant. Fix a random element $a$. Note that $(x,a)|a$. So $(x,a)\le a$.Since there are infinite elements and finite many possibilities for the gcd (atmost $a$). So $\exists$ set $T$ which is infinite such that $\forall b_1,b_2\in T$ $$(a,b_1)=(a,b_2)=d.$$ Note that if $(b_1,b_2)\ne d$ then we get a contradiction as we get a set satisfying the proble...

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...

Some random problems

  I know, I know. Different font indeed. I have deleted a few of my MSE answers. I felt they weren't that good in quality. And a few questions are from my prev aops account which I have deactivated now. I also have posted 10 IOQM types of problems. These can be used while preparing for IOQM. Problem: Prove that $\dfrac{ab}{c^3}+\dfrac{bc}{a^3}+\dfrac{ca}{b^3}> \dfrac{1}{a}+\dfrac{1}{b}+\dfrac{1}{c}$, where $a,b,c$  are different positive real numbers.  Proof: Note that by AM-GM $$\frac{ab}{c^3}+\frac{bc}{a^3}\ge \frac{2b}{ac}$$ and we also have $$\frac {b}{ac}+\frac{c}{ab}\ge \frac{2}{a}$$. Hence, $$\sum_{cyc}\frac{ab}{c^3}\ge\sum_{cyc}\frac{b}{ac}\ge\sum_{cyc}\frac{1}{a}$$ where everything we got is by applying AM-GM on $2$ terms and then dividing by $2$. USA TST 2007: Triangle $ABC$ which is inscribed in circle $\omega$. The tangent lines to $\omega$ at $B$ and $C$ meet at $T$. Point $S$ lies on ray $BC$ such that $AS$ is perpendicular to $AT$. Points $B_1$ and $C_1...

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...