Arya’s Algorithms

The Pit of Tiling: Dominoes, Trominoes, and the Madness of Covering Boards Some math problems look like games. Tiling problems are the purest of these: you have a shape (a board), you have some tiles (dominoes, trominoes, etc.), and you want to cover the board without overlaps or gaps. It feels like a puzzle you’d get in a children’s magazine. That’s what I thought when I first tried to tile a rectangle with dominoes. Then I fell into a pit that connected geometry, combinatorics, algebra, and computational complexity. Step 1: Dominoes on a Chessboard — The Happy Start Take a standard chessboard, 8 × 8 8 \times 8 . Can you tile it with dominoes, each covering two adjacent squares? Yes — and easily. Just line them up in rows. What about smaller boards? A 2 × n 2 \times n board: clearly possible, just lay them end to end. In fact, the number of ways is exactly the Fibonacci numbers! (each tiling ends with a vertical domino or two horizontals). A 3 × n 3 \times n board? A...

The Pit of the Banach–Tarski Paradox: How to Double a Ball There are problems that feel like they shouldn’t exist. They don’t just resist intuition — they spit in its face. The Banach–Tarski paradox is one of them. The statement is so wild you’d expect it to be a joke: You can take a solid ball in 3D space, cut it into finitely many pieces, and reassemble those pieces — using only rotations and translations — to form two balls identical to the original. Not squashed, not stretched. Just rotated and moved. One ball becomes two. When I first heard this, I thought: impossible. Surely someone is cheating. Surely this is wordplay. Surely this is some optical illusion. Then I stepped into the pit. Step 1: My First Reactions “Conservation of volume!” My physics instincts screamed at me. Volume can’t just double. “Maybe the pieces overlap?” But the theorem insists: no overlap, no stretching. “Maybe the pieces are infinitely many?” No. Just five pieces. Everything I tr...

Problem Pit: The Deceptive Double Integral The Problem Evaluate the double integral: $$\iint_R \frac{x-y}{(x+y)^3} \, dx \, dy$$ where $R$ is the region bounded by $x = 0$, $y = 0$, $x + y = 1$, and $x + y = 2$. This looked like a standard double integration problem. The region seemed clear, the integrand manageable. What could go wrong? As it turns out, this problem would take me through coordinate transformations and some surprising insights about symmetry. Setting Up the Region First, let me understand the region $R$: - $x \geq 0$ (right of y-axis) - $y \geq 0$ (above x-axis) - $x + y \geq 1$ (above the line $x + y = 1$) - $x + y \leq 2$ (below the line $x + y = 2$) The vertices of this trapezoidal region are: - $(1,0)$ where $x + y = 1$ meets $y = 0$ - $(0,1)$ where $x + y = 1$ meets $x = 0$ - $(2,0)$ where $x + y = 2$ meets $y = 0$ - $(0,2)$ where $x + y = 2$ meets $x = 0$ So $R$ is a trapezoid with these four vertices. First Approach: Direct Integration...

  The Pit of Fractal Integrals : Measuring the Unmeasurable with Takagi’s Monster There are functions that refuse to be smooth. They wiggle, they bend, they squirm, and the closer you look, the worse they behave. In real analysis, such creatures live everywhere — but a few have become infamous for how innocently they present themselves before revealing their pathological depths. One such monster is the Takagi function , sometimes called the “blancmange function.” On first sight, it looks like a child’s zig-zag doodle. Defined by a simple infinite sum of tent functions, it has the unnerving property of being continuous everywhere, but differentiable nowhere. When I first met it, I thought: “Fine, I know Weierstrass did this already. This is just another example of pathological analysis.” But then I asked a simple question: I ( α ) = ∫ 0 1 f α ( x )   d x , I(\alpha) = \int_0^1 f_\alpha(x) \, dx, where f α ( x ) = ∑ n = 0 ∞ α n   ϕ ( 2 n x ) , ϕ ( x ) = min ⁡ k ∈ Z ∣ x − k ...

Problem Pit: The Matrix Eigenvalue Maze The Problem Find all possible values of $\det(A)$ where $A$ is a $3 \times 3$ matrix with integer entries such that $A^3 = 2A^2 + 3A - I$. This problem looked straightforward initially - just find the eigenvalues and compute their product. But as I dug deeper, I encountered surprising connections to algebraic number theory, minimal polynomials, and the subtle relationship between characteristic and minimal polynomials. First Approach: The Characteristic Polynomial Route If $A$ satisfies $A^3 = 2A^2 + 3A - I$, then rearranging: $$A^3 - 2A^2 - 3A + I = 0$$ This means the minimal polynomial of $A$ divides $m(x) = x^3 - 2x^2 - 3x + 1$. If $\lambda$ is an eigenvalue of $A$, then $m(\lambda) = 0$, so: $$\lambda^3 - 2\lambda^2 - 3\lambda + 1 = 0$$ Let me find the roots of this cubic. Using the rational root theorem, possible rational roots are $\pm 1$. Testing $\lambda = 1$: $$1 - 2 - 3 + 1 = -3 \neq 0$$ Testing $\lambda = -1...

Problem Pit: The Stubborn Series Convergence The Problem Determine the convergence of $\sum_{n=1}^{\infty} \frac{\sin(n!)}{n^p}$ for various values of $p$. This series fascinated me with its combination of the rapidly growing factorial in the sine function and polynomial decay. Standard convergence tests seemed useless against the erratic behavior of $\sin(n!)$, leading me into the world of equidistribution theory and deep properties of factorials. The Obvious Case First Since $|\sin(n!)| \leq 1$ for all $n$, we have: $$\left|\frac{\sin(n!)}{n^p}\right| \leq \frac{1}{n^p}$$ By comparison test, if $p > 1$, the series converges absolutely since $\sum \frac{1}{n^p}$ converges. But what about $p \leq 1$? This is where things get interesting and where standard methods fail. Dead End #1: Ratio and Root Tests The ratio test gives: $$\lim_{n \to \infty} \left|\frac{a_{n+1}}{a_n}\right| = \lim_{n \to \infty} \left|\frac{\sin((n+1)!)}{(n+1)^p} \cdot \frac{n^p}{\sin...

  Problem Pit: The Persistent Polynomial Mystery The Problem Find all polynomials $P(x)$ such that $P(x^2) = P(x) \cdot P(x+1)$ for all real $x$. When I first saw this functional equation, it looked straightforward. Just find a polynomial satisfying one condition - how hard could it be? Turns out, this innocent equation would drag me through multiple dead ends before revealing its secrets. First Attempts: Plugging in Values My instinct was to substitute simple values and see what constraints emerged. Starting with $x = 0$: $$P(0^2) = P(0) \cdot P(0+1)$$ $$P(0) = P(0) \cdot P(1)$$ If $P(0) \neq 0$, then $P(1) = 1$. Next, $x = 1$: $$P(1^2) = P(1) \cdot P(1+1)$$ $$P(1) = P(1) \cdot P(2)$$ Since $P(1) = 1$, we get $P(2) = 1$. With $x = 2$: $$P(4) = P(2) \cdot P(3) = 1 \cdot P(3) = P(3)$$ And $x = -1$: $$P(1) = P(-1) \cdot P(0)$$ $$1 = P(-1) \cdot P(0)$$ So I was getting specific values at integer points, but needed a systematic approach. Dead End #1: The...

The Pit of Integer Partitions: When Numbers Break Apart There are math problems that are easy to state but impossible to tame. Integer partitions are one of the purest examples. The problem sounds like child’s play: In how many ways can you write n n as a sum of positive integers, order irrelevant? For example, with n = 4 n=4 : 4 = 4 , 3 + 1 , 2 + 2 , 2 + 1 + 1 , 1 + 1 + 1 + 1. 4 = 4, \quad 3+1, \quad 2+2, \quad 2+1+1, \quad 1+1+1+1. So there are 5 partitions of 4. Simple, right? That’s what I thought. Then I fell into the pit. Step 1: First Steps Let’s compute the partition numbers p ( n ) p(n) : p ( 1 ) = 1 p(1)=1 . p ( 2 ) = 2 p(2)=2 : 2 , 1 + 1 2,1+1 . p ( 3 ) = 3 p(3)=3 : 3 , 2 + 1 , 1 + 1 + 1 3,2+1,1+1+1 . p ( 4 ) = 5 p(4)=5 . p ( 5 ) = 7 p(5)=7 . p ( 6 ) = 11 p(6)=11 . The sequence is: 1 , 2 , 3 , 5 , 7 , 11 , 15 , 22 , 30 , 42 , … 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, \dots Already I was tempted to guess a formula. I failed. Step 2: The Wro...