Math Challenge Problems

Give the squares coordinates $(x,y)$ with $0\le x,y\le 4$, starting at $(0,0)$. Let $f(x,y)$ be the number of routes from the start that end by stopping at $(x,y)$. The last move into $(x,y)$ starts at some $(x',y)$ with $x'<x$ or at some $(x,y')$ with $y'<y$. So

$$f(x,y)=\sum_{x'<x} f(x',y)+\sum_{y'<y} f(x,y'),$$

with $f(0,0)=1$, and $f(1,1)=f(2,2)=f(3,3)=0$ because the rook may not stop there.

Fill in the table row by row, from the bottom. Here it is with the top row first:

$$\begin{array}{|c|c|c|c|c|}\hline 8&20&50&107&\mathbf{370}\\ \hline 4&8&17&0&107\\ \hline 2&3&0&17&50\\ \hline 1&0&3&8&20\\ \hline 1&1&2&4&8\\ \hline\end{array}$$

The bottom row is $1,1,2,4,8$: along a single row, a route to the $k$-th square is a way to cut $k$ steps into moves, and there are $2^{k-1}$ of those. The table is symmetric across the diagonal, as it should be, since swapping “right” and “up” swaps the two halves of the board. The corner gets $107+50+20+8$ from its column plus the same from its row: $2\cdot 185=370$.

The idea to keep: when you count paths, count them to every point and let the numbers build on each other.

Small cases first: $1!+24=25=5^2$ works, $2!+24=26$, $3!+24=30$ and $4!+24=48$ do not, $5!+24=144=12^2$ works, and $6!+24=744$ lies between $27^2=729$ and $28^2=784$.

For $n\ge 7$, the factorial $n!$ is divisible by $7$, so $n!+24\equiv 24\equiv 3\pmod 7$. The squares modulo $7$ are $0^2,1^2,\dots,6^2\equiv 0,1,4,2,2,4,1$. The residue $3$ is not among them, so $n!+24$ is never a square for $n\ge7$.

The answers are $n=1$ and $n=5$, with sum $6$.

Why $7$? We wanted a modulus $m$ that divides $n!$ from some point on and for which $24$ is not a square modulo $m$. Modulo $5$ it fails ($24\equiv 4$ is a square), and modulo $7$ it works.

Put $B=(0,0)$ and $C=(14,0)$. A third vertex $A=(5,12)$ gives $AB=\sqrt{25+144}=13$ and $AC=\sqrt{81+144}=15$.

Area and inradius. The height is $12$, so the area is $\tfrac12\cdot14\cdot12=84$. The semiperimeter is $s=21$, and area $=rs$ gives $r=4$.

Incenter. It lies at height $r=4$. Its foot on $BC$ is the point where the incircle touches $BC$, and the tangent length from $B$ is $s-AC=21-15=6$. So $I=(6,4)$.

Centroid. $G=\big(\tfrac{0+14+5}{3},\tfrac{0+0+12}{3}\big)=\big(\tfrac{19}{3},4\big)$.

Both points are at height $4$, so the distance is $\tfrac{19}{3}-6=\tfrac13$.

The coincidence of heights is no accident: the centroid is at one third of the height $12$, and the inradius is $84/21=4$ as well.

Measure arcs as fractions of the whole circle. The three points cut the circle into three arcs. The angle at a vertex is half of the opposite arc (the arc not containing that vertex), measured in degrees. So some angle exceeds $120^\circ$ exactly when some arc exceeds $240^\circ$, that is, $\tfrac23$ of the circle. That happens exactly when the three points lie inside an arc of length $\tfrac13$.

Now count. For a point $P$, let $E_P$ be the event “the other two points lie in the arc of length $\tfrac13$ that starts at $P$ and runs clockwise.” Each of the other points lands there with probability $\tfrac13$, independently, so $\Pr(E_P)=\tfrac19$.

If the three points fit in an arc of length $\tfrac13$, exactly one of them is the first one going clockwise inside that arc, so exactly one event $E_P$ happens. (Two events can’t both happen: that would put each of two points within $\tfrac13$ clockwise of the other, a total of less than $\tfrac23$ around the full circle.) So the events are disjoint and

$$\Pr=3\cdot\tfrac19=\tfrac13.$$

The same argument shows that $n$ random points fit in an arc of length $t\le\tfrac12$ with probability $n\,t^{\,n-1}$. With $t=\tfrac12$ and $n=3$ it gives the well-known $\tfrac34$ chance of an obtuse triangle.

Squaring the first clue, $36=(a+b+c)^2=18+2(ab+bc+ca)$, so $ab+bc+ca=9$.

By Vieta’s formulas, $a,b,c$ are the roots of $$t^3-6t^2+9t-4=0.$$ Trying $t=1$ gives $1-6+9-4=0$, and dividing out gives $t^3-6t^2+9t-4=(t-1)^2(t-4)$. So the numbers are $1,1,4$ in some order, and $$a^4+b^4+c^4=1+1+256=258.$$

Without factoring. Newton’s identities give power sums from the symmetric functions. With $p_k=a^k+b^k+c^k$, $e_1=6$, $e_2=9$, $e_3=4$: $$p_3=e_1p_2-e_2p_1+3e_3=108-54+12=66,\qquad p_4=e_1p_3-e_2p_2+e_3p_1=396-162+24=258.$$

Write $S_0=\sum_{n\ge1}3^{-n}=\tfrac12$, $S_1=\sum n\,3^{-n}$ and $S_2=\sum n^2\,3^{-n}$. All three series converge, since the terms shrink faster than $(\tfrac12)^n$ eventually.

The shift trick. For a sequence with $a_0=0$, $$\Big(1-\tfrac13\Big)\sum_{n\ge1}\frac{a_n}{3^n}=\sum_{n\ge1}\frac{a_n}{3^n}-\sum_{n\ge1}\frac{a_{n-1}}{3^{n}}=\sum_{n\ge1}\frac{a_n-a_{n-1}}{3^n}.$$

With $a_n=n$, the differences are all $1$: $\tfrac23S_1=S_0=\tfrac12$, so $S_1=\tfrac34$.

With $a_n=n^2$, the differences are $2n-1$: $\tfrac23S_2=2S_1-S_0=\tfrac32-\tfrac12=1$, so $S_2=\tfrac32$.

The picture shows the partial sums climbing toward $1.5$. The same trick works for any polynomial on top: each shift lowers the degree by one.

Let $R_k$ be the number with $k$ ones, so $R_k=\dfrac{10^k-1}{9}$. Because $\gcd(9,41)=1$, we have $41\mid R_k$ exactly when $41\mid 10^k-1$, that is, when $10^k\equiv1\pmod{41}$.

Now $99999=41\cdot 2439$, so $10^5\equiv 1\pmod{41}$, while $10\not\equiv1$. The order of $10$ modulo $41$ divides $5$ and is not $1$, so it is exactly $5$. Hence $10^k\equiv1\pmod{41}$ exactly when $5\mid k$.

So $R_k$ is divisible by $41$ exactly when $k$ is a multiple of $5$. Among $k=1,\dots,2026$ there are $\lfloor 2026/5\rfloor=405$ of these. (The first is $11111=41\cdot271$.)

Idea used: the order of a number modulo a prime. If $a^d\equiv1$ for the smallest such $d$, then $a^k\equiv1$ exactly when $d\mid k$.

The center of the disk always stays at distance exactly $1$ from the square: it slides parallel to a side, then swings around a corner on a quarter circle of radius $1$.

Which points get covered? Every point of the disk is within $1$ of the center, so within $2$ of the square. Conversely, take a point $P$ outside the square at distance $d\le 2$, and let $Q$ be the nearest point of the square. At some moment the center sits at the point $C$ that is $1$ unit from $Q$ in the direction of $P$. (On a side, $C$ is on the perpendicular through $Q$; at a corner, the disk swings through every direction.) Then $|PC|=|d-1|\le1$, so $P$ is covered.

So the swept region is everything outside the square within distance $2$ of it:

• four $2\times2$ rectangles along the sides, area $16$;
• four quarter disks of radius $2$ at the corners, which form one full disk, area $4\pi$.

Total: $16+4\pi\approx 28.57$. In general, for a convex shape with perimeter $L$ and a disk of radius $r$, the region within $2r$ has area $2rL+4\pi r^2$ (a case of Steiner’s formula for parallel bodies).

Let $f(n)$ count the good subsets of $\{1,\dots,n\}$, with $f(0)=1$ (just the empty set).

• If $n$ is not in the subset, the rest is any good subset of $\{1,\dots,n-1\}$: $f(n-1)$ ways.
• If $n$ is in it, then $n-1$ and $n-2$ are not, and the rest is any good subset of $\{1,\dots,n-3\}$: $f(n-3)$ ways.

So $f(n)=f(n-1)+f(n-3)$ for $n\ge3$, with $f(0)=1$, $f(1)=2$, $f(2)=3$. Then

$$1,\ 2,\ 3,\ 4,\ 6,\ 9,\ 13,\ 19,\ 28,\ 41,\ 60,\ 88,\ 129.$$

The last entry is $f(12)=129$.

The same split, “is the last element in or out?”, gives the Fibonacci numbers when only differences of $1$ are banned.

Let $Q(x)=xP(x)-1$. It has degree at most $5$ and vanishes at $x=1,2,3,4,5$, so $$Q(x)=c\,(x-1)(x-2)(x-3)(x-4)(x-5).$$ At $x=0$: $Q(0)=-1$ and the right side is $c\cdot(-120)$, so $c=\tfrac1{120}$.

Since $Q(x)=xP(x)-1$, the coefficient of $x$ in $Q$ is $P(0)$. In the product $(x-1)\cdots(x-5)$ the coefficient of $x$ is the sum of all products of four of the numbers $1,\dots,5$: $$120\Big(\tfrac11+\tfrac12+\tfrac13+\tfrac14+\tfrac15\Big)=274.$$ So $P(0)=\tfrac{274}{120}=\tfrac{137}{60}$.

Notice $\tfrac{137}{60}=1+\tfrac12+\tfrac13+\tfrac14+\tfrac15$. The polynomial can’t follow $1/x$ to its pole at $0$, and it lands on the harmonic number instead.

Track the total modulo $7$. After the first roll the total is $1,\dots,6$, never a multiple of $7$, so you never stop on the first roll.

After that, suppose the total is $\equiv r\pmod 7$ with $r\ne0$. Exactly one face, namely $7-r$, makes the new total a multiple of $7$. So every later roll ends the game with probability exactly $\tfrac16$, no matter what happened before.

The number of rolls after the first is therefore geometric with success chance $\tfrac16$, with mean $6$. Adding the first roll, the expected number of rolls is $1+6=7$.

The answer would still be $7$ if the die were replaced by any fair spinner that never lands on a multiple of $7$ and has one face for each nonzero remainder.

For any $2\times2$ matrix $M$, the sum of its entries is $u^{T}Mu$ with $u=\begin{pmatrix}1\\1\end{pmatrix}$.

Now $Au=\begin{pmatrix}3\\3\end{pmatrix}=3u$, so $u$ is an eigenvector with eigenvalue $3$, and $A^{10}u=3^{10}u$. Therefore $$u^{T}A^{10}u=3^{10}\,u^{T}u=2\cdot3^{10}=118098.$$

The picture shows $A$ acting on the plane: the direction $(1,1)$ is stretched by $3$, the direction $(1,-1)$ is left alone (eigenvalue $1$). That is why $A^{10}=\tfrac12\begin{pmatrix}3^{10}+1&3^{10}-1\\3^{10}-1&3^{10}+1\end{pmatrix}$.

With $x=1/n$, $$n\ln(1+x)=\frac{x-\tfrac{x^2}{2}+\tfrac{x^3}{3}-\cdots}{x}=1-\frac x2+\frac{x^2}3+O(x^3).$$ So $\left(1+\frac1n\right)^n=e\cdot\exp(u)$ with $u=-\frac x2+\frac{x^2}3+O(x^3)$. Since $e^u=1+u+\frac{u^2}2+O(u^3)$, $$e^u=1-\frac x2+\frac{x^2}3+\frac{x^2}8+O(x^3)=1-\frac x2+\frac{11}{24}x^2+O(x^3).$$ Hence $$\left(1+\frac1n\right)^n-e+\frac e{2n}=\frac{11e}{24n^2}+O\!\left(\frac1{n^3}\right),$$ and the limit is $\dfrac{11e}{24}\approx 1.2459$.

Check with numbers. For $n=10^6$, high-precision arithmetic gives $n^2[\cdots]\approx1.2458792$, against $11e/24\approx1.2458792$.

For fixed $x>0$, differentiate $\arctan(tx)$ in $t$: $\frac{\partial}{\partial t}\arctan(tx)=\frac{x}{1+t^2x^2}$. So $$\frac{\arctan(3x)-\arctan(x)}{x}=\int_1^3\frac{dt}{1+t^2x^2}.$$ Everything is positive, so we may swap the integrals (Tonelli’s theorem): $$\int_0^\infty\!\!\int_1^3\frac{dt\,dx}{1+t^2x^2}=\int_1^3\left[\frac{\arctan(tx)}{t}\right]_{x=0}^{\infty}dt=\int_1^3\frac{\pi}{2t}\,dt=\frac\pi2\ln3.$$

Known result. This is a case of Frullani’s integral: if $f$ is continuous with limits $f(0)$ and $f(\infty)$, then $\int_0^\infty\frac{f(ax)-f(bx)}{x}dx=\big(f(\infty)-f(0)\big)\ln\frac ab$. Here $f=\arctan$, $a=3$, $b=1$, and $f(\infty)-f(0)=\frac\pi2$.

Let $A$ be the adjacency matrix of rook moves on the 64 squares. The number of walks of length $4$ from $u$ to $v$ is $(A^4)_{uv}$.

All squares look alike. Any permutation of the rows and any permutation of the columns maps rook moves to rook moves, and these can send any square to any other. So every diagonal entry of $A^4$ is the same, and the answer is $\operatorname{tr}(A^4)/64$.

Eigenvalues. A move either keeps the column and changes the row, or the reverse. With $B=J-I$ (the $8\times8$ all-ones matrix minus the identity), $A=B\otimes I+I\otimes B$. The eigenvalues of $B$ are $7$ (once) and $-1$ (seven times), and the eigenvalues of $A$ are all sums $\beta+\beta'$:

• $14$, once;
• $7+(-1)=6$, $2\cdot7=14$ times;
• $-2$, $49$ times.

So $$\operatorname{tr}(A^4)=14^4+14\cdot6^4+49\cdot2^4=38416+18144+784=57344,$$ and the answer is $57344/64=896$.

A check for length 3. The same method gives $\operatorname{tr}(A^3)/64=(2744+3024-392)/64=84$. Directly: a closed walk of length $3$ is a triangle through a1, and a triangle of rook moves must lie in one row or one column. There are $\binom72$ pairs of other squares in the row and the same in the column, $42$ triangles, each walked in $2$ directions: $84$.

Carries. Doubling a digit $d$ gives $2d$. A carry goes to the next place exactly when $d\ge5$. An incoming carry never causes a new one, since $2d+1\le9$ for $d\le4$ and $2d+1-10\le9$ for $d\ge5$. Each carry turns $10$ in one place into $1$ in the next, losing $9$ from the digit sum. So $$s(2n)=2s(n)-9c(n),$$ where $c(n)$ is the number of digits of $n$ that are at least $5$. The condition $s(2n)=s(n)$ becomes $s(n)=9c(n)$.

Counting. The number $10^4$ fails, so write every other $n$ as a string of four digits with leading zeros. Call a digit big if it is $\ge5$ and small otherwise. We need digit sum $9c$ with exactly $c$ big digits. Write each big digit as $5+x$ with $0\le x\le4$; then we need four values in $0..4$ with sum $9c-5c=4c$, once the places of the big digits are chosen.

• $c=0$: sum $0$, only $0000$, which is not allowed.
• $c=1$: $4$ places, and four values in $0..4$ with sum $4$: $\binom73=35$ ways. Total $140$.
• $c=2$: $\binom42=6$ placements, and four values in $0..4$ with sum $8$: the middle coefficient of $(1+t+t^2+t^3+t^4)^4$, which is $85$. Total $510$.
• $c=3$: replacing every digit $d$ by $9-d$ swaps big and small and changes digit sum $9c$ to $36-9c$, so this case matches $c=1$: $140$.
• $c=4$: sum $36$, only $9999$.

Total: $140+510+140+1=791$.

Number the coins $0,\dots,n-1$ around the circle. Let $T_i$ be the move that flips coins $i,i+1,i+2$ (mod $n$). Flipping is adding $1$ modulo $2$, so the result of a set of moves depends only on how many times each $T_i$ is used, modulo $2$.

If $3\mid n$: impossible (an invariant). Color coin $j$ by $j\bmod 3$. Each class has $n/3$ coins, and every move flips exactly one coin of each color. So the three counts of tails change parity together. At the start all three counts are $0$. A position with exactly one tail has counts with parities $1,0,0$ in some order, which never happens.

If $3\nmid n$: possible. Doing $T_i$ then $T_{i+1}$ flips only coins $i$ and $i+3$. Chaining these, we can flip any two coins $a$ and $a+3k$. Since $\gcd(3,n)=1$, the multiples of $3$ reach every residue mod $n$, so we can flip any two coins. Now do $T_0$ (coins $0,1,2$ become tails) and then flip the pair $1,2$ back. Only coin $0$ is tails.

So the good $n$ are the ones not divisible by $3$. From $3$ to $20$ there are $18$ values, six of them multiples of $3$, leaving $12$.

Idea used: an invariant to show something is impossible, and a construction to show the rest is possible.

Reduce. The two midlines cut the square into four squares of side $\tfrac12$, and in each the nearest corner of the big square is the corner of the small square it shares. By symmetry, the answer is the average distance from a corner of a square of side $\tfrac12$ to a random point in it. Distances scale with size, so this is half of $$D=\int_0^1\!\!\int_0^1\sqrt{x^2+y^2}\,dx\,dy,$$ the average distance from a corner of the unit square.

Compute $D$. By symmetry across the diagonal, use the triangle $0\le y\le x\le1$ twice. In polar coordinates it is $0\le\theta\le\pi/4$, $0\le r\le\sec\theta$: $$D=2\int_0^{\pi/4}\!\!\int_0^{\sec\theta}r\cdot r\,dr\,d\theta=\frac23\int_0^{\pi/4}\sec^3\theta\,d\theta.$$ The standard antiderivative $\int\sec^3\theta\,d\theta=\tfrac12\big(\sec\theta\tan\theta+\ln|\sec\theta+\tan\theta|\big)$ gives $\tfrac12\big(\sqrt2+\ln(1+\sqrt2)\big)$ at $\pi/4$. So $D=\frac13\big(\sqrt2+\ln(1+\sqrt2)\big)$, and the answer is $$\frac D2=\frac{\sqrt2+\ln(1+\sqrt2)}{6}\approx0.38260.$$

With angles. Put $x=2\cos\theta$. Then $x^3-3x=8\cos^3\theta-6\cos\theta=2\cos3\theta$, so the equation says $\cos3\theta=-\tfrac12$. Three solutions with different cosines are $\theta=\tfrac{2\pi}9,\tfrac{4\pi}9,\tfrac{8\pi}9$, so $$\{a,b,c\}=\Big\{2\cos\tfrac{2\pi}9,\ 2\cos\tfrac{4\pi}9,\ 2\cos\tfrac{8\pi}9\Big\}.$$ Now $(2\cos\theta)^2-2=2\cos2\theta$. Doubling the angles sends $\tfrac{2\pi}9\to\tfrac{4\pi}9\to\tfrac{8\pi}9\to\tfrac{16\pi}9$, and $\cos\tfrac{16\pi}9=\cos\tfrac{2\pi}9$. So the map $r\mapsto r^2-2$ permutes the roots, and $$(a^2-2)(b^2-2)(c^2-2)=abc=-1$$ by Vieta’s formulas.

With the polynomial. Let $p(x)=x^3-3x+1=(x-a)(x-b)(x-c)$. Then $\prod(r-\sqrt2)=-p(\sqrt2)$ and $\prod(r+\sqrt2)=-p(-\sqrt2)$, so the product is $$p(\sqrt2)\,p(-\sqrt2)=(1-\sqrt2)(1+\sqrt2)=-1.$$ The first method explains why the answer is so simple; the second checks it.

The terms are positive and decreasing, so they have a limit $L\ge0$ with $L=L/(1+L^2)$, which forces $L=0$.

Square and flip the recursion: $$\frac1{x_{n+1}^2}=\frac{(1+x_n^2)^2}{x_n^2}=\frac1{x_n^2}+2+x_n^2.$$ Adding these for $k=0,\dots,n-1$: $$\frac1{x_n^2}=1+2n+\sum_{k=0}^{n-1}x_k^2.$$ Since $x_k^2\to0$, the average $\frac1n\sum_{k<n}x_k^2\to0$ (an average of terms that tend to $0$ tends to $0$). So $\dfrac1{n\,x_n^2}\to2$, and $$\sqrt n\,x_n\to\frac1{\sqrt2}=\frac{\sqrt2}2.$$

Method to keep: for a sequence that shrinks like $x_{n+1}=x_n-x_n^3+\cdots$, look at $1/x_n^2$, which grows by about a constant each step. The plot shows how slowly $\sqrt n\,x_n$ settles.

Volume and areas. The volume is $\tfrac16\cdot1\cdot2\cdot3=1$. The faces on the coordinate planes have areas $\tfrac12\cdot1\cdot2=1$, $\tfrac12\cdot1\cdot3=\tfrac32$ and $\tfrac12\cdot2\cdot3=3$. The slanted face has area $\tfrac12\big|(-1,2,0)\times(-1,0,3)\big|=\tfrac12|(6,3,2)|=\tfrac72$. The total is $S=9$.

Four pyramids. Joining the center to the four faces cuts the solid into pyramids of height $r$, so $V=\tfrac13rS$ and $r=\dfrac{3V}{S}=\dfrac39=\dfrac13$.

A second way. The center is at distance $r$ from the three coordinate planes, so it is $(r,r,r)$. The slanted face lies on $6x+3y+2z=6$, whose normal $(6,3,2)$ has length $7$. The distance condition is $\dfrac{6-11r}{7}=r$, so $r=\tfrac13$.

The neat face area $\tfrac72$ comes from a 3D Pythagorean theorem (de Gua’s theorem): the square of the slanted area equals the sum of the squares of the other three, $1+\tfrac94+9=\tfrac{49}4$.

A non-attacking placement is a permutation $\sigma$ of $\{1,\dots,8\}$, and we need $\sigma(i)\ne i$ and $\sigma(i)\ne9-i$ for every $i$.

Inclusion and exclusion. Let $r_k$ be the number of ways to put $k$ non-attacking rooks on forbidden squares. The standard rook-polynomial count is $$N=\sum_{k=0}^{8}(-1)^k\,r_k\,(8-k)!.$$ (Each placement on forbidden squares can be completed in $(8-k)!$ ways, and the signs cancel the overcounting.)

Blocks. The forbidden squares in rows $i$ and $9-i$ are exactly the four squares where those rows meet columns $i$ and $9-i$. For $i=1,2,3,4$ this gives four full $2\times2$ blocks, and different blocks share no row or column. A full $2\times2$ block holds $0$, $1$ or $2$ non-attacking rooks in $1$, $4$, $2$ ways, so $$\sum_k r_kx^k=(1+4x+2x^2)^4=1+16x+104x^2+352x^3+664x^4+704x^5+416x^6+128x^7+16x^8.$$

Sum. $$N=40320-80640+74880-42240+15936-4224+832-128+16=4752.$$

Known tool: rook polynomials (Kaplansky and Riordan, 1946), which turn “avoid these squares” into a polynomial that multiplies across independent blocks.

Group the squares by how they relate to h8:

• A: on the 8th rank or the h-file, but not h8 ($14$ squares);
• B: on neither ($49$ squares, including a1).

Moves from B. Of the $7$ moves along its row, one lands on the h-file; of the $7$ along its column, one lands on the 8th rank. So $B\to A$ with probability $\tfrac2{14}=\tfrac17$, and otherwise it stays in $B$.

Moves from A. Say the rook is on the 8th rank. Of its $7$ row moves, one reaches h8 and six stay on the 8th rank (state A). All $7$ column moves leave the 8th rank and the column is not h, so they go to B. So from A: h8 with probability $\tfrac1{14}$, A with $\tfrac6{14}$, B with $\tfrac12$.

Equations. With $E_A,E_B$ the expected remaining moves, $$E_B=1+\tfrac17E_A+\tfrac67E_B,\qquad E_A=1+\tfrac37E_A+\tfrac12E_B.$$ The first gives $E_B=7+E_A$. Putting this into the second: $\tfrac47E_A=\tfrac92+\tfrac12E_A$, so $E_A=63$ and $E_B=70$.

Starting at a1, which is in B, the answer is $70$. Compare: the expected time for a random walk on this board to return to h8 is $64$ (Kac’s lemma: one over the share of time the walk spends there, which is $\tfrac1{64}$ since every square has the same number of moves).

Since $A^3=I$, the minimal polynomial of $A$ divides $x^3-1=(x-1)(x-\omega)(x-\bar\omega)$, which has distinct roots. So $A$ is diagonalizable over $\mathbb C$, with eigenvalues in $\{1,\omega,\bar\omega\}$.

$A$ is real, so its characteristic polynomial is real, and $\omega$ and $\bar\omega$ have the same multiplicity $m$. The eigenvalue $1$ has multiplicity $4-2m$.

• $m=0$: all eigenvalues are $1$, and a diagonalizable matrix with only the eigenvalue $1$ is $I$. Not allowed.
• $m=1$: trace $2+\omega+\bar\omega=2-1=1$.
• $m=2$: trace $2(\omega+\bar\omega)=-2$.

Both happen. Let $R=\begin{pmatrix}0&-1\\1&-1\end{pmatrix}$, a matrix with $R^3=I$ and trace $-1$ (it is similar to a rotation by $120^\circ$). The block matrices $\operatorname{diag}(1,1,R)$ and $\operatorname{diag}(R,R)$ have traces $1$ and $-2$.

The sum of the possible traces is $1+(-2)=-1$.

Let $t_n=\tfrac{n(n+1)}2$, the triangular numbers, with $t_0=0$. Then $$t_n-t_{n-1}=n,\qquad 1+t_nt_{n-1}=1+\frac{n^2(n^2-1)}4=\frac{n^4-n^2+4}4.$$ So $$\frac{4n}{n^4-n^2+4}=\frac{t_n-t_{n-1}}{1+t_nt_{n-1}}.$$ For $a,b\ge0$, the difference $\arctan a-\arctan b$ lies in $(-\tfrac\pi2,\tfrac\pi2)$ and its tangent is $\frac{a-b}{1+ab}$, so it equals $\arctan\frac{a-b}{1+ab}$. Hence each term is $\arctan t_n-\arctan t_{n-1}$, and $$\sum_{n=1}^{N}=\arctan t_N-\arctan t_0=\arctan\frac{N(N+1)}2\ \longrightarrow\ \frac\pi2.$$

Picture. Draw the points $(1,t_n)$. The $n$-th term is the angle between the rays to $(1,t_{n-1})$ and $(1,t_n)$. The rays climb toward the vertical, so the angles add up to a right angle.

Base 7. $2026=5\cdot343+6\cdot49+2\cdot7+3$, so $2026=(5623)_7$.

Lucas’s theorem (Édouard Lucas, 1878). If $n=(n_r\dots n_0)_p$ and $k=(k_r\dots k_0)_p$ in base $p$, then $$\binom nk\equiv\prod_i\binom{n_i}{k_i}\pmod p.$$ A factor is $0$ when $k_i>n_i$. Otherwise it is $\frac{n_i!}{k_i!(n_i-k_i)!}$ with $n_i<7$, and no factorial below $7!$ contains the prime $7$, so the factor is not divisible by $7$.

So $\binom{2026}{k}$ is not divisible by $7$ exactly when every base-7 digit of $k$ is at most the matching digit of $2026$. The choices are $0..5$, $0..6$, $0..2$, $0..3$: $$6\cdot7\cdot3\cdot4=504.$$

Picture. Color Pascal’s triangle by whether entries are divisible by $7$, and a pattern of triangles inside triangles appears. Lucas’s theorem explains it: the rows $0..6$ form a small triangle, and every block of $7$ rows repeats it, scaled up.

Burnside’s lemma. The number of different paintings equals the average, over all rotations $g$, of the number of paintings that $g$ leaves unchanged. A painting is unchanged by $g$ exactly when every cycle of edges under $g$ has one color, so $g$ fixes $2^{c(g)}$ paintings, where $c(g)$ is its number of edge cycles.

The $12$ rotations.

• The identity: $6$ cycles, $2^6=64$.
• Turns by $\pm120^\circ$ about an axis through a vertex and the center of the opposite face: $8$ of them. They cycle the three edges at the vertex and the three edges of the opposite face: $2$ cycles, $2^2=4$ each.
• Half-turns about an axis through the midpoints of two opposite edges: $3$ of them. They fix those two edges and swap the other four in two pairs: $4$ cycles, $2^4=16$ each.

$$\frac{64+8\cdot4+3\cdot16}{12}=\frac{144}{12}=12.$$

A surprise. A painting is a graph on the $4$ vertices (the red edges), and there are only $11$ graphs on $4$ vertices up to relabeling. Relabeling allows reflections, but rotations alone do not. One graph splits in two: the path with three edges. Its only symmetries, doing nothing and reversing it, are both rotations of the tetrahedron. So no reflection maps that painting to itself, and its mirror image is a different painting.

Rewrite. Write $y=n/k$. Then $\lfloor2y\rfloor$ is odd exactly when $\{y\}\ge\tfrac12$, where $\{y\}$ is the fractional part. So $c(n)/n=\frac1n\sum_{k=1}^n g(k/n)$ with $$g(x)=\begin{cases}1&\text{if }\{1/x\}\ge\tfrac12,\\0&\text{otherwise.}\end{cases}$$

Riemann sum. On $[\delta,1]$, $g$ is bounded with finitely many jumps, so it is Riemann integrable there and the part of the sum with $k\ge\delta n$ tends to $\int_\delta^1g$. The rest of the sum has at most $\delta n+1$ terms, each at most $\tfrac1n$, and $\int_0^\delta g\le\delta$. Letting $\delta\to0$, the limit is $\int_0^1g(x)\,dx$.

The integral. $g(x)=1$ when $1/x\in[m+\tfrac12,\,m+1)$ for an integer $m\ge1$, that is, when $x\in\big(\tfrac1{m+1},\tfrac2{2m+1}\big]$. These intervals have total length $$\sum_{m\ge1}\Big(\frac2{2m+1}-\frac2{2m+2}\Big)=2\Big(\frac13-\frac14+\frac15-\frac16+\cdots\Big)=2\Big(\ln2-1+\frac12\Big)=2\ln2-1,$$ using $1-\tfrac12+\tfrac13-\cdots=\ln2$.

So $c(n)/n\to2\ln2-1\approx0.3863$. The plot shows $c(n)/n$ settling toward that line.

Gauss’s identity. For every $m$, $\sum_{d\mid m}\varphi(d)=m$. Apply it to $m=\gcd(i,j)$: the divisors of $\gcd(i,j)$ are the common divisors of $i$ and $j$, so $$\gcd(i,j)=\sum_{d=1}^{10}E_{id}\,\varphi(d)\,E_{jd},\qquad E_{id}=\begin{cases}1&d\mid i\\0&\text{otherwise.}\end{cases}$$

So $M=E\,D\,E^{T}$ with $D=\operatorname{diag}(\varphi(1),\dots,\varphi(10))$. The matrix $E$ is lower triangular (a divisor of $i$ is at most $i$) with ones on the diagonal, so $\det E=1$ and $$\det M=\prod_{d=1}^{10}\varphi(d)=1\cdot1\cdot2\cdot2\cdot4\cdot2\cdot6\cdot4\cdot6\cdot4=18432.$$

Known result: this is Smith’s determinant (H. J. S. Smith, 1876): $\det[\gcd(i,j)]_{i,j\le n}=\prod_{d\le n}\varphi(d)$.

The model. Breaking at two uniform points gives lengths $(a,b,c)$ that are uniformly distributed on the triangle $\{a+b+c=1,\ a,b,c\ge0\}$. (The two break points, sorted, are uniform on a triangle in the plane, and the lengths are a linear function of them.) The six orderings of $(a,b,c)$ are equally likely, so the sorted lengths $s\le m\le\ell$ are uniform on one sixth of it.

Coordinates. Use $(s,m)$, with $\ell=1-s-m$. The sorted region is $0\le s\le m\le\frac{1-s}2$, a triangle with corners $(0,0)$, $(0,\tfrac12)$, $(\tfrac13,\tfrac13)$ and area $\tfrac1{12}$.

The condition. “No piece more than twice another” means $\ell\le2s$, that is, $m\ge1-3s$. Inside the sorted region this cuts out the triangle bounded by $m=s$, $m=1-3s$ and $m=\tfrac{1-s}2$. Its corners are $$\big(\tfrac14,\tfrac14\big),\quad\big(\tfrac13,\tfrac13\big),\quad\big(\tfrac15,\tfrac25\big),$$ and its area is $$\tfrac12\left|\det\begin{pmatrix}\tfrac1{12}&\tfrac1{12}\\-\tfrac1{20}&\tfrac3{20}\end{pmatrix}\right|=\tfrac12\cdot\tfrac{1}{60}=\tfrac1{120}.$$

Answer. $\dfrac{1/120}{1/12}=\dfrac1{10}$.

The picture shows the triangle of all breaks, with the six small “fair” triangles around its center (one for each ordering), and random breaks landing in them about one time in ten.

Affine invariance. An invertible affine map $\phi$ sends ellipses to ellipses, and multiplies all areas by the same number $|\det\phi|$. So the ratio $$\frac{\text{area of an ellipse }E}{\text{area of a triangle }T\text{ inscribed in }E}$$ does not change when we apply $\phi$ to both.

Lower bound. Given any ellipse $E$ through the vertices of our triangle $T$, choose $\phi$ that maps $E$ onto a circle of radius $\rho$. Then $\phi(T)$ is a triangle inscribed in that circle, and the largest such triangle is equilateral, with area $\tfrac{3\sqrt3}4\rho^2$. So $$\frac{\operatorname{area}E}{\operatorname{area}T}=\frac{\pi\rho^2}{\operatorname{area}\phi(T)}\ \ge\ \frac{\pi\rho^2}{\tfrac{3\sqrt3}4\rho^2}=\frac{4\pi}{3\sqrt3}.$$

Equality. Map an equilateral triangle onto $T$ by an affine map; its circumcircle goes to an ellipse through the vertices of $T$ with exactly this ratio.

The area of $T$ is $6$, so the smallest area is $\dfrac{4\pi}{3\sqrt3}\cdot6=\dfrac{8\pi}{\sqrt3}\approx14.51$.

Known result: the minimizer is the Steiner circumellipse, centered at the centroid. The animation slides an equilateral triangle and its circle smoothly into the $3$-$4$-$5$ triangle and its ellipse.

Periods. If $\tfrac1n=0.\overline{d_1\dots d_k}$, then $\tfrac1n=\dfrac{D}{10^k-1}$ with $D=d_1\dots d_k$, so $n\mid10^k-1$. Conversely, if $n\mid10^k-1$, then $\tfrac1n=\dfrac{(10^k-1)/n}{10^k-1}$ repeats with a block of length $k$. So the blocks that work are exactly the $k$ with $10^k\equiv1\pmod n$, and the smallest period is the order of $10$ modulo $n$.

Count. The smallest period is exactly $6$ when $n\mid10^6-1$ but $n\nmid10^1-1,10^2-1,10^3-1$. Since $9\mid99$, it is enough to exclude divisors of $99$ and of $999$.

• $999999=3^3\cdot7\cdot11\cdot13\cdot37$ has $4\cdot2\cdot2\cdot2\cdot2=64$ divisors.
• $999=3^3\cdot37$ has $8$ divisors and $99=3^2\cdot11$ has $6$. They share the $3$ divisors of $\gcd(999,99)=9$.

By inclusion and exclusion, $64-(8+6-3)=53$.

Fixed points of a power. Applying $\sigma$ moves each element around its cycle. An element in a cycle of length $d$ returns after $12$ steps exactly when $d\mid12$.

The cycle of one element. The cycle containing $1$ has length $d$ when $\sigma(1),\sigma^2(1),\dots,\sigma^{d-1}(1)$ are new elements and then $\sigma^{d}(1)=1$. Building $\sigma$ one value at a time, that has probability $$\frac{9}{10}\cdot\frac{8}{9}\cdots\frac{10-d+1}{10-d+2}\cdot\frac1{10-d+1}=\frac1{10}.$$ So the cycle length is uniform on $\{1,\dots,10\}$, and the same holds for every element.

Linearity. The divisors of $12$ up to $10$ are $1,2,3,4,6$, five of the ten possible lengths. Each element is fixed by $\sigma^{12}$ with probability $\tfrac5{10}$, so the expected number of fixed points is $10\cdot\tfrac5{10}=5$.

In general, the expected number of fixed points of $\sigma^k$ for a random permutation of $n$ elements is the number of divisors of $k$ that are at most $n$.

Work with general $n$; rows are $\rho_1,\dots,\rho_n$ with $\rho_i=(|i-1|,\dots,|i-n|)$.

Step 1. For $i=1,\dots,n-1$, replace $\rho_i$ by $\sigma_i=\rho_i-\rho_{i+1}$ (using the original rows; this does not change the determinant). The entries are $|i-j|-|i+1-j|$, which is $-1$ for $j\le i$ and $+1$ for $j>i$: $$\sigma_i=(\underbrace{-1,\dots,-1}_{i},+1,\dots,+1).$$

Step 2. For $i=2,\dots,n-1$, replace $\sigma_i$ by $\sigma_i-\sigma_{i-1}$ (again using the original $\sigma$’s). That leaves $-2$ in position $i$ and zeros elsewhere. The rows are now $$\sigma_1=(-1,1,\dots,1),\qquad -2e_2,\ \dots,\ -2e_{n-1},\qquad \rho_n=(n-1,n-2,\dots,1,0).$$

Step 3. Use the rows $-2e_i$ to clear columns $2,\dots,n-1$ from the first and last rows. What is left in columns $1$ and $n$ is $\begin{pmatrix}-1&1\\n-1&0\end{pmatrix}$, with determinant $-(n-1)$. So $$\det D=(-2)^{n-2}\cdot\big(-(n-1)\big)=(-1)^{n-1}(n-1)\,2^{n-2}.$$

For $n=10$: $-9\cdot256=-2304$.

Known result: Graham and Pollak (1971) showed that the distance matrix of any tree on $n$ vertices has this same determinant. Our matrix is the distance matrix of a path.

The tool. By Kirchhoff’s matrix-tree theorem (1847), a connected graph on $n$ vertices has $\tfrac1n\lambda_2\cdots\lambda_n$ spanning trees, where $\lambda_2,\dots,\lambda_n$ are the nonzero eigenvalues of the Laplacian $L=\Delta-A$ (degree matrix minus adjacency matrix).

Eigenvalues. Label corners by $x\in\{0,1\}^3$; two corners are joined when they differ in one coordinate. For each $s\in\{0,1\}^3$, the vector $v_s(x)=(-1)^{s\cdot x}$ satisfies $$(Av_s)(x)=\sum_{i=1}^3(-1)^{s\cdot(x+e_i)}=\Big(\sum_i(-1)^{s_i}\Big)v_s(x)=(3-2|s|)\,v_s(x),$$ where $|s|$ is the number of ones in $s$. These $8$ vectors are independent, so the Laplacian $3I-A$ has eigenvalues $2|s|$: $0$ once, $2$ three times, $4$ three times, $6$ once.

Count. $$\frac18\cdot2^3\cdot4^3\cdot6=\frac{3072}8=384.$$

The picture draws random spanning trees of the cube, chosen fairly with Wilson’s algorithm.

Rotating the picture does not change the distribution of the point, so we may assume the line is horizontal.

If the point is at height $y$, the chord has length $L(y)=2\sqrt{1-y^2}$. For a point uniform in the disk, the height $y$ has density proportional to the width of the disk at that height, which is $L(y)$ again: $$f(y)=\frac{L(y)}{\pi},\qquad -1\le y\le1.$$ So $$\mathbb E[L]=\int_{-1}^{1}L(y)\,\frac{L(y)}{\pi}\,dy=\frac4\pi\int_{-1}^{1}(1-y^2)\,dy=\frac4\pi\cdot\frac43=\frac{16}{3\pi}\approx1.698.$$

Why longer than you might guess. If you pick the height uniformly instead, the average chord is $\tfrac\pi2\approx1.571$. A random point is more likely to sit on a long chord than a short one, so long chords are over-represented. This “length-biased” sampling is the same effect that makes the gap between buses seem long when you arrive at a random time: you are more likely to land in a long gap.

Rotate. Let $\rho$ be the rotation by $60^\circ$ about $A$, turning away from $B$, and let $P'=\rho(P)$ and $C'=\rho(C)$. Then:

• $AP=AP'$ with a $60^\circ$ angle between them, so triangle $APP'$ is equilateral and $PA=PP'$;
• rotations keep lengths, so $PC=P'C'$.

Hence $$S(P)=BP+PP'+P'C'\ \ge\ BC',$$ since a broken path from $B$ to $C'$ is at least as long as the straight segment. The point $C'$ is fixed: it is the apex of the equilateral triangle built outward on $AC$.

Equality. It holds when $B,P,P',C'$ lie on one line in that order. This happens at the point $P$ that sees each side at $120^\circ$, which exists inside the triangle because all its angles are below $120^\circ$.

Compute. The angle $\angle BAC'=90^\circ+60^\circ=150^\circ$, $AB=4$ and $AC'=AC=3$. By the law of cosines, $$BC'^2=16+9-2\cdot4\cdot3\cos150^\circ=25+12\sqrt3.$$ So the minimum is $\sqrt{25+12\sqrt3}\approx6.766$.

Known result: this is the Fermat point (or Torricelli point), the classic answer to “shortest road network joining three towns.” The picture shows the rotation and the straightened path.

Dirichlet convolution. For functions on the positive integers, define $(f*g)(n)=\sum_{d\mid n}f(d)g(n/d)$. This product is commutative and associative: $(f*g*h)(n)$ is the sum of $f(a)g(b)h(c)$ over all $abc=n$, in any grouping.

Let $\mathbf 1$ be the constant function $1$ and $\mathrm{id}(n)=n$. Then

• $\tau=\mathbf 1*\mathbf 1$ (each divisor counted once);
• $\varphi*\mathbf 1=\mathrm{id}$ (Gauss: $\sum_{d\mid n}\varphi(d)=n$);
• $\mathrm{id}*\mathbf 1=\sigma$, the sum of divisors.

So $$\varphi*\tau=\varphi*\mathbf 1*\mathbf 1=\mathrm{id}*\mathbf 1=\sigma.$$

Evaluate. $720=2^4\cdot3^2\cdot5$ and $\sigma$ is multiplicative: $$\sigma(720)=(1+2+4+8+16)(1+3+9)(1+5)=31\cdot13\cdot6=2418.$$

The sum has $30$ terms; the convolution view turns it into one line.

Factor. Let $f(x)=x^2-x+2=(x-\alpha)(x-\beta)$, so $\alpha+\beta=1$ and $\alpha\beta=2$. The product is $$\prod_{k=1}^6(\omega^k-\alpha)(\omega^k-\beta)=\prod_{k=1}^6(\alpha-\omega^k)\cdot\prod_{k=1}^6(\beta-\omega^k)$$ (six sign changes in each). Since the $\omega^k$, $k=1..6$, are the roots of $\frac{z^7-1}{z-1}=z^6+\cdots+1$, $$\prod_{k=1}^6(z-\omega^k)=\frac{z^7-1}{z-1}.$$ So the product is $$\frac{(\alpha^7-1)(\beta^7-1)}{(\alpha-1)(\beta-1)}.$$

The denominator. $(\alpha-1)(\beta-1)=f(1)=2$.

The numerator. $(\alpha^7-1)(\beta^7-1)=(\alpha\beta)^7-(\alpha^7+\beta^7)+1$. With $s_n=\alpha^n+\beta^n$, each root satisfies $x^2=x-2$, so $s_n=s_{n-1}-2s_{n-2}$, with $s_0=2$, $s_1=1$: $$s_2=-3,\ s_3=-5,\ s_4=1,\ s_5=11,\ s_6=9,\ s_7=-13.$$ So the numerator is $128+13+1=142$, and the product is $\dfrac{142}{2}=71$.

Idea used: a product of $f$ over all roots of one polynomial is a product of the other polynomial over the roots of $f$ (a resultant). It turns a product over six complex numbers into two values.

A fair casino. Before each flip a new gambler arrives with one dollar. Gambler $j$ (who arrives before flip $j$) bets everything on flip $j$ being H, at fair odds (double or nothing). If he wins, he bets his two dollars on flip $j+1$ being T, and so on through the pattern H, T, H, T, H. He leaves when he loses, or when he has completed the pattern.

Let $N$ be the flip on which HTHTH first appears, and stop everything then.

Paid in. Exactly $N$ gamblers have arrived, so the casino has received $N$ dollars.

Held at the end. A gambler still holds money only if every flip since he arrived matched the start of the pattern. So the last $\ell$ flips must equal the first $\ell$ letters of HTHTH, while the last $\ell$ flips are also the last $\ell$ letters of HTHTH. The lengths where the beginning equals the ending are $$\ell=5\ (\mathrm{HTHTH}),\qquad \ell=3\ (\mathrm{HTH}),\qquad \ell=1\ (\mathrm{H}),$$ holding $2^5$, $2^3$ and $2^1$ dollars. The total is always $32+8+2=42$ dollars.

Fairness. Every bet is fair, so the casino’s net gain $N-42$ has expected value $0$. (The optional stopping theorem applies: $N$ has finite mean, since each block of five flips is HTHTH with probability $\tfrac1{32}$, and the net gain changes by a bounded amount per flip.) So $\mathbb E[N]=42$.

Known result: this “casino” or martingale argument is due to S.-Y. R. Li (1980); J. H. Conway found the same overlap rule earlier. Compare HHHTT, which has no self-overlap: its expected wait is just $2^5=32$.

Check by states. Solving the five linear equations for “how much of the pattern have I matched” also gives $42$.

Let $r_k\in\{0,\dots,p-1\}$ be the remainder of $k^3$ modulo $p$. Then $$\sum_{k=1}^{p-1}\left\lfloor\frac{k^3}{p}\right\rfloor=\frac1p\Big(\sum_{k=1}^{p-1}k^3-\sum_{k=1}^{p-1}r_k\Big).$$

Cubing permutes the remainders. Here $p-1=2026=2\cdot1013$ is not divisible by $3$, so there is a $u$ with $3u\equiv1\pmod{p-1}$. By Fermat’s little theorem, $(k^3)^u=k^{3u}\equiv k\pmod p$ for $p\nmid k$. So cubing has an inverse on the nonzero remainders, and $r_1,\dots,r_{p-1}$ are $1,\dots,p-1$ in some order. Their sum is $\tfrac{p(p-1)}2$.

Finish. $\sum_{k=1}^{p-1}k^3=\left(\tfrac{p(p-1)}2\right)^2$, so the sum is $$\frac{p(p-1)^2}{4}-\frac{p-1}{2}=\frac{(p-1)\big(p(p-1)-2\big)}4=\frac{(p-1)(p-2)(p+1)}4.$$ With $p=2027$: $\dfrac{2026\cdot2025\cdot2028}{4}=2080043550$.

If $3\mid p-1$, cubing is three-to-one on the nonzero remainders, and the remainders are no longer spread evenly; the neat formula breaks down.

Logs. Let $E_i=-\ln U_i$. Then $\Pr(E_i>t)=\Pr(U_i<e^{-t})=e^{-t}$, so the $E_i$ are independent exponential variables with mean $1$. The product is below $\tfrac12$ exactly when $E_1+\dots+E_n>\ln2$. Write $t=\ln2$ and $S_n=E_1+\dots+E_n$.

Poisson process. Points placed at $S_1<S_2<\cdots$ on the line form a Poisson process of rate $1$: independent exponential gaps. Then $N-1$ is the number of points in $[0,t]$, which has a Poisson distribution with mean $t$. So $$\mathbb E[N]=1+t=1+\ln2\approx1.693.$$

Without the Poisson process. The density of $S_n$ is $\frac{s^{n-1}e^{-s}}{(n-1)!}$, and integrating by parts gives $\Pr(S_n\le t)=\sum_{k\ge n}e^{-t}\frac{t^k}{k!}$. Then $$\mathbb E[N]=\sum_{n\ge0}\Pr(N>n)=\sum_{n\ge0}\Pr(S_n\le t)=\sum_{k\ge0}(k+1)e^{-t}\frac{t^k}{k!}=t+1.$$

The same reasoning with the threshold $e^{-t}$ in place of $\tfrac12$ gives $1+t$. A cousin: if you add uniform numbers until the sum passes $1$, the expected count is $e$.

Counting the other triples. In a triple that is not cyclic, one player beat the other two, and that player is unique. A player with $w$ wins is the winner of exactly $\binom w2$ such triples (choose two of the players he beat). So $$\#\text{cyclic}=\binom{10}3-\sum_{i=1}^{10}\binom{w_i}2=120-\sum_i\binom{w_i}2,$$ where $w_i$ are the win totals, with $\sum w_i=\binom{10}2=45$.

Make the sum small. $\binom w2$ is convex in $w$: if $w_i\ge w_j+2$, moving one unit from $w_i$ to $w_j$ lowers the sum by $w_i-1-w_j>0$. So among integer lists with sum $45$, the minimum is at the most even one: five $4$’s and five $5$’s, giving $5\cdot6+5\cdot10=80$. Hence at most $120-80=40$ cyclic triples.

A tournament that reaches it. Seat players $0,\dots,8$ around a circle, and let each beat the next four going clockwise. Each of them has $4$ wins. Add player $9$, who beats $0,1,2,3$ and loses to $4,\dots,8$. Now $0,1,2,3$ and $9$ have $4$ wins and $4,\dots,8$ have $5$. By the formula, this tournament has exactly $40$ cyclic triples.

Known result: Kendall and Babington Smith (1940) found this maximum for every $n$: $\frac{n^3-n}{24}$ for odd $n$ and $\frac{n^3-4n}{24}$ for even $n$.

Riemann sum. $\dfrac{n\bmod k}{k}=\left\{\dfrac nk\right\}=g\!\left(\dfrac kn\right)$ with $g(x)=\{1/x\}$, so the expression is $\frac1n\sum_{k=1}^ng(k/n)$. The function $g$ takes values in $[0,1)$. On $[\delta,1]$ it has finitely many jumps, so it is Riemann integrable there; the terms with $k<\delta n$ contribute at most $\delta+\tfrac1n$, and $\int_0^\delta g\le\delta$. Letting $\delta\to0$, the limit is $$\int_0^1\{1/x\}\,dx=\int_1^\infty\frac{\{u\}}{u^2}\,du.$$

The integral. On $[m,m+1)$, $\{u\}=u-m$, and $$\int_m^{m+1}\frac{u-m}{u^2}\,du=\ln\frac{m+1}{m}-m\Big(\frac1m-\frac1{m+1}\Big)=\ln\frac{m+1}m-\frac1{m+1}.$$ Summing $m=1,\dots,M$: $$\ln(M+1)-\Big(\frac12+\frac13+\cdots+\frac1{M+1}\Big)=1-\big(H_{M+1}-\ln(M+1)\big)\ \longrightarrow\ 1-\gamma,$$ where $H_n-\ln n\to\gamma$ is the definition of the Euler–Mascheroni constant.

So the limit is $1-\gamma\approx0.4228$: on average the remainder is a bit less than half of the divisor.

Lengths $1/m$ always work. Let $h=\tfrac1m$ and $g(x)=f(x+h)-f(x)$ on $[0,1-h]$. The sum telescopes: $$g(0)+g(h)+g(2h)+\dots+g((m-1)h)=f(1)-f(0)=0.$$ So some term is $\ge0$ and some term is $\le0$. By the intermediate value theorem, $g$ has a zero between them: a level stretch of length $\tfrac1m$.

Other lengths can fail. Let $0<h<1$ with $1/h$ not an integer, and set $$f(x)=\sin^2\!\Big(\frac{\pi x}h\Big)-x\,\sin^2\!\Big(\frac\pi h\Big).$$ Then $f(0)=0$ and $f(1)=\sin^2(\pi/h)-\sin^2(\pi/h)=0$. The first part has period $h$, so $$f(x+h)-f(x)=-h\,\sin^2\!\Big(\frac\pi h\Big),$$ which is never $0$, because $\pi/h$ is not a multiple of $\pi$. For $h=\tfrac25$ and $h=\tfrac3{10}$, $1/h$ is $2.5$ and $3.\overline3$, so these trails have no level stretch of that length.

So the guaranteed lengths are exactly $\tfrac12$, $\tfrac13$ and $\tfrac14$.

Known result: Paul Lévy’s universal chord theorem (1934): the guaranteed lengths are exactly $\tfrac1m$. The picture lets you slide a chord of fixed length along a trail and watch for a level spot.

Factor. Let $L_{ik}=\binom ik$ for $0\le i,k\le5$, a lower-triangular matrix with ones on the diagonal. Then $$(LL^{T})_{ij}=\sum_k\binom ik\binom jk=\sum_k\binom ik\binom j{j-k}=\binom{i+j}{j}$$ by Vandermonde’s identity (choose $j$ people from $i$ women and $j$ men, sorted by how many women). So $P=LL^{T}$.

Invert $L$. Let $M_{ik}=(-1)^{i-k}\binom ik$. Then $$(LM)_{ik}=\sum_j\binom ij\binom jk(-1)^{j-k}=\binom ik\sum_{j}\binom{i-k}{j-k}(-1)^{j-k}=\binom ik\,(1-1)^{i-k},$$ which is $1$ if $i=k$ and $0$ otherwise. So $L^{-1}=M$.

Trace. $P^{-1}=(L^{T})^{-1}L^{-1}=M^{T}M$, and $\operatorname{tr}(M^{T}M)$ is the sum of the squares of the entries of $M$: $$\operatorname{tr}P^{-1}=\sum_{i=0}^{5}\sum_{k=0}^{i}\binom ik^2=\sum_{i=0}^5\binom{2i}{i}=1+2+6+20+70+252=351,$$ using $\sum_k\binom ik^2=\binom{2i}i$ (Vandermonde again).

Since $\det P=(\det L)^2=1$, the inverse has integer entries; the trace adds up central binomial coefficients.

Reduce to hemispheres. With probability $1$ the points are in general position. The center lies outside the hull of $P_1,\dots,P_n$ exactly when some plane through the center has all the points strictly on one side, that is, when all the points lie in an open hemisphere. Let $p_n$ be that probability. Then $\Pr(N>n)=p_n$, with $p_0=1$, and $$\mathbb E[N]=\sum_{n\ge0}\Pr(N>n)=1+\sum_{n\ge1}p_n.$$

The sign trick. Replacing any $P_i$ by $-P_i$ does not change the joint distribution. So $p_n$ is the expected fraction of the $2^n$ sign choices $(\varepsilon_1P_1,\dots,\varepsilon_nP_n)$ that lie in an open hemisphere.

A sign choice lies in the open hemisphere centered at $v$ exactly when $\varepsilon_i\,(v\cdot P_i)>0$ for all $i$. The great circles $v\cdot P_i=0$ cut the sphere into regions, and on each region the signs of $v\cdot P_i$ are constant. So the good sign choices match the regions one to one.

Count regions. One great circle makes $2$ regions. The $n$-th circle meets each earlier one in $2$ points, so it is cut into $2(n-1)$ arcs, and each arc splits a region in two. So $R_n=2+2(1+2+\dots+(n-1))=n^2-n+2$, and $$p_n=\frac{n^2-n+2}{2^n}.$$ (This gives $p_1=p_2=p_3=1$ and $p_4=\tfrac78$: four points surround the center with probability $\tfrac18$.)

Sum. Using $\sum_{n\ge0}\frac{n(n-1)}{2^n}=4$ and $\sum_{n\ge0}\frac2{2^n}=4$, $$\mathbb E[N]=1+\Big(\sum_{n\ge0}\frac{n^2-n+2}{2^n}-2\Big)=1+(8-2)=7.$$

On a circle the same steps give $p_n=\frac{2n}{2^n}$ and $\mathbb E[N]=5$, which the animation simulates.

Known results: the $\tfrac18$ for four points is Putnam 1992 A6, the subject of 3Blue1Brown’s video The hardest problem on the hardest test. The general formula for $p_n$ in any dimension is due to J. G. Wendel (1962).

The correspondence. The Robinson–Schensted correspondence is a bijection between permutations of $\{1,\dots,n\}$ and pairs $(P,Q)$ of standard Young tableaux of the same shape $\lambda$ with $n$ cells. Schensted’s theorem (1961) says the length of the first row of $\lambda$ is the longest increasing subsequence, and the number of rows is the longest decreasing subsequence.

The shape. We need at most $3$ cells in each row and at most $4$ rows, with $12$ cells in all. Only the full $4\times3$ rectangle $\lambda=(3,3,3,3)$ fits. So the answer is $f_\lambda^2$, where $f_\lambda$ is the number of standard Young tableaux of that shape.

Hook lengths. By the Frame–Robinson–Thrall hook length formula, $f_\lambda=\dfrac{12!}{\prod\text{hooks}}$. In the $4\times3$ rectangle the hooks, row by row, are $$6,5,4;\quad 5,4,3;\quad 4,3,2;\quad 3,2,1,$$ with product $120\cdot60\cdot24\cdot6=1036800$. So $f_\lambda=\dfrac{479001600}{1036800}=462$, and the answer is $$462^2=213444.$$

Edge cases. With $13$ numbers there would be none at all (Erdős–Szekeres). A smaller case to test the method: permutations of $1..6$ with no increasing subsequence of length $4$ and no decreasing one of length $3$ correspond to the $2\times3$ rectangle, $f=5$, so $25$.