Posts

"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

Behind the Scenes of SMO Q4, Part 1: the Proposal Backstory

-
Image
(David here.) Recently, a problem of mine came out as Q4 on SMO Open 2024. I'll go over how I proposed the problem and the theory behind it, which involves some machine learning ideas (!).
Post a Comment
Read more

Substituting Zero

-
Image
(Pengchong here). While in NS, I've been looking at some topics that I might've encountered back in school but not really gone too deeply into - one of which is real analysis, quite a common starting point for undergrad math. Though for those preparing for olympiads it probably doesn't have a high 'ROI', I think much of this stuff provides plenty of intuition for some olympiad problems I've encountered before. And of course, most importantly, I found it pretty fun (looking at Rudin's classic book, in particular). I'll give a brief introduction to some fundamental analysis concepts using ISL 2020 A8 as the vessel, and as an example of how these concepts can sometimes (though rarely) turn out pretty critical for a 'real' olympiad problem. I've used this problem during a session for this year's IMO team a while back (and actually got this in a mock during my own IMO training). It will only use the very fundamen
Post a Comment
Read more