SIMO Retiree Blog

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

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

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

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