\documentclass[amssymb,twocolumn,pra,10pt,aps]{revtex4-1}
\usepackage{mathptmx,amsmath,amsthm,hyperref}

\newtheorem{lemma}{Lemma}
\newtheorem{cor}[lemma]{Corollary}
\newtheorem*{lemma*}{Lemma}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\ZZ}{\mathbb{Z}}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\Trace}{Trace}
\newcommand{\ee}{\ell}

\begin{document}
\title{Solutions to the 82nd William Lowell Putnam Mathematical Competition \\
    Saturday, December 4, 2021}
\author{Manjul Bhargava, Kiran Kedlaya, and Lenny Ng}
\noaffiliation
\maketitle

\begin{itemize}
\item[A1]
The answer is $578$. 

Each hop corresponds to adding one of the $12$ vectors $(0,\pm 5)$, $(\pm 5,0)$, $(\pm 3,\pm 4)$, $(\pm 4,\pm 3)$ to the position of the grasshopper. Since $(2021,2021) = 288(3,4)+288(4,3)+(0,5)+(5,0)$, the grasshopper can reach $(2021,2021)$ in $288+288+1+1=578$ hops.

On the other hand, let $z=x+y$ denote the sum of the $x$ and $y$ coordinates of the grasshopper, so that it starts at $z=0$ and ends at $z=4042$. Each hop changes the sum of the $x$ and $y$ coordinates of the grasshopper by at most $7$, and $4042 > 577 \times 7$; it follows immediately that the grasshopper must take more than $577$ hops to get from $(0,0)$ to $(2021,2021)$.

\noindent
\textbf{Remark.}
This solution implicitly uses the distance function 
\[
d((x_1, y_1), (x_2, y_2)) = |x_1 - x_2| + |y_1 - y_2|
\]
on the plane, variously called the \emph{taxicab metric}, the \emph{Manhattan metric}, or the \emph{$L^1$-norm} (or $\ell_1$-norm).

\item[A2]
The limit is $e$.

\noindent
\textbf{First solution.}
By l'H\^opital's Rule, we have
\begin{align*}
&\lim_{r\to 0} \frac{\log((x+1)^{r+1}-x^{r+1})}{r} \\
&\quad = \lim_{r\to 0} \frac{d}{dr} \log((x+1)^{r+1}-x^{r+1}) \\
&\quad = \lim_{r\to 0} \frac{(x+1)^{r+1}\log(x+1)-x^{r+1}\log x}{(x+1)^{r+1}-x^{r+1}} \\
&\quad = (x+1)\log(x+1)-x\log x,
\end{align*}
where $\log$ denotes natural logarithm. It follows that $g(x) = e^{(x+1)\log(x+1)-x\log x} = \frac{(x+1)^{x+1}}{x^x}$. Thus
\[
\lim_{x\to\infty} \frac{g(x)}{x} = \left(\lim_{x\to\infty}\frac{x+1}{x}\right) \cdot \left(\lim_{x\to\infty} \left(1+\frac{1}{x}\right)^x\right) = 1\cdot e = e.
\]

\noindent
\textbf{Second solution.}
We first write 
\begin{align*}
\lim_{x \to \infty} \frac{g(x)}{x} &= \lim_{x \to \infty} \lim_{r \to 0} \frac{((x+1)^{r+1} - x^{r+1})^{1/r}}{x} \\
&= \lim_{x \to \infty} \lim_{r \to 0} \frac{((r+1) x^r + O(x^{r-1}))^{1/r}}{x}.
\end{align*}
We would like to interchange the order of the limits, but this requires some justification.
Using Taylor's theorem with remainder, for $x \geq 1$, $r \leq 1$
we can bound the error term $O(x^{r-1})$ in absolute value by $(r+1) r x^{r-1}$. This
means that if we continue to rewrite the orginial limit as
\[
\lim_{r\to 0} \lim_{x\to\infty} (r+1+O(x^{-1}))^{1/r},
\]
the error term $O(x^{-1})$ is bounded in absolute value by $(r+1) r/x$.
For $x \geq 1$, $r \leq 1$ this quantity is bounded in absolute value by $(r+1)r$, \emph{independently of $x$}. This allows us to continue by interchanging the order of the limits,
obtaining 
\begin{align*}
&\lim_{r\to 0} \lim_{x\to\infty} (r+1+O(x^{-1}))^{1/r} \\
&\quad = \lim_{r\to 0} (r+1)^{1/r} \\
&\quad = \lim_{s\to \infty} (1+1/s)^{s} = e,
\end{align*}
where in the last step we take $s = 1/r$.

\noindent
\textbf{Third solution.} (by Clayton Lungstrum)
We first observe that
\begin{align*}
((x+1)^{r+1} - x^{r+1})^{1/r}
&= \left( \int_x^{x+1} (r+1)u^r\,du \right)^{1/r} \\
&= (r+1)^{1/r} \left( \int_x^{x+1} u^r\,du \right)^{1/r}.
\end{align*}
Since $\lim_{r \to 0} (r+1)^{1/r} = e$, we deduce that
\[
g(x) = e \lim_{r \to 0} \left( \int_x^{x+1} u^r\,du \right)^{1/r}.
\]
For $r > 0$, $u^r$ is increasing for $x \leq u \leq x+1$, so
\[
x^r \leq \int_x^{x+1} u^r\,du \leq (x+1)^r;
\]
for $r < 0$, $u^r$ is decreasing for $x \leq u \leq x+1$, so
\[
x^r \geq \int_x^{x+1} u^r\,du \geq (x+1)^r.
\]
In both cases, we deduce that
\[
x \leq \left( \int_x^{x+1} u^r\,du \right)^{1/r} \leq x+1;
\]
applying the squeeze theorem to the resulting inequality
 $e \leq \frac{g(x)}{x} \leq e\left( 1 + \frac{1}{x} \right)$
 yields the claimed limit.

\item[A3]
The integers $N$ with this property are those of the form $3m^2$ for some positive integer $m$.

In one direction, for $N = 3m^2$, the points
\[
(m,m,m), (m,-m,-m), (-m,m,-m), (-m,-m,m)
\]
form the vertices of a regular tetrahedron inscribed in the sphere $x^2 + y^2 + z^2 = N$.

Conversely, suppose that $P_i = (x_i, y_i, z_i)$ for $i=1,\dots,4$ are the vertices of an inscribed regular 
tetrahedron. Then the center of this tetrahedron must equal the center of the sphere, namely $(0,0,0)$. Consequently, these four vertices together with $Q_i = (-x_i, -y_i, -z_i)$ for $i=1,\dots,4$ form the vertices of an inscribed cube in the sphere.
The side length of this cube is $(N/3)^{1/2}$, so its volume is $(N/3)^{3/2}$;
on the other hand, this volume also equals the determinant of the matrix
with row vectors $Q_2-Q_1, Q_3-Q_1, Q_4-Q_1$, which is an integer. Hence $(N/3)^3$ is a perfect square, as then is $N/3$.

\item[A4]
The limit exists and equals $\frac{\sqrt{2}}{2} \pi \log 2$.

We first note that we can interchange $x$ and $y$ to obtain
\[
I(R) = \iint_{x^2+y^2 \leq R^2} \left( \frac{1+2y^2}{1+x^4+6x^2y^2+y^4} - \frac{1+x^2}{2+x^4+y^4} \right)\,dx\,dy.
\]
Averaging the two expressions for $I(R)$ yields
\[
I(R) = \iint_{x^2+y^2 \leq R^2} (f(x,y) - g(x,y))\,dx\,dy
\]
where
\begin{align*}
f(x,y) &= \frac{1+x^2+y^2}{1 + x^4 + 6x^2y^2 + y^4} \\
g(x,y) &= \frac{1+x^2/2+y^2/2}{2 + x^4 + y^4}.
\end{align*}
Now note that
\[f(x,y) = 2 g(x+y, x-y).
\]
We can thus write
\[
I(R) = \iint_{R^2 \leq x^2 +y^2 \leq 2R^2} g(x,y)\,dx\,dy.
\]
To compute this integral, we switch to polar coordinates:
\begin{align*}
I(R) &= \int_R^{R\sqrt{2}} \int_0^{2\pi} g(r\cos \theta, r \sin \theta)r\,dr\,d\theta \\
&=  \int_R^{R\sqrt{2}} \int_0^{2\pi} \frac{1 + r^2/2}{2 + r^4(1 - (\sin^2 2\theta)/2)} r\,dr\,d\theta.
\end{align*}
We rescale $r$ to remove the factor of $R$ from the limits of integration:
\begin{align*}
I(R) & =  \int_1^{\sqrt{2}} \int_0^{2\pi} \frac{1 + R^2 r^2/2}{2 + R^4 r^4(1 - (\sin^2 2\theta)/2)} R^2 r\,dr\,d\theta.
\end{align*}

Since the integrand is uniformly bounded for $R \gg 0$, we may take the limit over $R$ through the integrals to obtain
\begin{align*}
\lim_{R \to \infty} I(R) &= \int_1^{\sqrt{2}} \int_0^{2\pi} \frac{r^2/2}{r^4(1 - (\sin^2 2\theta)/2)} r\,dr\,d\theta \\
&= \int_1^{\sqrt{2}} \frac{dr}{r} \int_0^{2\pi} \frac{1}{2- \sin^2 2\theta} d\theta \\
&= \log \sqrt{2} \int_0^{2\pi} \frac{1}{1 + \cos^2 2\theta} d\theta \\
&= \frac{1}{2} \log 2 \int_0^{2\pi} \frac{2}{3 + \cos 4\theta} d\theta.
\end{align*}
It thus remains to evaluate 
\[
\int_0^{2\pi} \frac{2}{3 + \cos 4\theta} d\theta = 
2 \int_0^{\pi} \frac{2}{3 + \cos \theta} d\theta.
\]
One option for this is to use the half-angle substitution $t = \tan (\theta/2)$ to get
\begin{align*}
\int_{-\infty}^\infty \frac{4}{3(1+t^2) + (1-t^2)}\,dt
&= \int_{-\infty}^\infty \frac{2}{2+t^2}\,dt \\
&= \sqrt{2} \arctan \left( \frac{x}{\sqrt{2}} \right)^{\infty}_{-\infty} \\
&= \sqrt{2} \pi.
\end{align*}
Putting this together yields the claimed result.

\item[A5]
The values of $j$ in question are those not divisible by either $42$ or $46$.

We first check that for $p$ prime,
\[
\sum_{n=1}^{p-1} n^j \equiv 0 \pmod{p} \Leftrightarrow j \not\equiv 0 \pmod{p-1}.
\]
If $j \equiv 0 \pmod{p-1}$, then $n^j \equiv 1 \pmod{p}$ for each $n$, so $\sum_{n=1}^{p-1} n^j \equiv p-1 \pmod{p}$. If $j \not\equiv 0 \pmod{p-1}$, we can pick a primitive root $m$ modulo $p$,
observe that $m^j \not\equiv 1 \pmod{p}$, and then note that
\[
\sum_{n=1}^{p-1} n^j \equiv \sum_{n=1}^{p-1} (mn)^j = m^j \sum_{n=1}^{p-1} n^j \pmod{p},
\]
which is only possible if $\sum_{n=1}^{p-1} n^j \equiv 0 \pmod{p}$.

We now note that the prime factorization of 2021 is $43 \times 47$,
so it suffices to determine when $S(j)$ is divisible by each of 43 and 47.
We have
\begin{align*}
S(j) &\equiv 46 \sum_{n=1}^{42} n^j \pmod{43} \\
S(j) &\equiv 42 \sum_{n=1}^{46} n^j \pmod{47}.
\end{align*}
Since 46 and 42 are coprime to 43 and 47, respectively, 
we have 
\begin{gather*}
S(j) \equiv 0 \pmod{43} \Leftrightarrow j \not\equiv 0 \pmod{42} \\
S(j) \equiv 0 \pmod{47} \Leftrightarrow j \not\equiv 0 \pmod{46}.
\end{gather*}
This yields the claimed result.

\item[A6]
Yes, it follows that $P(2)$ is a composite integer. (Note: 1 is neither prime nor composite.)

Write $P(x) = a_0 + a_1 x + \cdots + a_n x^n$ with $a_i \in \{0,1\}$ and $a_n = 1$.
Let $\alpha$ be an arbitrary root of $P$. Since $P(\alpha) = 0$, $\alpha$ cannot be a positive real number.
%In addition, if $\alpha \neq 0$ then
%\begin{align*}
%1 &< |a_{n-1} \alpha^{-1} + \cdots + a_0 \alpha^{-n}| \\
%&\leq |\alpha|^{-1} + \cdots + |\alpha|^{-n}
%\end{align*}
%and so $|\alpha| < 2$.
%
In addition, if $\alpha \neq 0$ then
\begin{align*}
|1 + a_{n-1} \alpha^{-1}| &= |a_{n-2} \alpha^{-2} + \cdots + a_0 \alpha^{-n}| \\
&\leq |\alpha|^{-2} + \cdots + |\alpha|^{-n}.
\end{align*}
If $\alpha \neq 0$ and $\mathrm{Re}(\alpha) \geq 0$, then $\mathrm{Re}(1 + a_{n-1} \alpha^{-1}) \geq 1$
and 
\[
1 \leq |\alpha|^{-2} + \cdots + |\alpha|^{-n} < \frac{|\alpha|^{-2}}{1 - |\alpha|^{-1}};
\]
this yields $|\alpha| < (1 + \sqrt{5})/2$.

By the same token, if $\alpha \neq 0$ then
\[
|1 + a_{n-1} \alpha^{-1} + a_{n-2} \alpha^{-2}| \leq |\alpha|^{-3} + \cdots + |\alpha|^{-n}.
\]
We deduce from this that $\mathrm{Re}(\alpha) \leq 3/2$ as follows.
\begin{itemize}
\item
There is nothing to check if $\mathrm{Re}(\alpha) \leq 0$.
\item
If the argument of $\alpha$ belongs to $[-\pi/4, \pi/4]$, then $\mathrm{Re}(\alpha^{-1}), \mathrm{Re}(\alpha^{-2}) \geq 0$, so
\[
1 \leq |\alpha|^{-3} + \cdots + |\alpha|^{-n} < \frac{|\alpha|^{-3}}{1 - |\alpha|^{-1}}.
\]
Hence $|\alpha|^{-1}$ is greater than the unique positive root of $x^3 + x - 1$, which 
is greater than $2/3$. 
\item
Otherwise, $\alpha$ has argument in $(-\pi/2,\pi/4) \cup (\pi/4,\pi/2)$,
so the bound $|\alpha| < (1 + \sqrt{5})/2$ implies that $\mathrm{Re}(\alpha) < (1 + \sqrt{5})/(2 \sqrt{2}) < 3/2$.
\end{itemize}

By hypothesis, there exists a factorization $P(x) = Q(x)R(x)$ into two nonconstant integer polynomials, which we may assume are monic.
$Q(x + 3/2)$ is a product of polynomials, each of the form $x - \alpha$ where $\alpha$ is a real root of $P$
or of the form
\begin{align*}
&\left( x + \frac{3}{2} - \alpha\right) \left(x + \frac{3}{2} - \overline{\alpha} \right) \\
&\quad = x^2 + 2 \mathrm{Re}\left(\frac{3}{2} - \alpha\right) x + \left|\frac{3}{2} - \alpha \right|^2
\end{align*}
where $\alpha$ is a nonreal root of $P$. It follows that $Q(x+3/2)$ has positive coefficients;
comparing its values at $x=1/2$ and $x=-1/2$ yields $Q(2) > Q(1)$. We cannot have $Q(1) \leq 0$, as otherwise the intermediate value theorem would imply that $Q$ has a real root in $[1, \infty)$; hence $Q(1)  \geq 1$ and so $Q(2) \geq 2$.
Similarly $R(2) \geq 2$, so $P(2) = Q(2) R(2)$ is composite.

\noindent
\textbf{Remark.}
A theorem of Brillhart, Filaseta, and Odlyzko from 1981 states that if a prime $p$ is written as $\sum_i a_i b^i$ in any base $b \geq 2$, the polynomial $\sum_i a_i x^i$ is irreducible.
(The case $b=10$ is an older result of Cohn.) 
The solution given above is taken from: Ram Murty, Prime numbers and irreducible polynomials, \textit{Amer. Math. Monthly} \textbf{109} (2002), 452--458). The final step is due to P\'olya and Szeg\H{o}.

\item[B1]
The probability is $2 - \frac{6}{\pi}$.

Set coordinates so that the original tiling includes the (filled) square 
$S = \{(x,y): 0 \leq x,y \leq 1 \}$. It is then equivalent to choose the second square by first choosing a point uniformly at random in $S$ to be the center of the square, then choosing an angle of rotation uniformly at random from the interval $[0, \pi/2]$.

For each $\theta \in [0, \pi/2]$, circumscribe a square $S_\theta$ around $S$ with angle of rotation $\theta$ relative to $S$; this square has side length $\sin \theta + \cos \theta$. Inside $S_\theta$, draw the smaller square $S_\theta'$ consisting of points at distance greater than $1/2$ from each side of $S_\theta$; this square has side length $\sin \theta + \cos \theta - 1$. 

We now verify that a unit square with angle of rotation $\theta$ fails to cover any corners of $S$ if and only if its center lies in the interior of $S_\theta'$. In one direction, if one of the corners of $S$ is covered, then that corner lies on a side of $S_\theta$ which meets the dropped square, so the center of the dropped square is at distance less than $1/2$ from that side of $S_\theta$.
To check the converse, note that
there are two ways to dissect the square $S_\theta$ into the square $S_\theta'$ plus four $\sin \theta \times \cos \theta$ rectangles. If $\theta \neq 0, \pi/4$, then one of these dissections
has the property that each corner $P$ of $S$ appears as an interior point of a side (not a corner) of one of the rectangles $R$. 
It will suffice to check that if the center of the dropped square is in $R$, then the dropped square covers $P$; this follows from the fact that $\sin \theta$ and $\cos \theta$ are both at most 1.

It follows that the conditional probability, given that the angle of rotation is chosen to be $\theta$, that the dropped square does not cover any corners of $S$ is $(\sin \theta + \cos \theta - 1)^2$. We then compute the original probability as the integral
\begin{align*}
&\frac{2}{\pi} \int_0^{\pi/2} (\sin \theta + \cos \theta - 1)^2\,d\theta \\
&\quad =
\frac{2}{\pi} \int_0^{\pi/2} (2 + \sin 2\theta - 2\sin \theta - 2 \cos \theta)\,d\theta\\
&\quad = \frac{2}{\pi} \left( 2 \theta - \frac{1}{2} \cos 2\theta + 2 \cos \theta - 2 \sin \theta \right)_0^{\pi/2} \\
&\quad = \frac{2}{\pi} \left( \pi + 1 - 2 - 2 \right) = 2 - \frac{6}{\pi}.
\end{align*}

\noindent
\textbf{Remark:} Noam Elkies has some pictures illustrating this problem:
\href{https://abel.math.harvard.edu/~elkies/putnam_b1a.pdf}{image 1},
\href{https://abel.math.harvard.edu/~elkies/putnam_b1.pdf}{image 2}.

\item[B2]
The answer is $2/3$. 

By AM-GM, we have
\begin{align*}
2^{n+1}(a_1\cdots a_n)^{1/n} &= \left((4a_1)(4^2a_2)\cdots (4^na_n)\right)^{1/n}\\
& \leq \frac{\sum_{k=1}^n (4^k a_k)}{n}.
\end{align*}
Thus
\begin{align*}
2S &\leq \sum_{n=1}^\infty \frac{\sum_{k=1}^n (4^k a_k)}{4^n} \\
&= \sum_{n=1}^\infty \sum_{k=1}^n (4^{k-n}a_k) = \sum_{k=1}^\infty \sum_{n=k}^\infty (4^{k-n}a_k) \\
&= \sum_{k=1}^\infty \frac{4a_k}{3}  = \frac{4}{3}
\end{align*}
and $S \leq 2/3$. Equality is achieved when $a_k=\frac{3}{4^k}$ for all $k$, since in this case $4a_1=4^2a_2=\cdots=4^na_n$ for all $n$.

\item[B3]
We prove the given statement.

For any circle $\mathcal{S}$ of radius $r$ whose center is at distance $d$ from the origin, express the integral in polar coordinates $s,\theta$:
\[
\iint_{\mathcal{S}} \rho = \int_{s_1}^{s_2} \int_{\theta_1(s)}^{\theta_2(s)} (yh_x - xh_y)(s \sin \theta, s \cos \theta) s\,d\theta\,ds.
\]
For fixed $s$, the integral over $\theta$ is a line integral of $\mathrm{grad} \, h$, which evaluates to $h(P_2) - h(P_1)$
where $P_1, P_2$ are the endpoints of the endpoints of the arc of the circle of radius $s$ centered at the origin lying within $\mathcal{S}$. If we now fix $r$ and $d$ and integrate $\iint_{\mathcal{S}} \rho$ over all choices of $\mathcal{S}$ (this amounts to a single integral over an angle in the range $[0, 2\pi]$), we may interchange the order of integration to first integrate over $\theta$,
then over the choice of $\mathcal{S}$, and at this point we get 0 for every $s$.
We conclude that the integral of $\iint_{\mathcal{S}}$ over all choices of $\mathcal{S}$ vanishes; since the given integral varies continuously in $\mathcal{S}$, by the intermediate value theorem there must be some $\mathcal{S}$  where the given integral is 0.

\item[B4]
We can check directly that $R_3=R_4=1$ are Virahanka--Fibonacci numbers; henceforth we will assume $m \geq 5$.

Denote the product $\prod_{k=1}^{F_m-1} k^k$ by $A$. Note that if $F_m$ is composite, say $F_m = ab$ for $a,b>1$ integers, then $A$ is divisible by $a^a b^b$ and thus by $F_m=ab$; it follows that $R_m=0=F_0$ when $F_m$ is composite.

Now suppose that $F_m$ is prime. Since $F_{2n} = F_n(F_{n+1}+F_{n-1})$ for all $n$, $F_m$ is composite if $m>4$ is even; thus we must have that $m$ is odd. Write $p=F_m$, and use $\equiv$ to denote congruence $\pmod p$. Then we have
\[
A = \prod_{k=1}^{p-1} (p-k)^{p-k} \equiv \prod_{k=1}^{p-1} (-k)^{p-k} = (-1)^{p(p-1)/2} \prod_{k=1}^{p-1} k^{p-k}
\]
and consequently
\begin{align*}
A^2 &\equiv (-1)^{p(p-1)/2} \prod_{k=1}^{p-1} (k^k k^{p-k}) \\
&= (-1)^{p(p-1)/2}((p-1)!)^p \\
&\equiv (-1)^{p(p+1)/2},
\end{align*}
where the final congruence follows from Wilson's Theorem. Now observe that when $m$ is odd, $p=F_m$ must be congruent to either $1$ or $2 \pmod{4}$: this follows from inspection of the Virahanka--Fibonacci sequence mod $4$, which has period $6$: $1,1,2,3,1,0,1,1,\ldots$. It follows that $A^2 \equiv (-1)^{p(p+1)/2} = -1$.

On the other hand, by the Kepler--Cassini identity
\[
F_n^2 = (-1)^{n+1} + F_{n-1}F_{n+1}
\]
with $n=m-1$, we have $F_{m-1}^2 \equiv (-1)^m = -1$. Thus we have
$0 \equiv A^2 - F_{m-1}^2 \equiv (A-F_{m-1})(A-F_{m-2})$. Since $p$ is prime, it must be the case that either $A=F_{m-1}$ or $A=F_{m-2}$, and we are done.

\noindent
\textbf{Remark.}
The Kepler--Cassini identity first appears in a letter of Kepler from 1608.
Noam Elkies has scanned the \href{https://people.math.harvard.edu/~elkies/Kepler_XVI_p157.jpg}{relevant page of Kepler's collected works} (slightly NSFW if your boss can read Latin).

\item[B5]
For convenience, throughout we work with matrices over the field of 2 elements. In this language, if there exists a permutation matrix $P$ such that $P^{-1} A P$ is unipotent (i.e., has 1s on the main diagonal and 0s below it), then $A$ is very odd: any principal submatrix of $A$ is conjugate to a principal submatrix of $P^{-1} A P$, which is again unipotent and in particular nonsingular.
We will solve the problem by showing that conversely, for any very odd matrix $A$, there exists a permutation matrix $P$ such that $P^{-1} A P$ is unipotent. Since the latter condition is preserved by taking powers, this will prove the desired result.

To begin, we may take $S = \{i\}$ to see that $a_{ii} = 1$. We next form a (loopless) directed graph on the vertex set $\{1,\dots,n\}$ with an edge from $i$ to $j$ whenever $a_{ij} = 1$, and claim that this graph has no cycles.
To see this, suppose the contrary,
choose a cycle of minimal length $m \geq 2$, and let $i_1,\dots,i_m$ be the vertices in order.
The minimality of the cycle implies that
\[
a_{i_j i_k} = \begin{cases} 1 & \mbox{if } k - j \equiv 0 \mbox{ or } 1 \pmod{m} \\
0 & \mbox{otherwise}.
\end{cases}
\]
The submatrix corresponding to $S = \{i_1,\dots,i_m\}$ has row sum 0 and hence is singular, a contradiction.

We now proceed by induction on $n$.
Since the directed graph has no cycles, there must be some vertex which is not the starting point of any edge
(e.g., the endpoint of any path of maximal length).
We may conjugate by a permutation matrix so that this vertex becomes 1. We now apply the induction hypothesis to the submatrix corresponding to $S = \{2,\dots,n\}$ to conclude.

\noindent
\textbf{Remark.}
A directed graph without cycles, as in our solution, is commonly called a \emph{DAG (directed acyclic graph)}. It is a standard fact that a directed graph is a TAG if and only if there is a linear ordering of its vertices consistent with all edge directions.
See for example \url{https://en.wikipedia.org/wiki/Directed_acyclic_graph}.

\noindent
\textbf{Remark.}
An $n \times n$ matrix $A = (a_{ij})$ for which the value of $a_{ij}$ depends only on $i-j \pmod{n}$ is called a \emph{circulant matrix}.
The circulant matrix with first row $(1,1,0,\dots,0)$ is an example of an $n \times n$ matrix whose determinant is even, but whose other principal minors are all odd.

\item[B6]
\noindent
\textbf{First solution.}
(based on a suggestion of Noam Elkies)
Let $f_k(x)$ be the probability distribution of $X_k$, the last number remaining when one repeatedly trims a list of $3^k$ random variables chosen with respect to the uniform distribution on $[0,1]$; note that $f_0(x) = 1$ for $x \in [0,1]$.
Let $F_k(x)=\int_0^x f_k(t)\,dt$ be the cumulative distribution function; by symmetry,
$F_k(\frac{1}{2}) = \frac{1}{2}$.
Let $\mu_k$ be the expected value of $X_k - \frac{1}{2}$; then $\mu_0 = \frac{1}{4}$, so it will suffice to prove that $\mu_{k} \geq \frac{2}{3} \mu_{k-1}$ for $k > 0$.

By integration by parts and symmetry, we have
\[
\mu_k = 2 \int_0^{1/2} \left( \frac{1}{2} - x \right) f_k(x)\,dx  = 2 \int_0^{1/2} F_k(x)\,dx;
\]
that is, $\mu_k$ computes twice the area under the curve $y = F_k(x)$ for $0 \leq x \leq\frac{1}{2}$. Since $F_k$ is a monotone function from $[0, \frac{1}{2}]$ 
with $F_k(0) = 0$ and $F_k(\frac{1}{2}) = \frac{1}{2}$, we may transpose the axes to obtain
\begin{equation} \label{eq:2021B6 eq4}
\mu_k = 2 \int_0^{1/2} \left( \frac{1}{2} - F_k^{-1}(y) \right)\,dy.
\end{equation}

Since $f_k(x)$ is the probability distribution of the median of three random variables chosen with respect to the distribution $f_{k-1}(x)$,
\begin{equation} \label{eq:2021B6 eq1}
f_k(x) = 6 f_{k-1}(x) F_{k-1}(x) ( 1-F_{k-1}(x) )
\end{equation}
or equivalently
\begin{equation} \label{eq:2021B6 eq2}
F_k(x) = 3 F_{k-1}(x)^2 - 2 F_{k-1}(x)^3.
\end{equation}
By induction, $F_k$ is the $k$-th iterate of $F_1(x) = 3x^2 -2x^3$, so
\begin{equation} \label{eq:2021B6 eq5}
F_k(x) = F_{k-1}(F_1(x)).
\end{equation}
Since $f_1(t) = 6t(1-t) \leq \frac{3}{2}$ for $t \in [0,\frac{1}{2}]$,
\[
\frac{1}{2} - F_1(x) = \int_x^{1/2} 6t(1-t)\,dt \leq \frac{3}{2}\left(\frac{1}{2}-x\right);
\]
for $y \in [0, \frac{1}{2}]$, we may take $x = F_{k}^{-1}(y)$ to obtain
\begin{equation} \label{eq:2021B6 eq3}
\frac{1}{2} - F_k^{-1}(y) \geq \frac{2}{3} \left( \frac{1}{2} - F_{k-1}^{-1}(y) \right).
\end{equation}
Using \eqref{eq:2021B6 eq5} and \eqref{eq:2021B6 eq3}, we obtain
\begin{align*}
\mu_k &= 2 \int_0^{1/2} \left( \frac{1}{2} - F_k^{-1}(y) \right) \,dy \\
&\geq \frac{4}{3} \int_0^{1/2} \left( \frac{1}{2} - F_{k-1}^{-1}(y) \right) \,dy = \frac{2}{3}\mu_{k-1}
\end{align*}
as desired.

\noindent
\textbf{Second solution.}
Retain notation as in the first solution. Again $F_k(\frac{1}{2}) = \frac{1}{2}$, so \eqref{eq:2021B6 eq1} implies
\[
f_k\left( \frac{1}{2} \right) = 6 f_{k-1} \left( \frac{1}{2} \right) \times \frac{1}{2} \times \frac{1}{2}.
\]
By induction on $k$, we deduce that %$f_k(x)$ is a polynomial in $x$,
$f_k(\frac{1}{2}) = (\frac{3}{2})^k$
and $f_k(x)$ is nondecreasing on $[0,\frac{1}{2}]$.
(More precisely, besides \eqref{eq:2021B6 eq1}, the second assertion uses that $F_{k-1}(x)$ increases from $0$ to $1/2$
and $y \mapsto y - y^2$ is nondecreasing on $[0, 1/2]$.)

The expected value of $|X_k-\frac{1}{2}|$ equals
\begin{align*}
\mu_k &= 2 \int_0^{1/2} \left( \frac{1}{2} - x \right) f_k(x)\,dx \\
&= 2 \int_0^{1/2} x f_k\left( \frac{1}{2} - x \right)\,dx.% \\
%&= \int_0^{1/2} \left( \frac{1}{2} - F_k\left( \frac{1}{2} - x \right)\right)\,dx \\
\end{align*}
%where the last step is integration by parts. Define the function
Define the function
\[
g_k(x) = \begin{cases} \left( \frac{3}{2} \right)^k & x \in \left[ 0, \frac{1}{2} \left( \frac{2}{3} \right)^k \right] \\ 0 & \mbox{otherwise}.
\end{cases}
\]
Note that for $x \in [0, 1/2]$ we have
\[
\int_0^x (g_k(t) - f_k(1/2-t))\,dt \geq 0
\]
with equality at $x=0$ or $x=1/2$. (On the interval $[0, (1/2)(2/3)^k]$ the integrand is nonnegative, so the function increases from 0; on the interval $[(1/2)(2/3)^k, 1/2]$ the integrand is nonpositive, so the function decreases to 0.)
Hence by integration by parts,
\begin{align*}
&\mu_k - 2 \int_0^{1/2} x g_k(x) \,dx \\
&\quad = \int_0^{1/2} 2x (f_k\left( \frac{1}{2} - x \right) - g_k(x)) \,dx \\
&\quad = \int_0^{1/2} x^2 \left( \int_0^x g_k(t) - \int_0^x f_k\left( \frac{1}{2} - t \right)\,dt \,dt \right)\,dx \geq 0. 
\end{align*}
(This can also be interpreted as an instance of the \emph{rearrangement inequality}.)

We now see that
\begin{align*}
\mu_k &\geq 2\int_0^{1/2} x g_k(x)\,dx \\
&\quad \geq 2 \left( \frac{3}{2} \right)^k \int_0^{(1/2)(2/3)^k} x\,dx\\
&\quad = 2 \left( \frac{3}{2} \right)^k \left. \frac{1}{2} x^2 \right|_0^{(1/2)(2/3)^k} \\
&\quad = 2 \left( \frac{3}{2} \right)^k \frac{1}{8} \left( \frac{2}{3} \right)^{2k}  = \frac{1}{4} \left( \frac{2}{3} \right)^k
\end{align*}
as desired.



\noindent
\textbf{Remark.}
For comparison, if we instead take the median of a list of $n$ numbers, the probability distribution is given by
\[
P_{2n+1}(x) = \frac{(2n+1)!}{n!n!} x^n (1-x)^n.
\]
The expected value of the absolute difference between $1/2$ and the median is 
\[
2 \int_0^{1/2} (1/2 - x) P_{2n+1}(x) dx = 2^{-2n-2}{{2n+1}\choose n}.
\]
For $n = 3^{2021}$, using Stirling's approximation this can be estimated as
$1.13 (0.577)^{2021} < 0.25 (0.667)^{2021}$. This shows that the trimming procedure produces a quantity that is on average further away from 1/2 than the median.

\end{itemize}
\end{document}



