Skip to main content

TOP 10 problems of Week#2

This week was full Number Theory and algebra biased!! 😄

Do try all the problems first!! And if you guys get any nice solutions , do post in the comments section!

Here are the walkthroughs of this week's top 5 Number Theory problems!

5th position (1999 JBMO P2): For each nonnegative integer $n$ we define $A_n = 2^{3n}+3^{6n+2}+5^{6n+2}$. Find the greatest common divisor of the numbers $A_0,A_1,\ldots, A_{1999}$.

Walkthrough: It doesn't require a walkthrough, I wrote this here, cause it's a cute problem for the person who has just started Contest math :P

a. What is $A_0$?

b. Find out $A_1$.

c. Show that $\boxed{7}$ is the required answer!

4th position (APMO, Evan Chen's orders modulo a prime handout): Let $a,b,c$ be distinct integers. Given that $a | bc + b + c, b | ca + c + a$

and $c | ab + a + b$, prove that at least one of $a, b, c$ is not prime.

Walkthrough: Fully thanks to MSE ! (Also one should try MSE, it has helped me a lot, ofc it's more tilted to College math but it's great! )

a. FTSOC let $a,b,c$ be primes. Then note that by simon's favorite factoring trick , we get $(b+1)(c+1)\equiv 1 \mod a$ , similarly for $b,c$.

b. Bound $\frac{(a+1)(b+1)(c+1)}{abc}$ and get a contradiction !

3rd position (IMO 2011 P1): Given any set $A = \{a_1, a_2, a_3, a_4\}$ of four distinct positive integers, we denote the sum $a_1 +a_2 +a_3 +a_4$ by $s_A$. Let $n_A$ denote the number of pairs $(i, j)$ with $1 \leq  i < j \leq 4$ for which $a_i +a_j$ divides $s_A$. Find all sets $A$ of four distinct positive integers which achieve the largest possible value of $n_A$.

Walkthrough: This was clearly the hardest of all like I took  lot of hints :P.

a. Show that $n_A\ne 6,5$.

b. We will show that $n_A=4$ is possible. hmm...so what do we have ? 

c. Show that $a_1+a_4=a_2+a_3$.

d. So $a_1+a_2|2(a_2+a_3) \implies k_1(a_1+a_2)=2(a_2+a_3)$ , and similarly $k_2(a_1+a_3)=2(a_2+a_3)$ , where $k_1>k_2$.

e.But note that $2a_3+2a_1>2(a_2-a_1) \implies k_2=3$.

f. Show that $k(a_1+a_2)=6a_2-6a_1 \implies k_1=4,5$

g. Case bash!!!!!!!!! 

2nd position(IMO 2011 P5) : Let $f$ be a function from the set of integers to the set of positive integers. Suppose that, for any two integers $m$ and $n$, the difference $f(m) - f(n)$ is divisible by $f(m- n)$. Prove that, for all integers $m$ and $n$ with $f(m) \leq f(n)$, the number $f(n)$ is divisible by $f(m)$.

Walkthrough: Thanks to the Pr0est Mueller.25

a. Take $P(m,0)$ and show that $f(m)|f(0)$ for all $m$. This gives that $f(x)$ has finite solutions.

b. Take $P(0,n)$ and $P(0,-n) $ and show that $f(n)=f(-n)$.

c. Prove by induction that if $a|b \implies f(a)|f(b)$ [it's not required, we just want $f(1)|f(b)$, but it's cute, so one can try].

d. Since $f(x)$ has finite solution, let the solutions be $f(1)<f(a_1)< \dots <f(a_k)<f(0)$.

e. So.. the problem now reduces on showing $f(a_i)|f(a_j)$ when $i<j$. 

f. okay so we have $f(1)|f(a_i)$ , so let's try showing $f(a_1)|f(a_2)$.

g. Let's take $P(a_2,a_1)$ then show that $f(a_2-a_1)= f(a_1)$ or $f(1)$.

h. But we want to show that $f(1)|f(2)$ . But note that if we show that $f(a_2-a_1)= f(a_1)$, then we will be done! So let's try to show that!

i. Take $P(a_2-a_1, -a_1)$ and wola!

1st Position (IMO Shortlist 2011 N3):  Let $n \geq 1$ be an odd integer. Determine all functions $f$ from the set of integers to itself, such that for all integers $x$ and $y$ the difference $f(x)-f(y)$ divides $x^n-y^n.$

Walkthrough: a. Try to guess what possible solutions can be by taking $n=1,3,6$ ( just guess, no need to prove :P) 

b. Note that if $f(x)$ works then $f(x)+c, -f(x)$ works too. So we can assume $f(0)=0$ and $f(1)=1$.

c. With $P(p,1)$ and $P(p,0)$, where $p$ is a prime, show that $f(p)=\pm p^k$ , where $k|n$ 

d. Show $f(p)\ne -p^k$ [ we here use the fact that when $a^b-1|a^c-1 \implies b|c$ and also $k\ne 0$ ]

e. But n has finitely many prime factors , and there are finitely many prime, so there will exist a prime factor of $n$ say $d$ , which will be used infinitely times. So let $q$ be a very( verrrry big) prime with $f(q)=q^d$

f. Take $P(x,q)$, and show that $f(x)=x^d$. And then conclude! 

g. Solutions are $\boxed{f(x)=\pm x^d+c}$ where $d|n$.

Next are the walkthroughs of this week's top 5 Algebra problems! This is only for beginners algebra people ( It's not my fault that people who are reading this blog are pr0s 😎). *Take it more like as a set of problems to motivate you to study algebra :P

5th position (2010 AMC 10 A P21) : The polynomial $x^3-ax^2+bx-2010$ has three positive integer roots. What is the smallest possible value of $a$?

Walkthrough: a. Use Vieta's formula and factorize $2010=2\cdot 3 \cdot 5\cdot 67$ 

b. okay to minimize , obviously 6,5,67 will be answer :P (idk how to explain this part , it actually follows trivially :P)

4th position (NIMO summer contest P9): The roots of the polynomial $P(x) = x^3 + 5x + 4$ are $r, s$, and $t$. Evaluate$ (r + s) ^4 (s + t) ^4 (t + r)^ 4$

Walkthrough: a. Use Viteta's , we get $r+s+t=0$ 

b. we just have to find $(rst)^4$.

3rd position (AIME 2008 II P7): Let $ r$, $ s$, and $ t$ be the three roots of the equation $8x^3+1001x+2008=0.$ Find $ (r+s)^3+(s+t)^3+(t+r)^3$.

Walkthrough: Ooo quite similar to the problem we did  previously.

a. Use viteta and get $r+s+t=0$. So $ (r+s)^3+(s+t)^3+(t+r)^3=-(t^3+r^3+s^3)$.

b. So for people who are in grade 9 or below India standard, or any beginner in algebra, there's a very well known formula, which says $a^3+b^3+c^3=3abc$ , when $a+b+c=0$, it's just $a^3 + b3^ + c^3 - 3abc = (a + b + c)(a^2 + b^2 + c^2 - ab - bc - ca)$ . Use it and we are done!

2nd position (2017 AMC 12 A P17) : There are $24$ different complex numbers $z$ such that $z^{24}=1$. For how many of these is $z^6$ a real number?

Walkthrough:  I don't think so any walkthrough is needed :P. Answer is $\boxed{12}$. Consider $z^{{\frac{2\pi\cdot i \cdot k}{24}}\cdot 6}$ , it will be real iff $k$ is even .

1st Position(JBMO 2012 Shortlist): Let $a$ , $b$ , $c$ be positive real numbers such that $abc=1$ . Show that :

$\frac{1}{a^3+bc}+\frac{1}{b^3+ca}+\frac{1}{c^3+ab} \leq \frac{ \left (ab+bc+ca \right )^2 }{6}$

Walkthrough: a. Use AM-GM and get $a^3+bc\ge 2a$.

b. Try to get this $\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\le \frac{(ab+bc+ca)^2}{3}$ , conclude with AM-GM again !

So these were my top 10 ! I personally wanted to add JMO 2017 P4, but didn't ( due to some soul imbalance , you will understand what I mean once you try this problem) . Go ahead and try if u want to :P.

What are your top 10s ? do write in the comments section (at least write something ! I will be happy to hear your comments ). Follow this blog if you want to see more contest math problems! See you all soon 😊.

---

I also made a pdf compilation of these problems and hints. Here is the google drive link https://drive.google.com/file/d/1sFQBU1MDIYGXWKG_1Bb6TpUAfTZfT4en/view?usp=sharing

Sunaina 💜


Labels:

Comments

  1. AnandDecember 13, 2020 at 10:39 PM

    Nice Post!
    BTW which year's APMO was N4? Asking 'cause its almost same as IMO 1992/P1

    ReplyDelete
    Replies
    1. Sunaina Pati December 14, 2020 at 3:07 PM

      I actually don't know.. Evan sourced it as APMO in his orders modulo prime handout ..

      Delete

Post a Comment

Popular posts from this blog

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....
3 comments
Read more

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$ ...
Post a Comment
Read more

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 ...
2 comments
Read more

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...
11 comments
Read more

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...
1 comment
Read more

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...
4 comments
Read more

Introduction

  Hey Everyone!! This is my first Blog post. So let me give a brief introduction about myself. I am Sunaina Pati. I love solving Olympiad math problems,  learning crazy astronomical facts , playing hanabi and anti-chess, listening to Kpop , love making diagrams in Geogebra and  teaching other people maths 😊 . I love geometry , number theory and Combinatorics . I am starting this blog to keep myself a bit motivated in doing studies 😎 . Right now, I am planning to write walkthroughs on some of the best problems I tried over the week which can refer for hints 'cause solutions contain some major spoilers and one learns a lot while solving the problem on his own rather than seeing solutions . Also, there will be some reviews about Kpop songs, study techniques, my day to day lifestyles,exam reviews and ofc some non-sense surprises 😂.  I am planning to  try  posting every week on Sundays or Saturdays ( most probably) ! Though there is no guarantee about when I ...
20 comments
Read more

Challenging myself? [Jan 15-Jan 27]

Ehh INMO was trash. I think I will get 17/0/0/0-1/3-5/10-14, which is def not good enough for qualifying from 12th grade. Well, I really feel sad but let's not talk about it and focus on EGMO rather.  INMO 2023 P1 Let $S$ be a finite set of positive integers. Assume that there are precisely 2023 ordered pairs $(x,y)$ in $S\times S$ so that the product $xy$ is a perfect square. Prove that one can find at least four distinct elements in $S$ so that none of their pairwise products is a perfect square. I will use Atul's sol, cause it's the exact same as mine.  Proof: Consider the graph $G$ induced by the elements of $S$ and edges being if the products are perfect squares. Note that if $xy = a^2$ and $xz = b^2$, then $yz = \left( \frac{ab}{x} \right)^2$, since its an integer and square of a rational number its a perfect square and so $yz$ is an edge too. So the graph is a bunch of disjoint cliques, say with sizes $c_1, c_2, \cdots, c_k$. Then $\sum_{i=1}^k c_i^2 = 2023$, which ...
Post a Comment
Read more

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...
7 comments
Read more

Let's complex bash Part 1

I have to learn complex bash. And almost everyone knows that I am notes taking girl so thought why not make a post on complex bash ( so that I don't get emotionally demotivated lol).😇 There wasn't any need for learning complex bash, but it was in my dream checklist i.e " To learn a bash." And since I am not loaded with exams, I think it's high time to learn Bash and new topics.  Also if anyone from the "anti-bash" community is reading, sorry in advance and R.I.P.  Notes:- 1. Complex numbers are of the form $z=a+ib,$ where $a$ and $b$ are real numbers and $i^2=-1.$ 2. In polar form, $z=r(\cos \theta+~~i\sin\theta)=~~re^{i\theta},$ where $r=~~|z|=~~\sqrt{a^2+b^2},$ which is called the magnitude. 3. Here we used euler's formula i.e $\cos \theta+~~i\sin\theta=~~e^{i\theta}.$ 4. The $\theta $ is called the argument of $z,$ denored $\arg z.$ ( $\theta$ can be considered in $\mod 360$ and it is  measured anti-clockwise). 5. The complex conjugate of $z$ is ...
4 comments
Read more