Sunaina thinks absurd

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

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

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

Welcome Back to mah blog! I thought I should revise Number theory and solve problems of IOQM level!  Also, NT is definitely my bias wrecker ( Kpop term used to describe the second favourite which has huge chances to become your favourite!) Problem 1 (2019 AMC 12A): For some positive integer $k$, the repeating base-$k$ representation of the (base-ten) fraction $\frac{7}{51}$ is $0.23_k = 0.232323\dots_k .$ What is $k$? Solution: Note that $$ 0.232323\dots_k= \frac{ 2}{k}+\frac{3}{k^2}+\frac{2}{k^2}+\frac{3}{k^4}\dots$$ $$= \frac{2}{k}+\frac{2}{k^3}+\dots + \frac{3}{k^2}+\frac{3}{k^4}+\dots $$ $$ = \frac{2/k+3/k^2}{1-\frac{1}{k^2}}=\frac{7}{51}\implies k= 16.$$ Problem 2[ AIME 2008 II]: There exist $r$ unique nonnegative integers $n_1 > n_2 > \cdots > n_r$ and $r$ integers $a_k$ ($1\le k\le r$) with each $a_k$ either $1$ or $- 1$ such that $$a_13^{n_1} + a_23^{n_2} + \cdots + a_r3^{n_r} = 2008.$$ Find $n_1 + n_2 + \cdots + n_r$. Solution: Note that $$\overline{2008}_{10}...

Welcome back to this blog!  My blog completed it's 1-year :D i.e 29 Nov. I am so happy that this blog grew so much and it didn't die! It also crossed 10k views! Thanks a lot! Enjoy the problems. It's more of a miscellaneous problem set with the level being INMO or less. So here are $20$ INMO level problems. Problems:  Problem 1: [IMO 2009/P1]  Let $ n$ be a positive integer and let $ a_1,a_2,a_3,\ldots,a_k$ $ ( k\ge 2)$ be distinct integers in the set $ { 1,2,\ldots,n}$ such that $ n$ divides $ a_i(a_{i + 1} - 1)$ for $ i = 1,2,\ldots,k - 1$. Prove that $ n$ does not divide $ a_k(a_1 - 1).$ Problem 2[ USEMO 2021 P4]:  Let $ABC$ be a triangle with circumcircle $\omega$, and let $X$ be the reflection of $A$ in $B$. Line $CX$ meets $\omega$ again at $D$. Lines $BD$ and $AC$ meet at $E$, and lines $AD$ and $BC$ meet at $F$. Let $M$ and $N$ denote the midpoints of $AB$ and $ AC$. Can line $EF$ share a point with the circumcircle of triangle $AMN?$ Problem 3 [ 2006 n5]: P...

INMO completed finally!!! I will write my experience/all other we do in the blog ( if I qualify/get merit awardee ) i.e making an excuse of not writing. During this period, I and Anand ft Arpan Bhaiya did a lot of G-Solves, like seriously a lot. ( Fun fact:- Anand didn't prepare anything this year and he solved 3 problems and some partials. So he is too pr0. ). Anyways, here's basically a collection of some modular bash problems, which one should try to motivate himself, they are RMO level. These problems are trivialised by zsig i.e why RMO level. If you want more INMO level problems do check out  https://artofproblemsolving.com/community/c1953209_olypd . I created it just to hide my frivolous forum posts (:P) but it's growing, and free of spam! Some Problems:- ( If you want the source, feel free to ask in comments I am just to lazy to type the source), one can take this as an High  RMO level compilation mock(?). If you want to attempt this as a mock, then 3hrs is perfect! ...