Snoring while sorting

You are waiting in line to be sorted into one of the four houses of Logwarts (a posh wizarding boarding school in the Scottish highlands) by an anthropomorphic sorting hat. The hat is a bit of a snob about the whole matter, and refuses to sort two students in a row into the same house. If a student requests a certain house, but the previously sorted student was already sorted into that same house, then the hat chooses randomly from among the three remaining houses.

You are standing 10th in line, and you make plans to request Graphindor house for yourself. As for the other students in line, you can assume that they have random preferences from among the four houses. The first student steps up, and has a brief, quiet conversation with the hat. After a few moments, the hat proclaims, “Graphindor!” At this point, what is the probability that you will be sorted into Graphindor?

Let's define our probability space such that it will be useful for the this problem. Of course, as stated there are three other houses with fanciful names (perhaps Hufflepath, Ravenndiagram and Slytheorem), but as far as you're concerned it is Graphindor or bust, so luckily all of these outcomes are indistinguishable to you. Let $p_{i,k}$ be the probability that the $i$th wizardling on line is sorted into Graphindor, subject to the fact that the $k$th wizardling on line was the last one to actually be sorted to Graphindor.

As far as you are concerned, you get to Graphindor as long as the 9th wizard is not sorted there, since you will always ask the hat to sort you into Graphindor. So, given that the 1st wizardling on line was just sorted into Graphindor, the probability that you will be sorted into Graphindor is $p=1-p_{9,1}.$ All that remains now is to divine what the formula for $p_{i,k}$ is anyway.

Let's say that we know $p_{i,k}$ for some $1 \leq k \leq i.$ There are two ways for the $(i+1)$th wizardling to end up sorted into Graphindor: either (a) the $i$th wizard is sorted to some ``not Graphindor'' house and the $(i+1)$th wizardling requested Graphindor; or (b) the $i$th wizard is sorted to some ``not Graphindor'' house and the $(i+1)$th wizardling requested that same ``not Graphindor'' house. In both cases, the probability of event (a) is $1/4$ while the probability of event (b) is $1/12 = 1/4 \cdot 1/3.$ Putting these two together, we get the recursion relationship $$p_{i+1,k} = \frac{1}{4} (1-p_{i,k}) + \frac{1}{12} (1-p_{i,k}) = \frac{1-p_{i,k}}{3}, \,\,\text{for $i \geq k \geq 1.$}$$ By construction, we have $p_{k,k} = 1,$ for each $k \geq 1.$

This recursive formula leads to the explicit formula $$p_{i,k} = \frac{1}{4} \left(1 + 3 \cdot (-3)^{k-i}\right), \,\,\, \text{for all $i \geq k \geq 1.$}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\star$$ We see that for $i=k \geq 1$ that we recover $p_{k,k} = \frac{1}{4} (1 + 3 \cdot (-3)^0 ) = 1,$ as our base case. If we assume that the formula $\star$ holds for some $i \geq k \geq 1,$ then from the recursive formula we see that \begin{align*}p_{i+1,k} = \frac{1-p_{i,k}}{3} &= \frac{1 - \frac{1}{4} \left(1 + 3 \cdot (-3)^{k-i} \right)}{3} \\ &= \frac{\frac{3}{4} - \frac{3}{4} \cdot (-3)^{k-i}}{3} \\ &= \frac{1}{4} \left( 1 + \frac{3}{-3} (-3)^{k-i} \right) \\ &= \frac{1}{4} \left( 1 + 3 \cdot (-3)^{k-i-1} \right),\end{align*} which follows formula $\star$ for the case $i+1$. Thus by induction we have proven the formula. This therefore allows us to answer that if you are $10$th in line and have resolved to request Graphindor no matter what that your probability of getting sorted into Graphindor after the first wizard is sorted into Graphindor is $$p=1-p_9 = 1 - \frac{1}{4} \left(1 + 3 \cdot (-3)^{1-9}\right) = \frac{3-3^{-7}}{4} = \frac{6560}{8748} = \frac{1640}{2187} \approx 0.7498856882....$$

Now, instead of being 10th in line, suppose you are $N$th in line, where $N$ is some value much greater than 10. Because so many students are being sorted in front of you, you decide you’ll take a nap. You wake up without any idea of how long you were out—it could have been a second, or it could have been an hour, you’re just not sure. It’s still not your turn to be sorted yet, but you see a student wearing the hat. After a brief moment, the hat shouts, “Graphindor!”

What is the smallest value of $N$ such that your probability of being sorted into Graphindor is greater than $p$? (To be clear, when you wake up, the student being sorted is anywhere from first in line to immediately before you in line with equal probability.)

OK, so now it becomes a little clearer why I chose such obscure nomenclature for the earlier problem. However, in this case where you are sitting at $N$th in line and then dozed off only to wake up as the wizardling in uniformly randomly distributed position $M$ is sorted into Graphindor, so we have the expected probability of being sorted into Graphindor is still dependent on whether or not the person immediately in front of you is sorted into Graphindor, that is $q=1-p_{N-1,M}$. However, here since $M$ is random we have \begin{align*} q = 1 - p_{N-1,M} &= 1 - \sum_{i=1}^{N-1} \mathbb{P} \{ M = i \} p_{N-1,i} \\ &= 1 - \frac{1}{N-1} \sum_{i=1}^{N-1} \frac{1}{4} \left(1 + 3 \cdot (-3)^{i-N+1} \right) \\ &= \frac{3}{4} - \frac{3 \cdot (-3)^{1-N}}{4(N-1)} \sum_{i=1}^{N-1} (-3)^i \\ &= \frac{3}{4} - \frac{3 \cdot (-3)^{1-N}}{4(N-1)} \frac{(-3) - (-3)^N}{1-(-3)} \\ &= \frac{3}{4} \left( 1 - \frac{ 9 \cdot (-3)^{-N} + 3}{4(N-1)} \right) \\ &= \frac{3}{16} \frac{4N-7-9\cdot(-3)^{-N}}{N-1}\end{align*} If we then want to know what is the minimal $N$ such that $q = q(N) \gt p = \frac{1640}{2187},$ we need get a nonlinear, monotonically increasing equation that we can just as easily guess and check for a solution.

In particular, if we solve the approximation where we ignore that pesky exponential function and equally ignore the integrality of $N$, we get $$\tilde{q}(x) = \frac{3 (4x-7)}{16(x-1)}.$$ If we were to solve $$\tilde{q}(x) = \frac{3(4x-7)}{16(x-1)} = p$$ for a non-integer value of $x$, we get $$x^* = \frac{21-16p}{12-16p} = \frac{19687}{4} = 4921.75.$$ This seems like a very good place to start hunting and pecking with $N^* = \lceil x^* \rceil = 4922.$ Let's first check $$\tilde{q}(N^*) = \frac{3 \cdot (4 \cdot 4922 -7)}{16 \cdot 4921} = \frac{59043}{78736} \approx 0.7498856939.....,$$ which is roughly $6 \times 10^{-9}$ larger than $p.$ Since $9 \cdot (-3)^{-N^*} \ll 10^{-9},$ we can confirm that $N^* = 4922$ is the smallest integer value such that if you fell asleep and randomly woke up to some wizardling ahead of you in line is being sorted to Graphindor then your probability of also getting sorted to Graphindor is $q(N) \gt p = \frac{1640}{2187}.$

Is that what squaring the circle means?

A pseudo-square has the following properties:

1. It is a simple, closed curve.
2. It has four sides, all the same length.
3. Each side is either a straight line segment or the arc of a circle.
4. The four sides are joined at four corners, with each corner having an internal angle of 90 degrees or 270 degrees.

The pseudo-square pictured above has two straight sides, which run radially between arcs of two concentric circles. Assuming this is a unit pseudo-square (i.e., each side has length 1), what is its area?

As you can see, I've pre-doctored the image from the prompt with some parameters. Let $r$ be the radius of the smaller circle and let $\theta$ be the angle inscribed between the two straight line edges. From here, if the shape is a unit pseudo-square then the larger radius is $1+r,$ so we can find the formula for the area of the shape in terms of $r$ and $\theta,$ as $$A(r,\theta) = \pi r^2 + \frac{1}{2} \theta \left((1+r)^2 - r^2\right) = \pi r^2 + \frac{1}{2} \theta (1 + 2r).$$ That is all well and good, but we now have to find the particular value of $r$ and theta that allow for this shape to be unit pseudo-square. In particular, the length of the arc on the larger of the two concentric circles is $$\ell = \theta (1 + r).$$ The length of the other arc is $$\tilde{\ell} = (2\pi - \theta) r.$$ Since the shape is a unit pseudo-square we have the nonlinear system of equations \begin{align*} \theta ( 1 + r) &= 1 \\ (2\pi - \theta) r &= 1.\end{align*} By setting $\theta = (1 + r)^{-1}$ and plugging into the second equation we get $$\left(2\pi - \frac{1}{1+r}\right) r = 1,$$ which is equivalent to the quadratic equation $$2\pi r^2 + 2(\pi - 1) r - 1 = 0.$$ Thus, if the shape is a unit pseudo-square then the smaller radius $r$ is equal to $$r^* = \frac{1-\pi + \sqrt{1+\pi^2}}{2\pi}.$$

By plugging $\theta = (1+r)^{-1}$ into the area formula we get $A(r) = \pi r^2 + \frac{1+2r}{2(1+r)},$ so plugging in $r^*$ from above we get the area of the unit psuedo-square with two straight lines is \begin{align*}A^* = A(r^*) &= \pi \left( \frac{1-\pi + \sqrt{1+\pi^2}}{2\pi} \right)^2 + \frac{ 1 + 2 \frac{1-\pi + \sqrt{1+\pi^2}}{2\pi} }{2 \left( 1 + \frac{1-\pi + \sqrt{1+\pi^2}}{2\pi} \right)}\\ &= \frac{1+\sqrt{1+\pi^2}}{2\pi} \approx 0.683874197466......\end{align*}

Can you find a unit pseudo-square that has three curved sides and just one straight side? What is the area of your new unit pseudo-square?

Without loss of generality, we can assume that the one flat side is positioned along the bottom. We would need to have two curved sides connected to this flat bottom that curve towards each other, with there being a third circle that is tangent to the circular arcs. The resulting shape is sort of like the shape of some pawns in chess. See the figure below. We again insert some parameters. Let the flat side be the line segment from $(-\frac{1}{2},0)$ to $(\frac{1}{2},0).$ Let the two symmetric sides attached to flat bottom be arcs of the circles centered at $(-a,0)$ and $(a,0),$ respectively, each with radius $a+\frac{1}{2},$ with subtended angle $\theta$. Let the final arc be from the circle centered $(0,b)$ with radius $r$ and subtended angle $2(\pi - \theta).$

Let's first try to figure out how to quantify the area of the pseudo-square with three curved sides. The region denoted by $B$ has area given by $$A_B = \frac{1}{2} (\pi - \theta) r^2.$$ The region denoted by $C$ has area given by $$A_C = \frac{1}{2} r^2 \tan \theta.$$ Finally, the region denoted by $D$ has aread given by $$A_D = \frac{1}{2} \theta \left(a + \frac{1}{2}\right)^2 - \frac{1}{2} a^2 \tan \theta.$$ The area of the entire pseudo-square with three curved sides is thus \begin{align*}A = A(a,r,\theta) &= 2 \left(A_B + A_C + A_D\right) \\ &= (\pi - \theta + \tan \theta) r^2 + \theta \left(a + \frac{1}{2}\right)^2 - a^2 \tan \theta.\end{align*}

With some creative trigonometry we can obtain $r = r(a,\theta),$ thus reducing the dimensions of the problem a smidge. The region denoted by $C$ is a triangle whose height is $r$ and base $\beta,$ which is some portion of line segment of total length $a + \frac{1}{2},$ since that line segment is a radius of the circle centered at $(-a,0)$ of radius $a+\frac{1}{2}.$ Since the line segment, negative $x$-axis and positive $y$-axis form a triangle, we can compute $\beta$ as $$\beta = a + \frac{1}{2} - a\sec \theta.$$ Since $r = \beta \cot \theta,$ we have $$r = r(a,\theta) = \left( \left(a+\frac{1}{2}\right) - a \sec \theta \right) \cot \theta = \frac{ (a + \frac{1}{2}) \cos \theta - a }{ \sin \theta }.$$ Therefore, we have $$A = A(a,\theta) = (\pi - \theta + \tan \theta) \left( \frac{ \left(a + \frac{1}{2}\right) \cos \theta - a }{\sin \theta} \right)^2 + \theta \left(a + \frac{1}{2} \right)^2 - a^2 \tan \theta.$$

OK, now that that significantly more intricate foundational work is out of the way, we need to ensure that each of these curves sides is unit length. Since the more vertical arcs are symmetric, we only need to quantify $\ell=(a+\frac{1}{2}) \theta$ and $\tilde{\ell} = 2(\pi - \theta) r,$ and set them both equal to $1$ to obtain the nonlinear system of equations \begin{align*} (a + \frac{1}{2}) \theta &= 1 \\ 2(\pi - \theta) r = (\pi - \theta) \frac{(a+1/2)\cos \theta - a}{\sin \theta} &= 1\end{align*} Solving for $a$ in the second equation and then plugging back into the first we get $$\frac{ \sin \theta - \pi + \theta }{ 2(\pi - \theta) ( \cos \theta - 1) } \theta = 1.$$ This non-linear equation is solved with $$\theta^* \approx 0.74960359...$$ which leads to $$a^* = \frac{2-\theta^*}{2\theta^*} \approx 0.8340377...$$ which ultimately leads to the area of a unit pseudo-square with three curved sides of $$A^* = A(a^*, \theta^*) \approx 0.8317044...$$