Posts

INDUCTION??

 So I was explaining to a friend my (slightly different from the standard) view of (mathematical) induction, and decided to, in short, explain it here. The standard version goes (according to NCERT): Mathematical induction is one of the techniques which can be used to prove variety of mathematical statements which are formulated in terms of n, where n is a positive integer. The principle of mathematical induction: Let $P(n)$ be a given statement involving the natural number n such that (i) The statement is true for $n = 1$, i.e., $P(1)$ is true (or true for any fixed natural number) and (ii) If the statement is true for $n = k$ (where $k$ is a particular but arbitrary natural number), then the statement is also true for $n = k + 1$, i.e, truth of $P(k)$ implies the truth of $P(k + 1)$. Then $P(n)$ is true for all natural numbers $n$. In olympiad circles, a strong form is often mentioned, which assumes $P(1), P(2), \dots, P(k)$ are all true and attempts to prove $P(k+1)$. However, c...
Post a Comment
Read more

Super cool Algebra from the IMO!!

 (This article was written 15-1-2025) Problem (23IMO4). Let \(x_1,x_2,\dots,x_{2023}\) be pairwise different positive real numbers such that \[a_n = \sqrt{(x_1+x_2+\dots+x_n)\left(\frac{1}{x_1}+\frac{1}{x_2}+\dots+\frac{1}{x_n}\right)}\] is an integer for every \(n = 1,2,\dots,2023\). Prove that \(a_{2023} \geqslant 3034\). Let's try to get small bounds on the \(a_i\). Well, \(a_1 = 1\) is obvious.   Similarly, we have \[a_2 = \sqrt{(x_1 + x_2) \left(\frac{1}{x_1} + \frac{1}{x_2} \right)} \ge 2,\] where the inequality is by Cauchy-Schwarz. But the sequence has distinct terms (conveniently enough), so in fact \(a_2 \ge 3\). Is there any general inductive bound we can have on \(a_{n+1}\) given \(a_n\)? Let's see: \[a_{n+1} = \sqrt{(x_1+x_2+\dots+x_{n+1})\left(\frac{1}{x_1}+\frac{1}{x_2}+\dots+\frac{1}{x_{n+1}}\right)}.\] But we can already see a hidden \(a_n\): \[a_{n+1} = \sqrt{\left((x_1+x_2+\dots+x_n) + x_{n+1}\right)\left(\left(\frac{1}{x_1}+\frac{1}{x_2}+\dots+\frac{1}...
Post a Comment
Read more

On NT FEs

 (This article was written 2-1-2025)  So, I've been doing NT FEs recently (for an OTIS unit) and I've seen that they all just die to a certain group of techniques. Here they are: 1. Induction Of course, this technique is valuable not just in NT FEs, but in FEs over \(\mathbb{N},\mathbb{Z},\) and \(\mathbb{Q}\). Sometimes the results found in it can be extended to \(\mathbb{R}\). (This is known as the NQR method for obvious reasons.) 2. NT-type Size Quite a few NT FEs are of the form $$\textrm{LHS} \mid \textrm{RHS}.$$ In these sort of FEs, we'd like to find an LHS and RHS such that \(|LHS| > |RHS|,\) since it implies that \(RHS = 0\). Some ideas are taking a variable to be a large number which we have a lot of control over (for example, a large prime). In fact, this idea is so important per se that I have written it in bold. If we can find a fixed RHS for which infinitely many LHS satisfy the condition, we will also be done. 3. Regular Bounding One more FE idea (which al...
Post a Comment
Read more

Why visualisation is soooo powerful

(This article was written on 1 Jan 2025 before it was migrated here)  Today I'm gonna talk about a super-simple but super-overpowered thing called visualisation. Let's begin with the following problem. (22SLC1): 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$ such 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.$$ Yeesh, what a statement. We have a very limited yet free sequence, and we want to choose elements in it (also under a restriction) to maximise a given quantity (which happens to look somewhat terrifying). How do we even begin to approach this? Well, we can try to visualise it. In fact, consider this alternative version in the same shortlist (This was the version given to USA MOP students) : $2022$ buckets o...
Post a Comment
Read more

Configs in Algebra?

 We start with the following problem: (2005 Czech-Polish-Slovak Olympiad) Let $n$ be a positive integer. Solve over $\mathbb{R}_{\ge 0}$ the system $$\sum_{i  =1}^n x_i^i = n$$ $$\sum_{i = 1}^n ix_i = \frac{n(n+1)}{2}.$$ Okay. The first thing that we see is that $x_i = 1 \forall i$ works. Also I'd expect this to be the only solution; the equation feels very "restricted" in some sense. (I'm not sure how to formalise this intuition, so if anyone could help with that, that would be nice.) Also, the equations just seem to look like AM-GM? I'm not sure how exactly, but maybe I've done enough AM-GM ineq such as 2012 IMO 2 so that $x_i^i$ and $ix_i$ look like AM-GM. (Is this how geometers see configs?) Anyway, we'd be highly likely to find an AM-GM equality case from here. And equality holds for $x_i = 1$. So we're motivated (using Sharpness Principle, for example) to use AM-GM in the following way: $$x_i^i + (i-1) \ge i \left(x_i^i\right)^{\frac{1}{i}} $$ An...
Post a Comment
Read more