Circular optimization

This post will mostly be focused on construction-type problems in which you're asked to construct something satisfying property $latex {P}&fg=000000$. Minor spoilers for USAMO 2011/4, IMO 2014/5. 1. What is a leap of faith? Usually, a good thing to do whenever you can is to make ``safe moves'' which are implied by the property $latex… Continue reading Circular optimization

A story of block-ascending permutations

I recently had a combinatorics paper appear in the EJC. In this post I want to brag a bit by telling the ``story'' of this paper: what motivated it, how I found the conjecture that I originally did, and the process that eventually led me to the proof, and so on. This work was part… Continue reading A story of block-ascending permutations

Joyal’s Proof of Cayley’s Tree Formula

I wanted to quickly write this proof up, complete with pictures, so that I won't forget it again. In this post I'll give a combinatorial proof (due to Joyal) of the following: Theorem 1 (Cayley's Formula) The number of trees on $latex {n}&fg=000000$ labelled vertices is $latex {n^{n-2}}&fg=000000$. Proof: We are going to construct a… Continue reading Joyal’s Proof of Cayley’s Tree Formula

Positive Definite Quadratic Forms

I'm reading through Primes of the Form $latex {x^2+ny^2}&fg=000000$, by David Cox (link; it's good!). Here are the high-level notes I took on the first chapter, which is about the theory of quadratic forms. (Meta point re blog: I'm probably going to start posting more and more of these more high-level notes/sketches on this blog… Continue reading Positive Definite Quadratic Forms

Formal vs Functional Series (OR: Generating Function Voodoo Magic)

Epistemic status: highly dubious. I found almost no literature doing anything quite like what follows, which unsettles me because it makes it likely that I'm overcomplicating things significantly. 1. Synopsis Recently I was working on an elegant problem which was the original problem 6 for the 2015 International Math Olympiad, which reads as follows: Problem… Continue reading Formal vs Functional Series (OR: Generating Function Voodoo Magic)

New algebra handouts on my website

For olympiad students: I have now published some new algebra handouts. They are: Introduction to Functional Equations, which cover the basic techniques and theory for FE's typically appearing on olympiads like USA(J)MO. Monsters, an advanced handout which covers functional equations that have pathological solutions. It covers in detail the solutions to Cauchy functional equation. Summation,… Continue reading New algebra handouts on my website

Miller-Rabin (for MIT 18.434)

This is a transcript of a talk I gave as part of MIT's 18.434 class, the ``Seminar in Theoretical Computer Science'' as part of MIT's communication requirement. (Insert snarky comment about MIT's CI-* requirements here.) It probably would have made a nice math circle talk for high schoolers but I felt somewhat awkward having to… Continue reading Miller-Rabin (for MIT 18.434)

Mechanism Design and Revenue Equivalence

Happy Pi Day! I have an economics midterm on Wednesday, so here is my attempt at studying. 1. Mechanisms The idea is as follows. We have $latex {N}&fg=000000$ people and a seller who wants to auction off a power drill. The $latex {i}&fg=000000$th person has a private value of at most $latex {\$1000}&fg=000000$ on the… Continue reading Mechanism Design and Revenue Equivalence

Writing Olympiad Geometry Problems

You can use a wide range of wild, cultivated or supermarket greens in this recipe. Consider nettles, beet tops, turnip tops, spinach, or watercress in place of chard. The combination is also up to you so choose the ones you like most. --- Y. Ottolenghi. Plenty More In this post I'll describe how I come… Continue reading Writing Olympiad Geometry Problems

The Mixtilinear Incircle

This blog post corresponds to my newest olympiad handout on mixtilinear incircles. My favorite circle associated to a triangle is the $latex {A}&fg=000000$-mixtilinear incircle. While it rarely shows up on olympiads, it is one of the richest configurations I have seen, with many unexpected coincidences showing up, and I would be overjoyed if they become… Continue reading The Mixtilinear Incircle