Posts

SMO(J) '24 Q1

-
Image
(Dylan here.) I realised the general content on this blog is pitched at a rather high level. Here's an attempt to balance it. (SMOJ '24 Q1) Let $ABC$ be an isosceles right-angled triangle of area $1$. Find the length of the shortest segment that divides the triangle into $2$ parts of equal area. First, let’s draw some pictures and find out what the side lengths are: if $|AB| = |BC| = x$, then $$\text{Area}(ABC) = \frac{1}{2}x^2 = 1 \implies x = \sqrt{2}.$$ And for good measure, the length of the hypotenuse is determined by Pythagoras: $|AC| = \sqrt{x^2+x^2} = \sqrt{2} x = 2$. Okay, now let’s try to cut the triangle. I know I can divide the triangle into $2$ parts symmetrically, as in case (0). This gives us an upper bound of $1$ for the shortest segment. But more generally, the line segment can touch any two of the $3$ sides, giving us $3$ cases. And, note that cases (I) and (II) are symmetric via reflection, so it suffices to consider cases (I) and (III). And from my drawings,
Post a Comment
Read more

Bears and Cats

-
Image
(David here.) In my analysis set from 2020 , I had an overly ambitious section titled "Bears and Cats". Four years later, I've finally decided to compile my solutions somewhere and to record the intention behind this set. This post will assume some familiarity with closed/open sets and continuous functions.
Post a Comment
Read more

"Equal" Partitions

-
Image
(Gabriel here.) Today I'll talk about an interesting distribution problem that I solved recently and my thought process when solving it. Here it is: (India-Iran Friendly Competition Q5) Let $n \geq k$ be positive integers and let $a_1, \dots, a_n$ be a non-increasing list of positive real numbers. Prove that there exists $k$ sets $B_1, \dots, B_k$ which partition the set $\{1, 2, \dots, n\}$ such that $$\min_{1 \le j \le k} \left(\sum_{i \in B_j} a_i \right) \geq \min_{1 \le j \le k} \left(\frac{1}{2k+1-2j} \cdot \sum^n_{i=j} a_i\right).$$ Proposed by Navid Safaei The inequality looks extremely convoluted, so let's dissect what is happening. We have the numbers $a_1\ge a_2\ge \dots \ge a_n$, and we can freely partition them into $k$ different (possibly non-empty) groups. The expression on the LHS is just the minimum sum of elements across the groups. Because there is no mention of $B_i$ in the RHS, we are simply trying to distribute the elements as evenly as possible. T
Post a Comment
Read more

An Infinitely Long Game

-
(Drew here.) Let's take a dive into a problem from the 2023 IMO Shortlist. This is C5, one of the hardest shortlist problems this year (but let's be honest, the whole C list was devilishly hard). Elisa has $2023$ treasure chests, all of which are unlocked and empty at first. Each day, Elisa adds a new gem to one of the unlocked chests of her choice, and afterwards, a fairy acts according to the following rules: if more than one chests are unlocked, it locks one of them, or if there is only one unlocked chest, it unlocks all the chests. Given that this process goes on forever, prove that there is a constant $C$ with the following property: Elisa can ensure that the difference between the numbers of gems in any two chests never exceeds $C$, regardless of how the fairy chooses the chests to unlock. Here, the problem presents itself to us. An infinitely long game, with a finite goal. How is this even possible? Let $n=2023$, and I'll just clean up the statement a bit here: after
Post a Comment
Read more

BTS III: Some loose ends

-
Image
This is the last installment to the series sparked off by the SMO Open Q4 problem, which led us to introduce some basic learning theory. If you're deciding whether to read this, I've approximately split up this post into two parts: the first part is about dealing with a certain flavor of inequalities, where you are averaging a maximum over all $2^n$ combinations of $\pm$ signs. the second part is some conventional ML theory content tying generalization error to the Rademacher complexity of loss functions I would suggest reading just the first part unless you are really dying to see where Rademacher complexity comes from. $\newcommand\lrangle[1]{\left\langle #1 \right\rangle} \newcommand \E {\mathbb E} \newcommand \cH {\mathcal H} \newcommand \Var {\mathrm{Var}} \newcommand \MSE {\mathrm{MSE}} \newcommand \cR {\mathcal R} \newcommand \cS {\mathcal S} \newcommand \cF {\mathcal F}$ Part 1: Dealing with $\pm$ inequalities Recap: Rademacher complexity From Part I , we met
Post a Comment
Read more

Coordinate geometry and circles

-
Image
 (This is Glen.) As you may have noticed from my previous posts, my go-to method for approaching geometry problems is bashing, normally with coordinates. Anyone who's tried to bash a problem (especially with coordinates) would have probably found out the hard way that circles generally lead to trouble, but years of bashing have led me to devise some tricks to get around this. I'll be writing about them below, along with, as far as possible, some examples which I remember bashing. I'm not typing out solutions for the sake of my sanity, and besides, I think there is value in actually working through the algebra. Instead, I'm just going to sketch an approach which I think is the most efficient. Introduction Bashing apologia Before I get lynched by the Synthetic Mafia, I should probably provide some justification for this post. Why bash? As a cynical member of the Synthetic Mafia might tell you, it's what immoral people do when they fail in thinking about a problem geom
Post a Comment
Read more

BTS II: An introduction to learning theory

-
Image
(David here.) In this blogpost, we'll go off on a tangent and explore what it means to learn from data . In the process, we will get slightly closer (but not quite there) to the context where Rademacher complexity emerges.
Post a Comment
Read more