Skip to main content


Edge querying in graph theory

In this post, I will present three graph theory problems in increasing difficulty, each with a common theme that one would determine a property of an edge in a complete graph through repeated iterations, and seek to achieve a greater objective. ESPR Summer Program Application: Alice and Bob play the following game on a $K_n$ ($n\ge 3$): initially all edges are uncolored, and each turn, Alice chooses an uncolored edge then Bob chooses to color it red or blue. The game ends when any vertex is adjacent to $n-1$ red edges, or when every edge is colored; Bob wins if and only if both condition holds at that time. Devise a winning strategy for Bob. This is more of a warm-up to the post, since it has a different flavor from the other two problems, and isn't as demanding in terms of experience with combinatorics. However, do note that when this problem was first presented, applicants did not know the winner ahead of time; it would be difficult to believe that Bob can hold such a strong
Recent posts

The importance of "intuition" in geometry

Hii everyone! Today I will be discussing a few geometry problems in which once you "guess" or "claim" the important things, then the problem can easily be finished using not-so-fancy techniques (e.g. angle chasing, power-of-point etc. Sometimes you would want to use inversion or projective geometry but once you have figured out that some particular synthetic property should hold, the finish shouldn't be that non trivial) This post stresses more about intuition rather than being rigorous. When I did these problems myself, I used freehand diagrams (not geogebra or ruler/compass) because I feel that gives a lot more freedom to you. By freedom, I mean, the power to guess. To elaborate on this - Suppose you drew a perfect  diagram on paper using ruler and compass, then you would be too rigid on what is true in the diagram which you drew. But sometimes that might just be a coincidence. e.g. Let's say a question says $D$ is a random point on segment $BC$, so maybe

LMAO Revenge

Continuing the tradition of past years, our seniors at the Indian IMO camp(an unofficial one happened this year) once again conducted LMAO, essentially ELMO but Indian. Sadly, only those who were in the unofficial IMOTC conducted by Pranav, Atul, Sunaina, Gunjan and others could participate in that. We all were super excited for the problems but I ended up not really trying the problems because of school things and stuff yet I solved problem 1 or so did I think. Problem 1:  There is a   grid of real numbers. In a move, you can pick any real number  ,  and any row or column and replace every entry   in it with  .  Is it possible to reach any grid from any other by a finite sequence of such moves? It turned out that I fakesolved and oh my god I was so disgusted, no way this proof could be false and then when I was asked Atul, it turns out that even my answer was wrong and he didn't even read the proof, this made me even more angry and guess what? I was not alone, Krutarth too fakesol

Friendly numbers and infinite descent

Hey everyone, today we discuss two very cute ISL NTs! Hope you like it.  ISL 2012 N4 ISL 2012 N4:An integer $a$ is called friendly if the equation $(m^2+n)(n^2+m)=a(m-n)^3$ has a solution over the positive integers. a) Prove that there are at least $500$ friendly integers in the set ${ 1,2,\ldots ,2012}$. b) Decide whether $a=2$ is friendly Part A  Claim: All $a \equiv 1 ( \mod 4)$  works for all $m=2n+1$ Proof:  $$(4n^2+5n+1)(n+1)^2=a(n+1)^3$$ $$4n^2+n(5-a)+1-a=0$$ $$n=\frac{a-5 \pm \sqrt{a^2+6a+9}}{8}$$ $$=\frac {a-5 \pm a+3}{8}$$ $$= 1 or \frac{a-1}{4}$$ Therefore, we clearly have $500$ such working $n$. Part B Subclaim: If $p|m$, then $p|n$ also,$p|n$, then $p|=m$ for $p$ not equal to $3$  Claim: $V_p(m)=2V_p(n)$ or $V_p(n)=2V_p(m)$ for all  prime $p$, where $p$ divides $n$ Proof:  $$(m^2+n)(n^2+m)=2(m-n)^3$$ $$0=m^3+m^2(-6n-n^2)+m(6n^2-n) -3n^3$$ Which implies that $m|3n^3$ and $n|m^3$ So, our subclaim is true. Now, consider some prime $p$ such that $p|n$ which also implies that $

Inequalities Still Exist!

Long time no inequality post right? So, this is going to be an introductory post on the Rearrangement Inequality . During my Olympiad journey, Rearrangement Inequality was the one that I found most intuitive as well as beautiful. You might say that it is just a mathematical generalization of some idea that you kind of already know and might have used in some of your daily life optimizations, So it says this: Given $2n$ reals $a_1,a_2,$...$,a_n$ and $b_1,b_2$...$,b_n$, $\forall i\leq j\leq n,$ $a_i\leq a_j$ and $b_i\leq b_j$. Consider any permutation $p$ on {$1,2,$.....$,n$}. Then $$\sum_{i=1}^{i=n}a_ib_{n+1-i}\leq \sum_{i=1}^{i=n} a_ib_{p(i)}\leq \sum_{i=1}^{i=n}a_ib_i.$$ and equality for both inequalities holds when either all $a_i$'s or all $b_i$'s are the same. To get an intuition of what the rearrangement inequality addresses, think over the following problems: There are $n$ construction companies and $n$ pieces of land of sizes $l_1,l_2,........,l_n$ units. You are the ow

Introduction to Real Analysis pt 1

 Hi everyone, here are my notes for the real analysis course I have been taking.  The book I have referred to:  Elementary Analysis: The Theory of Calculus Book by Kenneth A. Ross Review Theorem: [ Rational Root Theorem] Suppose $c_0,c_1,\dots, c_n$ are integers and $r$ is a rational number satisfying the polynomial equation $$ c_nx^n+c_{n-1}x^{n-1}+\dots+c_1x+c_0=0$$ where $n\ge 1,c_n\ne 0, c_0\ne 0.$ If $r=\frac{c}{d}$ where $c,d$ are integers and $(c,d)=1$. Then $c|c_0, d|c_n$.  Example: Prove that $\sqrt[3]{6}$ is not a rational number. Proof: Note that $\sqrt[3]{6}$ is solution of $x^3-6=0$. But by rational root theorem, the only possible rational solutions of $x^3-6=0$ are $\pm 1, \pm 2, \pm 3, \pm 6$. But none of these eight numbers satisfies $x^3-6=0$.  Example: All numbers of the form $5^n-4n-1$ are divisible by $16$. Proof: Our $n$th proposition is $$P_n: 5^n-4n-1 \text{ is divisible by } 16$$ The basis for induction $P_1$ is clearly true, since $5^1-4\cdot 1-1=0.$ Propos

Functional Equations 101

Let's get to the math:  Let there be two sets $X$ and $Y$. A function  from $X$ to $Y$ denoted as $f \colon X \to Y$ is assigning a value in $Y$ for every element in $X$. We say that $X$ is the domain of the function $f$ and $Y$ is the range.  A function $f \colon X \to y$ is said to be injective if $f(x) = f(x^{\prime}) \implies x = x^{\prime}$ To put it in a more abstract way, if there is some $a \in Y$ then there is at most one $b \in X$ such that $f(b) = a$ holds true.  A function is said to be surjective when for any $a \in Y$ there is at least one $b \in X$ such that $f(b) = a$ holds true.  A function is bijective if for every $a \in Y$ there is exactly one $b \in X$ such that $f(b) = x$. Bijective functions are basically functions which are both injective and surjective.  Bonus: A function $f \colon X \to X$ is known as an involution if $f(f(x)) = x \; \forall  x \in X$  As an exercise, the readers should try to prove that every function that is an involution is a bijective

Spoiled for choice

 Hi! I'm Atul, in my last year of school and this is going to be my first blog post. For an introduction, I have a bronze at the IMO and a silver at the APMO this year. Apart from math, I also love reading, playing table tennis and making terrible jokes. Something I seem to miss out on saying often is that I love  cats , especially  colour ful ones. Anyway, let's begin! Like many things  i n math, the axiom of choice has a deceptively  s imple statement. All it says is - "Given a collection of  n onempty sets, it is possible to pick an element from each of them". That... sounds pretty obvious and something that just  should  be true. And well, it is. At least for a finite collection of sets, it is definitely true. With some thought, it's also clear how to do it if the collection is countably infinite. But what if the number of sets is just  extremely  huge? When the sets are uncountably infinite, that's when the problems begin. So far I've b e en rather ha

Numbers, and that too IMAGINARY!!

  Hi, I am Emon and yes, I am gonna write something today, after a long period of time, maybe on some imaginary numbers and in turn, complex numbers? Okay, so let's look back into the history of complex numbers which first evolved mainly in the country of Italy... Back in the $16$th century, a famous Italian mathematician, Niccolo Fontana Tartaglia posed the following problem in a journal : Can you find a number $x$ such that $x^3+px=q$, where $p, q$ are given numbers? In fact, he had a secret formula to this question : $$\boxed{x=\sqrt[3]{\frac{q}{2}+\sqrt{\frac{q^2}{4}+\frac{p^3}{27}}} + \sqrt[3]{\frac{q}{2}-\sqrt{\frac{q^2}{4}+\frac{p^3}{27}}}}$$ Later, Italian Mathematician, Gerolamo Cardano proposed the same problem, with the only modification $p\mapsto -p$ : Can you find a number $x$ such that $x^3=px+q$, where $p, q$ are given numbers? He went on to give a second problem by asking : "Can you divide $10$ into two parts such that their product is $40$?" The people of

Mathematics - An Art of Thinking

"Mathematics is not about numbers, equations, computations, or algorithms: it is about understanding." — William Paul Thurston, American mathematician In a previous blog , I spoke a lot about what mathematics isn’t. However, I don’t think I spoke quite enough on what mathematics truly is. Here's how I began that blog. "When we’re young we begin by learning the steps to add – we’re given the rules and we must learn to repeat them – no questions asked. Why does carry forward work the way it does? Well, no questions asked." However, I believe that the essence of truly understanding mathematics lies in the questions you ask – and the first one, the most fundamental one, is also probably one of the hardest questions you would and could find – What really is Mathematics? Something that differentiates explaining what mathematics is from explaining a lot of other concepts is that mathematics was not really ever invented . If a young student angry about excessive math h