SIMO Retiree Blog

(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...

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 ...

 (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...

(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.