Posts

Putnam 2024 Testsolve

(David here!) Putnam 2024 was released recently, so I decided to try a bunch of the problems while on the plane ride from NYC to Chicago. (A3) Let $T$ be a (uniformly) random bijection $$ T: \{1,\,2,\,3\}\times\{1,\,2,\,\ldots,\,2024\}\to\{1,\,2,\,\ldots,\,6072\} $$ conditioned on $T$ being increasing in both arguments. Does there exist indices $(a,b)$ and $(c,d)$ such that $$1/3 \le P(T(a,b)\lt T(c,d)) \le 2/3?$$ I took some liberties with reformulating it probabilistically here. My initial reaction was that this was probably true. My first idea was that if $(a,b) \lneq (c,d)$, then the probability is 0, and flipped around it is 1. So maybe we can take some intermediate sequence of indices that slowly switches them? Didn't get very far with this. Well, thinking slightly meta, the problem can't possibly be that hard - there is no way we're figuring out exactly how many $T$ satisfy $T(a,b) \lt T(c,d)$, so maybe we should be looking for bijections (or partial bijecti...

Inversions and Möbius transformations

Image
 (This is Glen.) At some point, Ker Yang wrote a post on Reim's theorem, which he used to solve two past year IMO problems. I remember commenting to him that I had solved neither of them with Reim (and no, I did not bash them). Later on, I tried reconstructing my solution to IMO 2017/4, and I noticed something interesting that made me find another (slightly weird) solution that (I think) isn't on AoPS. So that's what I'll be writing about today. First, the problem: ( IMO 2017/4 ) Let $R$ and $S$ be different points on a circle $\Omega$ such that $RS$ is not a diameter. Let $\ell$ be the tangent line to $\Omega$ at $R$. Point $T$ is such that $S$ is the midpoint of the line segment $RT$. Point $J$ is chosen on the shorter arc $RS$ of $\Omega$ so that the circumcircle $\Gamma$ of triangle $JST$ intersects $\ell$ at two distinct points. Let $A$ be the common point of $\Gamma$ and $\ell$ that is closer to $R$. Line $AJ$ meets $\Omega$ again at $K$. Prove that the line $KT$...

The onion constant is not 0.557

Image
(This is Yan Sheng.) In my mind, J. Kenji López-Alt is the greatest nerdsniper chef: he has made claims about cooking methods and techniques, based on experimental evidence, which have become the inspiration for later theoretical research. For instance, on the subject of grilling meat , he writes that "...flipping steak repeatedly during cooking can result in a cooking time about 30% faster than flipping only once"; this was confirmed by a model of Thiffeault (2022) (here are some slides from a talk ). Today's post, however, is about onions: Question : What is the optimal way to cut an onion such that the size variation among the diced pieces is minimised? After removing the ends and halving the onion, we can view it as approximately a half-cylinder with concentric layers. This reduces the dimension of the problem, so now we're cutting concentric semicircles: (In the following diagrams, I'm viewing the arcs themselves as the layers, and not the spaces bet...

What is an algorithm?

Image
What is an algorithm? (Wee Kean here.) Some time a year ago, for some reason, the then observers and I were reading the following paper . It is related to Hilbert's tenth problem which asks: given any diophantine equation, is there a general algorithm to decide whether the equation has a solution in integer values? But how do we decide what an algorithm can or cannot do? Formalizing algorithms A turing machine is one way to represent computation. Whether or not turing machines can fully encapsulate what algorithms or computability are is not proven . There are other conceptions of computability but they have all shown to be equivalent to the turing machine. Informally, you can imagine a device with a head, an internal state and an infinitely long tape. At each step, the device reads the symbol on the cell and based on its internal state and the symbol read, it writes a symbol (possibly the same one) on the current cell and moves either left or right. Very useful depiction For...

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

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.

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