Sunaina thinks absurd

Posts

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

Trying to go beyond my comfort level?

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 extens

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\leq

Problem solving in NT ( day 4 Week 1)

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

Big 'O' notation

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.

Problem solving in NT ( day 3 Week 1)

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\in

Problem solving in NT (day 2 week 1)

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

Problem Solving in NT (Day 1 of Week 1)

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

Announcing the Unofficial TC 2022! ( Month 1 problem solving )

So it's been 1 month since the INMO results were out! So here's my past 1 month's journey into problem-solving. There hasn't been much in my life, although the Sharygin correspondence round results came out! And I qualified for the final round. I just made the cutoff though. I got 85 marks and the (unofficial) cutoff was 84 marks. I am one of the seven students selected for the final round and the only kid from India in my grade! They, however, are not inviting Indian students in the final round and have asked us to conduct the final round in India if an organization agrees. Monthly reflection: Till May 16, I tried the Awesome Math Application ( which I got accepted into woohoo! And I am taking courses in the second and third season hehe) Then I was completing 108 algebra problems along with MBL problems till June 1 June 1- June 10: Since I was feeling very guilty for not doing enough problems from the Sophie psets, I did a few Sophie psets problems. BTW Thankyou so mu