A Long-Form Mathematics Textbook

The board has $64 - 1 = 63$ squares. Each domino covers exactly 2 squares, so a complete tiling would require $63/2$ dominoes, which is not an integer. Hence no tiling exists.

Color the board like a standard chessboard, alternating black and white. The top-left and bottom-right corners share the same color (say, both are white). The original board has 32 black and 32 white squares; removing both corners leaves 32 black and 30 white squares. Each domino covers exactly one black square and one white square, so any tiling covers equal numbers of each color. Since $32 \neq 30$, no tiling exists.

Partition the set into four pairs: $\{1,8\},\{2,7\},\{3,6\},\{4,5\}$, each summing to 9. Since 5 numbers are chosen from 4 pairs, by the pigeonhole principle at least two come from the same pair, and those two sum to 9.

Every positive integer can be written uniquely as $2^k \cdot m$ where $m$ is odd. The odd parts of integers in $\{1,\ldots,200\}$ all lie in $\{1,3,5,\ldots,199\}$, which has exactly 100 elements. By the pigeonhole principle, among any 101 chosen integers, two share the same odd part: $a = 2^j \cdot m$ and $b = 2^k \cdot m$ with $j < k$. Then $a \mid b$.

The degree of any vertex lies in $\{0, 1, \ldots, n-1\}$, which has $n$ values. However, 0 and $n-1$ cannot both occur: if some vertex has degree $n-1$ it is adjacent to every other vertex, so no vertex can have degree 0. Thus the $n$ vertices take values in a set of at most $n-1$ possible degrees, and by the pigeonhole principle two vertices share the same degree.

Pick any two of the 5 points. There is a great circle passing through both of them, which divides the sphere into two closed hemispheres (each including its boundary great circle). The remaining 3 points are each in at least one of the two hemispheres. By the pigeonhole principle, one hemisphere contains at least $\lceil 3/2 \rceil = 2$ of those 3 points. That same hemisphere also contains the two points on the great circle, for a total of at least 4.

Partition $\{1, \ldots, 60\}$ into 30 consecutive pairs: $\{1,2\}, \{3,4\}, \ldots, \{59,60\}$. Any two consecutive integers $n$ and $n+1$ are relatively prime, since any common divisor must divide their difference 1. By the pigeonhole principle, choosing 31 numbers from these 30 pairs forces at least two chosen numbers to fall in the same pair, and those two are relatively prime.

Every odd integer $m$ can be written uniquely as $m = 3^k q$ where $k \geq 0$ and $q$ is an odd integer not divisible by 3. Call $q$ the 3-free part of $m$. For each such $q$, define the chain $C_q = \{q,\, 3q,\, 9q,\, \ldots\} \cap \{1,\ldots,3n\}$. These chains partition all odd integers in $\{1,\ldots,3n\}$, and within each chain every element divides the next.

The chains are indexed by the odd integers in $\{1,\ldots,3n\}$ that are not divisible by 3. In $\{1,\ldots,3n\}$ there are exactly $2n$ integers not divisible by 3, and exactly half of them are odd, giving exactly $n$ chains. By the pigeonhole principle, choosing $n+1$ odd integers from these $n$ chains forces two of them into the same chain, and the smaller of the two divides the larger.

Proof 1 (rearrangement). Consider the $p-1$ integers $a, 2a, \ldots, (p-1)a$. They are all distinct modulo $p$ and nonzero modulo $p$: if $ia \equiv ja \pmod{p}$ then $p \mid (j-i)a$, and since $p \nmid a$ we get $p \mid j-i$, impossible for $1 \leq i < j \leq p-1$. So $\{a, 2a, \ldots, (p-1)a\}$ is a permutation of $\{1, 2, \ldots, p-1\}$ modulo $p$. Multiplying all elements: $a^{p-1}(p-1)! \equiv (p-1)! \pmod{p}$. Since $\gcd((p-1)!, p) = 1$, we cancel to obtain $a^{p-1} \equiv 1 \pmod{p}$.

Proof 2 (binomial theorem). We first show $\binom{p}{k} \equiv 0 \pmod{p}$ for $0 < k < p$. Indeed, $\binom{p}{k} = \frac{p!}{k!(p-k)!}$ is an integer, $p$ divides the numerator, and $k!$ and $(p-k)!$ have no factor of $p$ since $k, p-k < p$. We now prove $a^p \equiv a \pmod{p}$ for all $a \geq 1$ by induction. The base case $a = 1$ is clear. Assuming $a^p \equiv a$, the binomial theorem gives $(a+1)^p = \sum_{k=0}^{p} \binom{p}{k} a^k$, and every middle term vanishes mod $p$, leaving $(a+1)^p \equiv a^p + 1 \equiv a + 1 \pmod{p}$. So $p \mid a(a^{p-1} - 1)$, and since $p \nmid a$, we get $a^{p-1} \equiv 1 \pmod{p}$.

Any integer ending in 5 can be written as $n = 10k + 5$ for some integer $k$. Then $n^2 = (10k+5)^2 = 100k^2 + 100k + 25 = 100k(k+1) + 25$. Since $100k(k+1)$ is divisible by 100, the last two digits of $n^2$ are exactly 25.

Any integer is congruent to $0$, $1$, or $2$ modulo 3, so its square is congruent to $0$ or $1$ modulo 3. Suppose for contradiction that $3 \nmid a$ and $3 \nmid b$. Then $a^2 \equiv 1$ and $b^2 \equiv 1 \pmod{3}$, giving $c^2 \equiv 2 \pmod{3}$. But no square is congruent to 2 modulo 3, a contradiction. Therefore 3 divides $a$ or $b$.

Let $n = 2k+1$ be any odd integer. Then $(k+1)^2 - k^2 = 2k + 1 = n$.

Consider the $n$ consecutive integers $(n+1)! + 2,\ (n+1)! + 3,\ \ldots,\ (n+1)! + (n+1)$. For each $k$ with $2 \leq k \leq n+1$, we have $k \mid (n+1)!$ and $k \mid k$, so $k \mid (n+1)! + k$. Since $(n+1)! + k > k$, it is composite.

Every integer is congruent to $0, 1, 2, 3, 4,$ or $5$ modulo 6. A prime $p > 3$ cannot be divisible by 2 (ruling out $0, 2, 4$) or by 3 (ruling out $0, 3$), so $p \equiv 1$ or $5 \pmod{6}$. Both cases mean $p$ is within 1 of a multiple of 6.

Let $r_1, r_2, \ldots, r_{\varphi(n)}$ be the integers in $\{1, \ldots, n\}$ coprime to $n$. Since $\gcd(a, n) = 1$, the products $ar_1, ar_2, \ldots, ar_{\varphi(n)}$ are also coprime to $n$ and distinct modulo $n$, so they are a permutation of $r_1, \ldots, r_{\varphi(n)}$ modulo $n$. Multiplying all terms: $a^{\varphi(n)} \prod r_i \equiv \prod r_i \pmod{n}$. Since each $r_i$ is coprime to $n$, so is their product, and we can cancel to get $a^{\varphi(n)} \equiv 1 \pmod{n}$.

The number of non-empty subsets of $A$ is $2^{10} - 1 = 1023$. The sum of any non-empty subset of $A$ is at most $91 + 92 + \cdots + 100 = 955$ (the largest possible 10-element subset of $\{1,\ldots,100\}$), and at least 1. So all subset sums take values in $\{1, \ldots, 955\}$, giving at most 955 distinct values. Since $1023 > 955$, by the pigeonhole principle two distinct non-empty subsets must have the same sum.

By induction on $n$. The base case $n = 1$ is immediate: removing any one square from a $2 \times 2$ board leaves exactly one L-tromino. For the inductive step, divide the $2^n \times 2^n$ board into four quadrants of size $2^{n-1} \times 2^{n-1}$. The removed square lies in exactly one quadrant. Place one L-tromino at the center of the board, covering one corner square from each of the other three quadrants. Each quadrant now has exactly one square missing, so by the induction hypothesis each can be tiled by L-trominoes.

Since $b - a > 0$, by the Archimedean property there exists $n \in \mathbb{N}$ with $n > \frac{1}{b-a}$, i.e. $\frac{1}{n} < b - a$. Let $m = \lfloor na \rfloor + 1$, so $m - 1 \leq na < m$, giving $a < \frac{m}{n}$. Also $m \leq na + 1 < na + n(b-a) = nb$, so $\frac{m}{n} < b$. Thus $q = \frac{m}{n} \in \mathbb{Q}$ satisfies $a < q < b$.

Exactly $nm - 1$ breaks are needed. Each break takes one piece and splits it into two, increasing the number of pieces by exactly 1. We start with 1 piece and need $nm$ pieces, so we need exactly $nm - 1$ breaks regardless of the order in which we break.

Alternative proof by strong induction. Let $P(k)$ be the statement that any rectangular piece of $k$ squares requires exactly $k - 1$ breaks. The base case $k = 1$ holds since no break is needed. For the inductive step, take a piece of $k > 1$ squares and make one break, splitting it into two pieces of $a$ and $b$ squares with $a + b = k$ and $a, b \geq 1$. By strong induction, these require $a - 1$ and $b - 1$ further breaks respectively. The total is $1 + (a-1) + (b-1) = a + b - 1 = k - 1$.

The step $P(1) \Rightarrow P(2)$ fails: the two subgroups of size 1 are $\{p_1\}$ and $\{p_2\}$, which are disjoint, so there is no shared member to force the names to agree.

Existence by strong induction. The base case $n = 1 = 2^0$ holds. For $n > 1$, let $2^k$ be the largest power of 2 with $2^k \leq n$. Then $n - 2^k < 2^k$ (otherwise $2^{k+1} \leq n$), so by induction $n - 2^k$ is a sum of distinct powers of 2, all strictly less than $2^k$. Prepending $2^k$ gives a representation of $n$ using distinct powers.

Uniqueness. Suppose $n = 2^{a_1} + \cdots + 2^{a_r} = 2^{b_1} + \cdots + 2^{b_s}$ with $a_1 > \cdots > a_r$ and $b_1 > \cdots > b_s$. Then $2^{a_1} \leq n < 2^{a_1+1}$ and similarly $2^{b_1} \leq n < 2^{b_1+1}$, so $a_1 = b_1$. Subtracting $2^{a_1}$ from both sides and repeating gives $r = s$ and $a_i = b_i$ for all $i$.

By induction on $n$. For the base case $n = 1$, a graph on 2 vertices has at most 1 edge, so the hypothesis ($n^2 + 1 = 2$ edges) cannot be satisfied and there is nothing to prove.

For the inductive step, assume the result holds for $n$. Let $G$ have $2(n+1)$ vertices and $(n+1)^2 + 1$ edges, and pick any edge $uv$. Let $G'$ be the subgraph induced by the remaining $2n$ vertices.

If $G'$ has at least $n^2 + 1$ edges, the induction hypothesis gives a triangle in $G'$, and we are done.

Otherwise $G'$ has at most $n^2$ edges. The remaining $(n+1)^2 + 1 - n^2 = 2n + 2$ edges all involve $u$ or $v$; one of them is $uv$ itself, so at least $2n + 1$ edges go from $\{u, v\}$ to the $2n$ other vertices. By the pigeonhole principle, some vertex $w$ among those $2n$ is adjacent to both $u$ and $v$, and $u, v, w$ form a triangle.

By induction on $n$. The base case $n = 0$ holds since $F_0 = 3 = F_1 - 2$. For the inductive step, assume $F_0 \cdots F_{n-1} = F_n - 2$. Multiplying both sides by $F_n$ gives $F_0 \cdots F_{n-1} \cdot F_n = (F_n - 2) \cdot F_n$. Writing $F_n = 2^{2^n} + 1$, the right side factors as a difference of squares: $(2^{2^n} - 1)(2^{2^n} + 1) = 2^{2^{n+1}} - 1 = F_{n+1} - 2$.

By induction on $n$. The base case $n = 0$ gives $1 \leq 1$, which holds. For the inductive step, assume $1 + nx \leq (1+x)^n$. Since $x \geq -1$ we have $1 + x \geq 0$, so multiplying both sides by $1 + x$ preserves the inequality: $(1 + nx)(1 + x) \leq (1 + x)^{n+1}$. Expanding the left side gives $(1 + nx)(1 + x) = 1 + (n+1)x + nx^2 \geq 1 + (n+1)x$, since $nx^2 \geq 0$. Chaining the two inequalities gives $1 + (n+1)x \leq (1+x)^{n+1}$.

By induction on $n$. The base case $n = 1$ holds with $a_1 = 1$, since $1^2 = 1^2$. For the inductive step, suppose $a_1, \ldots, a_n$ are distinct positive integers with $a_1^2 + \cdots + a_n^2 = k^2$. Set $b_i = 3a_i$ for each $i$ and $b_{n+1} = 4k$. Then $b_1^2 + \cdots + b_n^2 + b_{n+1}^2 = 9k^2 + 16k^2 = (5k)^2$. The values $b_1, \ldots, b_n$ are distinct since the $a_i$ are. If $b_{n+1} = 3a_j$ for some $j$, then $a_j = 4k/3$, giving $a_j^2 = 16k^2/9 > k^2$, which contradicts $a_j^2 \leq a_1^2 + \cdots + a_n^2 = k^2$. So $b_{n+1}$ is distinct from every $b_i$.

By induction on $n$. The base case $n = 1$ holds: a single vertex has no edges, and $1 - 1 = 0$. For the inductive step, let $T$ be a tree with $n \geq 2$ vertices. Every tree with at least two vertices has a leaf, i.e. a vertex $v$ of degree 1. Remove $v$ and its unique incident edge to obtain a graph $T'$ on $n - 1$ vertices. Since $T$ is connected and acyclic, $T'$ is also connected and acyclic, so $T'$ is a tree. By the induction hypothesis, $T'$ has $n - 2$ edges. Restoring $v$ and its edge gives $T$ exactly $(n - 2) + 1 = n - 1$ edges.

Suppose for contradiction that $\sqrt{p} = a/b$ with $a, b \in \mathbb{Z}$ and $\gcd(a, b) = 1$. Then $pb^2 = a^2$, so $b^2 \mid a^2$. Since $\gcd(a, b) = 1$ we have $\gcd(a^2, b^2) = 1$, forcing $b^2 = 1$, i.e. $b = \pm 1$. Then $p = a^2$, but a prime cannot be a perfect square, a contradiction.

Suppose for contradiction that the set $S$ of integers $\geq 2$ that are not products of primes is nonempty. By the well-ordering principle, $S$ has a least element $n$. Then $n$ is not prime (otherwise $n$ itself is a product of one prime, contradicting $n \in S$), so $n = ab$ for some integers $2 \leq a, b < n$. Since $a$ and $b$ are less than the minimal counterexample, neither belongs to $S$, so both are products of primes. But then $n = ab$ is also a product of primes, a contradiction.

Proof 1 (parity). Rewrite the equation as $x(x + 1) = a^2$. The left side is the product of two consecutive integers, so it is always even. But $a$ is odd, so $a^2$ is odd. An even number cannot equal an odd number, a contradiction.

Proof 2 (discriminant). For $x^2 + x - a^2 = 0$ to have an integer solution, its discriminant $\Delta = 1 + 4a^2$ must be a perfect square, say $k^2$. Then $k^2 - 4a^2 = 1$, i.e., $(k - 2a)(k + 2a) = 1$. The only integer factorizations of 1 are $1 \cdot 1$ and $(-1) \cdot (-1)$, both of which give $k - 2a = k + 2a$, forcing $a = 0$. Since 0 is even, no odd integer $a$ satisfies this, so no integer solution exists.

Let $\varepsilon > 0$. By the Archimedean property, there exists $N \in \mathbb{N}$ with $N > 1/\varepsilon$. Then for all $n > N$, we have $\left|\frac{1}{n} - 0\right| = \frac{1}{n} < \frac{1}{N} < \varepsilon$.

Let $\varepsilon > 0$. By the Archimedean property, there exists $N \in \mathbb{N}$ with $N > 1/\sqrt{\varepsilon}$. Then for all $n > N$, we have $\left|\left(2 - \frac{1}{n^2}\right) - 2\right| = \frac{1}{n^2} < \frac{1}{N^2} < \varepsilon$.

Suppose for contradiction that both $a$ and $b$ are odd. Any odd integer squares to $1$ modulo $4$, so $a^2 + b^2 \equiv 1 + 1 = 2 \pmod{4}$. But any integer squares to either $0$ or $1$ modulo $4$, so $c^2 \not\equiv 2 \pmod{4}$, a contradiction.

We prove the contrapositive: if $m$ and $n$ are both odd, then $4 \nmid m^2 + n^2$. Any odd integer squares to $1$ modulo $4$, so $m^2 + n^2 \equiv 1 + 1 = 2 \pmod{4}$, hence $4 \nmid m^2 + n^2$.

Proof 1 (contradiction). Suppose $n^2 + n + 1 = k^2$ for some integer $k$. Then $n(n + 1) = k^2 - 1 = (k-1)(k+1)$. Since $k^2 > n^2$ we have $k \geq n + 1$, so $k - 1 \geq n$ and $k + 1 \geq n + 2$. Thus $(k-1)(k+1) \geq n(n+2) > n(n+1)$, a contradiction.

Proof 2 (squeeze). For $n \geq 1$, we have $n^2 < n^2 + n + 1$ and $n^2 + n + 1 < n^2 + 2n + 1 = (n+1)^2$. So $n^2 + n + 1$ lies strictly between two consecutive perfect squares $n^2$ and $(n+1)^2$, and therefore cannot itself be a perfect square.

$(\Rightarrow)$ Suppose $f$ has an inverse $g : B \to A$, so $g \circ f = \mathrm{id}_A$ and $f \circ g = \mathrm{id}_B$. For injectivity, if $f(x) = f(y)$ then $x = g(f(x)) = g(f(y)) = y$. For surjectivity, given $y \in B$, set $x = g(y)$; then $f(x) = f(g(y)) = y$.

$(\Leftarrow)$ Suppose $f$ is a bijection. For each $y \in B$, surjectivity gives some $x$ with $f(x) = y$, and injectivity makes it unique; define $g(y) = x$. Then $g(f(x)) = x$ and $f(g(y)) = y$ for all $x, y$, so $g$ is an inverse of $f$.

Call index $n$ a peak if $a_n \geq a_k$ for all $k > n$. There are two cases.

If there are infinitely many peaks $n_1 < n_2 < \cdots$, then for each $i$, since $n_i$ is a peak and $n_{i+1} > n_i$, we have $a_{n_i} \geq a_{n_{i+1}}$. So $(a_{n_i})$ is non-increasing.

If there are finitely many peaks, let $N$ be the last one. Define $n_1 = N + 1$; since $n_1$ is not a peak, there exists $n_2 > n_1$ with $a_{n_2} > a_{n_1}$. Since $n_2$ is not a peak either, there exists $n_3 > n_2$ with $a_{n_3} > a_{n_2}$. Continuing inductively gives a strictly increasing subsequence.

The answer is 1 second, achieved by placing one ant at an end facing inward. It is also the worst case for any $n$: when two ants collide and reverse, the result is indistinguishable from them passing through each other (since ants are identical). So each ant effectively walks at constant speed in its original direction, and any ant at position $x \in [0,1]$ falls off after at most $\max(x, 1-x) \leq 1$ second.