Sunaina thinks absurd

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

  Today we shall try IMO Shortlist $2022$ C1. A $\pm 1$-sequence is a sequence of $2022$ numbers $a_1, \ldots, a_{2022},$ each equal to either $+1$ or $-1$. Determine the largest $C$ so that, for any $\pm 1$-sequence, there exists an integer $k$ and indices $1 \le t_1 < \ldots < t_k \le 2022$ so that $t_{i+1} - t_i \le 2$ for all $i$, and$$\left| \sum_{i = 1}^{k} a_{t_i} \right| \ge C.$$ We claim that the answer is $\boxed{506}$. $506$ is the upper bound. Just consider the sequence $$+1,-1,-1,+1,+1,-1,-1,+1\dots,-1,-1,+1,+1,-1.$$ Here $1, -1, -1, 1$ is repeated $505$ times and $1,-1$ is concatted to it. Now,our sequence would be $a_1,a_3,a_4,a_5,a_7,\dots$ which on summing would give $506$. And clearly, this would give the upper bound. Now, we show that $506$ is attainable by every sequence. WLOG there are at least $1011$ positive numbers in the sequence. Then we choose $+1$ whenever we can. Let the sequence be $c_1,b_1,\dots, c_n,b_n$ where $c_i$ are ...

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

 These problems are INMO~ish level. So trying this would be a good practice for INMO!  Let $ABCD$ be a quadrilateral. Let $M,N,P,Q$ be the midpoints of sides $AB,BC,CD,DA$. Prove that $MNPQ$ is a parallelogram. Consider $\Delta ABD$ and $\Delta BDC$ .Note that $NP||BD||MQ$. Similarly, $NM||AC||PQ$. Hence the parallelogram. In $\Delta ABC$, $\angle A$ be right. Let $D$ be the foot of the altitude from $A$ onto $BC$. Prove that $AD^2=BD\cdot CD$. Note that $\Delta ADB\sim \Delta CDA$. So by similarity, we have $$\frac{AD}{BD}=\frac{CD}{AD}.$$ In $\Delta ABC$, $\angle A$ be right. Let $D$ be the foot of the altitude from $A$ onto $BC$. Prove that $AD^2=BD\cdot CD$. Let $D\in CA$, such that $AD = AB$.Note that $BD||AS$. So by the Thales’ Proportionality Theorem, we are done! Given $\Delta ABC$, construct equilateral triangles $\Delta BCD,\Delta CAE,\Delta ABF$ outside of $\Delta ABC$. Prove that $AD=BE=CF$. This is just congruence. N...

Such a cute problem, although again, swapping the sum is hard.. I should practice more in that area :( Solved with Sidharth and Malay! Problem[2021 China TST 3/2/4] Prove that $$ \sum_{m=1}^n5^{\omega (m)} \le \sum_{k=1}^n\lfloor \frac{n}{k} \rfloor \tau (k)^2  \le \sum_{m=1}^n5^{\Omega (m)} .$$ Proof: Note that the middle term can be manipulated and written as $$\sum_{k=1}^n\lfloor \frac{n}{k} \rfloor \tau (k)^2= \sum_{k=1}^{n}\sum_{dk\le n}1 \tau(k)^2=\sum_{m=1}^n\sum_{k|m}\tau(k)^2$$ Since $\tau (k)$ is multiplicative, we get that $\tau(k)^2$ is multiplicative. Hence $F(m)= \sum_{k|a}\tau(k)^2$ is multiplicative too. ( As it's $1* \tau(k)^2$) Now, we begin our claim which proves the problem. Claim: $5^{\omega(a)}\le \sum_{k|a}\tau(k)^2\le 5^{\Omega(a)}$ Proof: Note that these symbols are multiplicative, we just have to check for primes. For primes $p^b$, $$5^{\omega(p^b)}\le \sum_{k|p^b}\tau(k)^2\le 5^{\Omega(p^b)}$$ Or showing $$5 \le \frac{(b+1)(b+2)(2b+3)}{6} \le 5^b$$ which...

Yeyy finally! I got time! I am so happy that I am finally going to read the analytic theory! However, I have added some CS stuff. Not sure if they are accurate. I have taken up CS in school so hopefully, it's correct!  Big $O$ notation:  We say $f(x)=O(g(x))$ if there exists $c$ such that $|f(x)|< c(g(x)$ for all $x\ge x_0$. Arithmetic of Big $O$ notation: $O(f(x))+O(g(x))= O(f(x)+g(x))$. Moreover, if $f(x)=O(g(x))\implies O(f(x)+g(x))=O(g(x)) $ $O(f(x))\times O(g(x))= O(f(x)\cdot g(x))$ $O(f(x)) - O(g(x))= O(f(x) +g(x))$ ( Yes, it is "+") $O(\int f(x) dx)=\int O(f(x) dx$ I want to dive into the CS part; it looks pretty nice and attractive :p. Introduction In CS, it is important to measure the efficiency of the algorithm before applying it on a big size of data. The "performance" depends on internal and external factors. Internal factors ( which we care more) specify the algorithm's efficiency in terms of: Time required to run and Space required to run....

 OMG Prime number theorem!!! I actually loved it! So today I solved a quite fancy NT problem with other people's help though! Problem : Prove that there exists an interval of the $[n^2,(n+1)^2]$ which contains at least $1000$ primes. Proof 1 : By PNT, if $n$ is large enough $$\pi(n) ~ \frac{n}{\log(n)}$$ So $$f(n)=\pi( {n+1}^2)-\pi( n^2) = \frac{(n+1)^2}{\log({n+1}^2)}- \frac{n^2}{\log(n^2)}$$ $$= \frac{(n+1)^2}{2\log({n+1})}- \frac{n^2}{2\log(n)}$$ Then $$f'(n)= \frac{(2n+2)\log(n+1)-(n+1)}{2[\log(n+1)]^2}-\frac{2n\log(n)-n}{2[\log(n)]^2}$$ $$=\frac{n+1}{\log(n+1)}+\frac{n}{2[\log(n)]^2}- (\frac{n}{\log(n)}+\frac{n+1}{2[\log(n+1)]^2})$$ Take  $$h(x)= \frac{(x)}{\log(x)}, g(x)=\frac{x}{2\log^2(x)}$$ we have basically $$(h(n+1)-h(n))>>>( g(n+1)-g(n)) $$ since $h$ grows faster than $g$ we have  $$h(n+1)-h(n) > (g(n+1)-g(n)$$ for large enough $n$. Infact $f'(n)$ is strictly increasing. Now, by MVT, note that there exist $t_1$ such that $$f(2)-f(1)=f'(t_1), t...

 Well, I am finally free! It's more like I was busy with classes and covering up the NT4 course, dang it is hard! Finally got hand of convolutions etc! ISL 2002 N3 : Let $p_1,p_2,\ldots,p_n$ be distinct primes greater than $3$. Show that $2^{p_1p_2\cdots p_n}+1$ has at least $4^n$ divisors. Proof : Now consider $d\mid p_1p_2\ldots p_n$ and $d'\mid p_1p_2\ldots p_n$. Note that there is a prime $p|2^d+1|2^{p_1p_2\cdots p_n}+1$ and $p\nmid 2^{d'}+1$ by zsig for any $d, d'$. Hence there are any $2^n$ distinct such $p$ ( as there are $2^n$ prime factors of $p_1p_2\cdots p_n$). Since there are atleast $2^n$ distinct primes dividing $p_1p_2\cdots p_n \implies $ there are at least $2^{2^n}$ primes factors which is $>>4^n$. The exceptional case doesn't matter here.  [ISL 2000 N4] :Find all triplets of positive integers $ (a,m,n)$ such that $ a^m + 1 \mid (a + 1)^n$ Proof : Except for the exception of the Zsigmondy theorem, there exists $p$ such that $p|a^m+1$ and $p\nm...

Just did two problems, and both were hard! So I think one can excuse me for not solving more, but it's true. I did give less time. I am trying to reduce the amount of time I "waste". I did spend a good amount of time learning the theory, so yey! Excited for today's link episode!!  [Romania TST 7 2009, Problem 3] Show that there are infinitely many pairs of prime numbers $(p,q)$ such that $p\mid 2^{q-1}-1$ and $q\mid 2^{p-1}-1$. Proof: We begin with the lemma,  Lemma: Let $p\mid 2^{2^n}+1$ then $p\equiv 1\pmod  2^{n+2}$ Proof: Note that ord$_p(2)=2^{n+1}$ $$\implies 2^{n+1}|p\implies p\equiv 1\pmod 2^{n+1}\implies p\equiv 1\pmod 8$$ $$\implies 2^{\frac{p-1}{2}}\equiv 1\pmod p\implies 2^{n+1}\mid \frac{p-1}{2}$$ So consider any prime $p$ dividing $2^{2^{n}}+1$ and $q$ to be prime factor of $2^{2^{n+1}}+1$. Then we get that $p\equiv 1 \pmod 2^{n+2}$ and we get that $q\equiv 1\pmod 2^{n+3}$. Note that $$p\mid 2^{n+1}-1\mid 2^{n+3}-1 \mid 2^{q-1}-1$$ Moreover, $$q\mid 2...

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

Continuing from  here . Book Referred: David Burton, Elementary Number Theory Also, thanks to Pranjal Bhaiya and Ritam bhaiya for taking lectures in NT in EGMO Camp and Sophie! We state and prove LTE first. $$v_p(x^n-y^n)=v_p(x-y)+v_p(n), n|x-y, n\not\mid x.$$ Walkthough: We use induction on $v_p(n).$ [ We show for $v_p(n)=0, v_p(n)=1$ and then use induction. 1. We show it for $v_p(n)=0.$ That is show $v_p(x^n-y^n)=v_p(x-y)$ To show this is true, $$v_p(\frac{x^n-y^n}{x-y})=v_p(x^{n-1}+yx^{n-2}+y^2x^{n-3}+\dots+y^{n-1})=0.$$ As $x\equiv y\pmod p.$ So,  $$x^{n-1}+yx^{n-2}+y^2x^{n-3}+\dots+y^{n-1}\equiv nx^{n-1}\pmod p. $$ And $p\not\mid nx^{n-1}$ 2. We show it for $v_p(n)=1.$ That is show $v_p(x^n-y^n)=v_p(x-y)+1$ To show this is true, $$v_p(\frac{x^n-y^n}{x-y})=v_p(x^{n-1}+yx^{n-2}+y^2x^{n-3}+\dots+y^{n-1})=1.$$ As $x\equiv y\pmod p\implies x=y+pk$ So,  $$x^{n-1}+yx^{n-2}+y^2x^{n-3}+\dots+y^{n-1}\pmod {p^2} $$ $$\equiv (pk+y)^{n-1}+(pk+y)^{n-2}y+(pk+y)^{n-3}y^2+\dots+y^{...

Continuing from the previous post from  here . Another memory lane of theorem I want to prove/try! Book Reffered: David Burton, Elementary Number Theory Problem 1: $$p_n<2^{2^{n-1}}$$ Proof: Note that $$p_{n+1}\le p_1p_2\dots p_n+1\le 2\cdot \dots 2^{2^{n-1}}=2^{2^{n-1}}$$ Problem 2: If the $n>2$ terms of the arithmetic progression $$p,p+d, p+2d,\dots,p+(n-1)d$$ are all primes then the common difference $d$ is divisible by every prime $q<n.$ Proof: If not then there exists a $q$ such that $(d,q)=1, q<n.$ But then we can get a $r$ such that $p\equiv -rd\mod q.$ Problem 3: Let $p_n$ denote the $n$ th prime. For $n>3$ show that $$p_n<p_1+p_2+\dots p_{n-1}.$$ Proof: Use induction and Bertrand's postulate. We get that $$p_{n+1}<2p_n<p_1+p_2+\dots p_{n-1}+p_n.$$ I should try to prove FLT and Wilson on my own too! But lemme state them in problems format. Anyways.. Problem4: If $n=a^2+b^2=c^2+d^2$ then $$n=\frac{(ac+bd)(ac-bd)}{(a+d)(a-d)}$$ Proof:  Note ...

I thought to revise David Burton and try out some problems which I didn't do. It's been almost 2 years since I touched that book so let's see! Also, this set of problems/notes is quite weird since it's actually a memory lane. You will get to know on your own! I started with proving a problem, remembered another problem and then another and so on! It was quite fun cause all these questions were the ones I really wanted to solve! And this is part1 or else the post would be too long. Problem1: Prove that for $n\ge 1$  $$\binom{n}{r}<\binom{n}{r+1}$$ iff $0\le r\le \frac{n-1}{2}$ Proof: We show that $\binom{n}{r}<\binom{n}{r+1}$ for $0\le r\le \frac{n-1}{2}$ and use the fact that $$\binom{n}{n-r}=\binom{n}{r}$$ Note that $\binom{n}{r}= \frac{n!}{r!(n-r)!}, \binom{n}{r+1}=\frac{n!}{(r+1)!(n-r-1)!}$  Comparing, it's enough to show that $$\frac{1}{n-r}<\frac{1}{r+1}\text{ or show } n-r>r+1$$ which is true as $0\le r\le \frac{n-1}{2}$ Problem2: Show that the exp...