The Art of Problem Solving

Combined rate: $\frac{1}{5} + \frac{1}{4} = \frac{9}{20}$ pools per hour, so $t = \frac{20}{9} \approx 2.22$ hours.

Minute hand: $6°$/min, hour hand: $0.5°$/min. At 4:00, the hour hand is at $120°$. The hands coincide when $6t = 120 + 0.5t$, i.e. $5.5t = 120$, so $t = \frac{240}{11} \approx 21.82$ minutes.

Unit digits of powers of 7 cycle with period 4: $7, 9, 3, 1, \ldots$ Since $42 \equiv 2 \pmod{4}$, the unit digit of $7^{42}$ is $9$.

Unit digits of powers of 2 cycle with period 4: $2, 4, 8, 6, \ldots$ Since $7 \equiv 3 \pmod{4}$, the unit digit of $42^7$ is $8$.

Therefore the unit digit of $7^{42} + 42^7$ is $9 + 8 = 17$, i.e. $\mathbf{7}$.

One person paints $\frac{5}{4 \times 3} = \frac{5}{12}$ houses per day. Two people paint $\frac{5}{6}$ houses per day, so 6 houses takes $\frac{6}{5/6} = \frac{36}{5} = 7.2$ days.

Since $P\!\left(\frac{p}{q}\right) = 0$, multiplying by $q^n$ gives $$a_n p^n + a_{n-1} p^{n-1} q + \cdots + a_1 p q^{n-1} + a_0 q^n = 0.$$

Isolating $a_0 q^n$: $$a_0 q^n = -p \left( a_n p^{n-1} + a_{n-1} p^{n-2} q + \cdots + a_1 q^{n-1} \right),$$ so $p \mid a_0 q^n$. Since $\gcd(p, q) = 1$, we have $\gcd(p, q^n) = 1$, hence $p \mid a_0$.

Isolating $a_n p^n$: $$a_n p^n = -q \left( a_{n-1} p^{n-1} + a_{n-2} p^{n-2} q + \cdots + a_0 q^{n-1} \right),$$ so $q \mid a_n p^n$. Since $\gcd(q, p^n) = 1$, we conclude $q \mid a_n$.

By the rational root theorem, any rational root $\frac{p}{q}$ (in lowest terms) satisfies $p \mid 1$ and $q \mid 2$, so the candidates are $\pm 1, \pm \frac{1}{2}$.

Testing $x = 1$: $2 - 5 + 4 - 1 = 0$, so $1$ is a root. Polynomial division yields $$2x^3 - 5x^2 + 4x - 1 = (x - 1)(2x^2 - 3x + 1) = (x - 1)^2 (2x - 1).$$

The roots are $x = 1$ (double) and $x = \frac{1}{2}$.

Since $P$ has roots $r_1, \ldots, r_n$ and leading coefficient $a_n$, we have $$P(x) = a_n \prod_{i=1}^{n} (x - r_i).$$

Expanding the product, the coefficient of $x^{n-k}$ is obtained by choosing $x$ from $n - k$ of the factors and $-r_i$ from the remaining $k$ factors, summed over all such choices: $$\prod_{i=1}^{n} (x - r_i) = \sum_{k=0}^{n} \left( \sum_{1 \leq i_1 < \cdots < i_k \leq n} \prod_{j=1}^{k} (-r_{i_j}) \right) x^{n-k} = \sum_{k=0}^{n} (-1)^k e_k \, x^{n-k},$$ with the convention $e_0 = 1$.

Therefore $$P(x) = \sum_{k=0}^{n} (-1)^k a_n e_k \, x^{n-k}.$$ Identifying with $P(x) = \sum_{k=0}^{n} a_{n-k} x^{n-k}$ gives $a_{n-k} = (-1)^k a_n e_k$, hence $$e_k = (-1)^k \frac{a_{n-k}}{a_n}.$$

Let $r$ be the fourth root. Since the coefficient of $x^3$ is $0$, Vieta's formulas give $e_1 = 0$: $$-1 + 2 + 3 + r = 0 \implies r = -4.$$

The polynomial factors as $$(x+1)(x-2)(x-3)(x+4) = (x^2 - x - 2)(x^2 + x - 12) = x^4 - 15 x^2 + 10 x + 24.$$ So $A = -15$, $B = 10$, $C = 24$.

Therefore $2C - AB = 48 - (-15)(10) = 48 + 150 = \mathbf{198}$.

For any $x \neq 0$, $$x^n P\!\left(\frac{1}{x}\right) = x^n \left( a_n x^{-n} + a_{n-1} x^{-(n-1)} + \cdots + a_0 \right) = a_n + a_{n-1} x + \cdots + a_0 x^n = Q(x).$$

Since $a_0 \neq 0$, no root of $P$ is $0$. If $r$ is a root of $P$, then $r \neq 0$ and $$Q(1/r) = (1/r)^n P(r) = 0,$$ so $1/r$ is a root of $Q$. Conversely, $a_0 \neq 0$ ensures $\deg Q = n$, so $Q$ has $n$ roots (with multiplicity) just like $P$. Hence the roots of $Q$ are exactly $\{1/r : r \text{ root of } P\}$.

If $r$ is a root of $P$, we want $kr$ to be a root of the new polynomial $Q$, i.e. $Q(kr) = 0$. This suggests $Q(x) = P(x/k)$: $$P(x/k) = a_n \frac{x^n}{k^n} + a_{n-1} \frac{x^{n-1}}{k^{n-1}} + \cdots + a_0.$$

Multiplying by $k^n$ to clear denominators gives the polynomial $$Q(x) = a_n x^n + a_{n-1} k \, x^{n-1} + a_{n-2} k^2 \, x^{n-2} + \cdots + a_0 k^n = \sum_{i=0}^{n} a_i k^{n-i} x^i.$$

By construction, $Q(kr) = k^n P(r) = 0$ for every root $r$ of $P$, and since $\deg Q = n$, these are all the roots.

Set $y = \frac{1}{x+3}$, so $x = \frac{1-3y}{y}$. The roots of $P$ in $x$ map to $\frac{1}{a+3}, \frac{1}{b+3}, \frac{1}{c+3}$ in $y$, which are the roots of $y^3 \cdot P\!\left(\frac{1-3y}{y}\right)$: $$(1-3y)^3 + (1-3y)^2 y - (1-3y) y^2 - 3 y^3 = -18 y^3 + 20 y^2 - 8 y + 1.$$

By Vieta's, the sum of roots is $\displaystyle -\frac{20}{-18} = \mathbf{\frac{10}{9}}$.

For each root $r_i$, $P(r_i) = 0$: $$a_n r_i^n + a_{n-1} r_i^{n-1} + \cdots + a_0 = 0.$$ Multiplying by $r_i^{k-n}$ (valid since $k \geq n$) gives $$a_n r_i^k + a_{n-1} r_i^{k-1} + \cdots + a_0 r_i^{k-n} = 0.$$

Summing over $i = 1, \ldots, n$: $$a_n s_k + a_{n-1} s_{k-1} + \cdots + a_0 s_{k-n} = 0.$$ (For $k = n$, the last term is $a_0 s_0 = a_0 n$.)

Apply Newton's sums with $k = n = 1000$: $$a_{1000} s_{1000} + a_{999} s_{999} + \cdots + a_1 s_1 + a_0 \cdot 1000 = 0.$$ Here $a_{1000} = 1$, $a_1 = -10$, $a_0 = 10$, and all other coefficients vanish, so $$s_{1000} - 10 s_1 + 10000 = 0.$$

By Vieta's, $s_1 = \sum r_i = -a_{999}/a_{1000} = 0$. Therefore $$s_{1000} = -10000.$$

Expanding the square of $s_1$: $$s_1^2 = \left( \sum_{i=1}^{n} r_i \right)^2 = \sum_{i=1}^{n} r_i^2 + 2 \sum_{i \lt j} r_i r_j = s_2 + 2 e_2,$$ where $e_2 = \sum_{i \lt j} r_i r_j$ is the second elementary symmetric sum. Hence $s_2 = s_1^2 - 2 e_2$.

By Vieta's, $s_1 = e_1 = -\frac{a_{n-1}}{a_n}$ and $e_2 = \frac{a_{n-2}}{a_n}$, so $$s_2 = \frac{a_{n-1}^2}{a_n^2} - \frac{2 a_{n-2}}{a_n}.$$ Multiplying by $a_n$ and rearranging: $$a_n s_2 = \frac{a_{n-1}^2}{a_n} - 2 a_{n-2} = -a_{n-1} s_1 - 2 a_{n-2},$$ i.e. $a_n s_2 + a_{n-1} s_1 + 2 a_{n-2} = 0$.

Reversing the coefficients gives the polynomial whose roots are $\frac{1}{r}, \frac{1}{s}, \frac{1}{t}$ (since $x^3 P(1/x) = -7 x^3 + 5 x^2 - 6 x + 1$ vanishes at $1/r$ whenever $P(r) = 0$): $$Q(x) = -7 x^3 + 5 x^2 - 6 x + 1.$$ We want $s_2$ for $Q$. Applying Newton's identity $a_n s_2 + a_{n-1} s_1 + 2 a_{n-2} = 0$ with $a_3 = -7$, $a_2 = 5$, $a_1 = -6$: $$-7 s_2 + 5 s_1 - 12 = 0.$$

By Vieta's on $Q$, $s_1 = -\frac{a_2}{a_3} = \frac{5}{7}$, so $$-7 s_2 = 12 - 5 \cdot \frac{5}{7} = \frac{59}{7} \implies s_2 = \mathbf{-\frac{59}{49}}.$$

Since $P$ has integer coefficients, $a \equiv b \pmod 2 \implies P(a) \equiv P(b) \pmod 2$.

Suppose $r \in \mathbb{Z}$ is a root of $P$. Then $P(r) = 0$ is even. But $r$ is either even or odd:

• if $r$ is even, $P(r) \equiv P(0) \equiv 1 \pmod 2$;
• if $r$ is odd, $P(r) \equiv P(1) \equiv 1 \pmod 2$.

The $n$-th roots of unity are the roots of $P(x) = x^n - 1$. By Vieta's, $$\prod_{k=0}^{n-1} \omega_k = (-1)^n \frac{a_0}{a_n} = (-1)^n \cdot (-1) = (-1)^{n+1}.$$

So the product is $1$ if $n$ is odd, and $-1$ if $n$ is even.

Let the roots be $r$, $-r$, $s$. By Vieta's, $r + (-r) + s = \frac{12}{4} = 3$, so $s = 3$.

Method 1 (more Vieta's): The other two Vieta relations give $$r(-r) + rs + (-r)s = -r^2 = \frac{c}{4}, \qquad r \cdot (-r) \cdot s = -3 r^2 = -\frac{d}{4}.$$ So $r^2 = -\frac{c}{4} = \frac{d}{12}$, hence $d = -3c$ and $\displaystyle \frac{d}{c} = \mathbf{-3}$.

Method 2 (plug in the known root): Since $s = 3$ is a root, $P(3) = 0$: $$4(27) - 12(9) + 3c + d = 108 - 108 + 3c + d = 3c + d = 0,$$ so $d = -3c$ and $\displaystyle \frac{d}{c} = \mathbf{-3}$.

Method 1 (remainder theorem): The remainder of $P(x)$ divided by $x - a$ is $P(a)$. Here $P(x) = x^{13} + 1$ and $a = 1$, so the remainder is $P(1) = 1 + 1 = \mathbf{2}$.

Method 2 (explicit division): Using the geometric series identity $x^{13} - 1 = (x-1)(x^{12} + x^{11} + \cdots + x + 1)$, we get $$x^{13} + 1 = (x-1)\underbrace{(x^{12} + x^{11} + \cdots + x + 1)}_{Q(x)} + \underbrace{2}_{R}.$$

Set $P(x) = (1 + x + x^2)^n$. Then $$P(1) = a_0 + a_1 + \cdots + a_{2n}, \qquad P(-1) = a_0 - a_1 + a_2 - \cdots + a_{2n}.$$ Adding and dividing by $2$ isolates the even-indexed coefficients: $$a_0 + a_2 + \cdots + a_{2n} = \frac{P(1) + P(-1)}{2} = \frac{3^n + 1^n}{2} = \mathbf{\frac{3^n + 1}{2}}.$$

Method 1 (congruences): Since $x^4 \equiv 1 \pmod{x^4 - 1}$ and $203 = 4 \cdot 50 + 3$, $$x^{203} = (x^4)^{50} \cdot x^3 \equiv x^3 \pmod{x^4 - 1}.$$ So $x^{203} - 1 \equiv x^3 - 1 \pmod{x^4 - 1}$, and the remainder is $\mathbf{x^3 - 1}$.

Method 2 (evaluate at roots): Write the Euclidean division as $x^{203} - 1 = (x^4 - 1) Q(x) + R(x)$ with $R(x) = a x^3 + b x^2 + c x + d$. The roots of $x^4 - 1$ are $1, -1, i, -i$, and at each root the left side equals $R$ evaluated there. Using $i^{203} = i^{4 \cdot 50 + 3} = i^3 = -i$:

• $x = 1$:   $0 = a + b + c + d$,
• $x = -1$:   $-2 = -a + b - c + d$,
• $x = i$:   $-i - 1 = -a i - b + c i + d$,
• $x = -i$:   $i - 1 = a i - b - c i + d$.

From the first two: $b + d = -1$ and $a + c = 1$. From the last two (real and imaginary parts): $-b + d = -1$ and $a - c = 1$. Solving: $a = 1$, $b = 0$, $c = 0$, $d = -1$, giving $R(x) = \mathbf{x^3 - 1}$.

Set $Y = P(X)$. The equation becomes $P(Y) = Y^k$ for every $Y$ in the image of $P$.

Case 1: $P$ non-constant. Then $P$ takes infinitely many values, so $P(Y) - Y^k$ vanishes at infinitely many points, hence $P(Y) = Y^k$ as polynomials. Conversely, $P(X) = X^k$ satisfies $P(P(X)) = (X^k)^k = X^{k^2} = P(X)^k$.

Case 2: $P$ constant, $P(X) = c$. Then $c = c^k$, i.e. $c(c^{k-1} - 1) = 0$. Over $\mathbb{R}$, this gives $c = 0$, $c = 1$, or $c = -1$ (the last only when $k$ is odd, so that $k-1$ is even).

The real solutions are therefore $P(X) = X^k$, $P(X) = 0$, $P(X) = 1$, and (for odd $k$) $P(X) = -1$.

Setting $y = 1$ gives $f(x) = x f(1)$, so $f(x) = cx$ with $c = f(1)$.

Conversely, $f(x) = cx$ satisfies $f(xy) = c(xy) = x (cy) = x f(y)$. So the solutions are exactly $f(x) = cx$, $c \in \mathbb{R}$.

Method 1: Setting $y = 1$ gives $f(x) = x f(1)$. Writing $c = f(1)$, we get $f(x) = cx$ for all $x$.

Method 2: For $x, y \neq 0$, dividing both sides by $xy$ gives $\frac{f(x)}{x} = \frac{f(y)}{y}$. So $g(t) = \frac{f(t)}{t}$ takes the same value for every nonzero $t$, i.e. $g$ is constant on $\mathbb{R} \setminus \{0\}$. Call this constant $c$; then $f(t) = ct$ for all $t \neq 0$. For $t = 0$, setting $x = 0$ and any $y \neq 0$ in the original equation gives $y f(0) = 0$, hence $f(0) = 0 = c \cdot 0$.

Conversely, any $f(x) = cx$ satisfies $y \cdot cx = x \cdot cy$. So the solutions are exactly the linear maps $f(x) = cx$, $c \in \mathbb{R}$.

Method 1: Setting $y = 0$ gives $2 f(x) = 2 x^2$, so $f(x) = x^2$.

Method 2: Setting $x = y = 0$ gives $2 f(0) = 0$, so $f(0) = 0$. Setting $x = y$ then gives $f(2x) + f(0) = 4 x^2$, so $f(2x) = (2x)^2$, i.e. $f(u) = u^2$ for all $u \in \mathbb{R}$.

Conversely, $f(x) = x^2$ satisfies $(x+y)^2 + (x-y)^2 = 2x^2 + 2y^2$. So $f(x) = x^2$ is the unique solution.

Setting $y = 0$ gives $2 f(x) = 2 x^2$, so $f(x) = x^2$. Setting $x = 0$ gives $f(y) + f(-y) = -2 y^2$, but $f(y) + f(-y) = y^2 + y^2 = 2 y^2$, forcing $4 y^2 = 0$ for all $y$, a contradiction.

Hence no such function exists.

Substituting $x \to \frac{1}{x}$ in the equation gives a second relation: $$f(x) + 2 f(1/x) = x, \qquad f(1/x) + 2 f(x) = \frac{1}{x}.$$

This is a linear system in $f(x)$ and $f(1/x)$. Multiplying the second by $2$ and subtracting the first: $$3 f(x) = \frac{2}{x} - x \implies f(x) = \frac{2 - x^2}{3 x}.$$

Conversely, this $f$ satisfies the equation: $\displaystyle \frac{2 - x^2}{3x} + 2 \cdot \frac{2 - 1/x^2}{3/x} = \frac{2 - x^2 + 4 x^2 - 2}{3 x} = x.$

Note that $a = \frac{1+a}{2} - \frac{1-a}{2}$, so the equation rewrites as $$f\!\left(\frac{1+a}{2}\right) - \frac{1+a}{2} = f\!\left(\frac{1-a}{2}\right) - \frac{1-a}{2}.$$ Defining $g(x) = f(x) - x$, this says $g\!\left(\frac{1+a}{2}\right) = g\!\left(\frac{1-a}{2}\right)$ for all $a$, i.e. $g(u) = g(1 - u)$ for all $u$ (since $\frac{1+a}{2} + \frac{1-a}{2} = 1$).

Now define $h(x) = g\!\left(x + \tfrac{1}{2}\right)$. The condition $g(u) = g(1-u)$ becomes $$h\!\left(u - \tfrac{1}{2}\right) = h\!\left(\tfrac{1}{2} - u\right),$$ i.e. $h(t) = h(-t)$: $h$ must be even.

Hence the solutions are exactly $$f(x) = x + h\!\left(x - \tfrac{1}{2}\right),$$ where $h : \mathbb{R} \to \mathbb{R}$ is any even function. (Taking $h(t) = t^2$ recovers $f(x) = x + (x - \tfrac{1}{2})^2 = x^2 + \tfrac{1}{4}$.)

Cross-multiplying gives $x f(x) = y f(y)$ for all $x, y$. So $x f(x)$ is independent of $x$: there is a constant $c$ with $x f(x) = c$, i.e. $f(x) = \frac{c}{x}$. Since $f$ is $\mathbb{R}^*$-valued, $c \neq 0$.

Conversely, $f(x) = c/x$ satisfies $\frac{c/x}{c/y} = \frac{y}{x}$. So the solutions are $f(x) = \frac{c}{x}$ for $c \in \mathbb{R}^*$.

Setting $x = y$ gives $f(2x) - f(0) = 4 x^2$, so $f(u) = u^2 + f(0)$ for all $u \in \mathbb{R}$.

Conversely, $f(x) = x^2 + c$ satisfies $(x+y)^2 - (x-y)^2 = 4xy$. So the solutions are $f(x) = x^2 + c$, $c \in \mathbb{R}$.

Since $1 - 2x = (1-x) - x$, the equation rewrites as $$f(1-x) - (1-x) = f(x) - x.$$ Define $g(x) = f(x) - x$; then $g(1-x) = g(x)$, so $g$ is symmetric about $\tfrac{1}{2}$.

Equivalently, letting $h(t) = g(t + \tfrac{1}{2})$, the condition $g(1-x) = g(x)$ becomes $h(-t) = h(t)$: $h$ is even.

Hence the solutions are exactly $$f(x) = x + h\!\left(x - \tfrac{1}{2}\right),$$ where $h : \mathbb{R} \to \mathbb{R}$ is any even function.

Factor the denominator: $x^2 - 3x + 2 = (x-1)(x-2)$. Testing $x = 2$ in the numerator: $16 - 12 + 2 - 6 = 0$, so $x - 2$ divides the numerator: $$2 x^3 - 3 x^2 + x - 6 = (x - 2)(2 x^2 + x + 3).$$ Hence for $x \neq 2$, $$f(x) = \frac{2 x^2 + x + 3}{x - 1}.$$ The quadratic $2x^2 + x + 3$ has discriminant $1 - 24 \lt 0$, so it has no real roots and $f$ has no $x$-intercepts.

Polynomial division yields $$f(x) = 2 x + 3 + \frac{6}{x - 1}.$$ Key features:

• Removable discontinuity at $x = 2$: the factor $x - 2$ cancels, so $f$ extends by continuity with $f(2) = 13$ (a "hole" in the graph if we keep the original domain).
• Vertical asymptote $x = 1$: $f \to -\infty$ as $x \to 1^-$, $f \to +\infty$ as $x \to 1^+$.
• Oblique asymptote $y = 2 x + 3$.
• $y$-intercept: $f(0) = -3$.

Recognize the limit as a derivative at $0$: $$\lim_{x \to 0} \frac{\sin x}{x} = \lim_{x \to 0} \frac{\sin x - \sin 0}{x - 0} = \sin'(0) = \cos(0) = 1.$$

Write $\tan 3x = \frac{\sin 3x}{\cos 3x}$ and rearrange: $$\frac{\tan 3 x}{4 x} = \frac{\sin 3 x}{3 x} \cdot \frac{3 x}{4 x \cos 3 x}.$$ As $x \to 0$, $\frac{\sin 3x}{3x} \to 1$ and $\cos 3x \to 1$, so the limit is $\displaystyle 1 \cdot \frac{3}{4} = \mathbf{\frac{3}{4}}$.

Take the log: $$\ln\!\left(1 + \tfrac{1}{n}\right)^n = n \ln\!\left(1 + \tfrac{1}{n}\right) = \frac{\ln(1 + 1/n) - \ln 1}{1/n}.$$ As $n \to \infty$, $h = 1/n \to 0$, and this is the difference quotient for $\ln$ at $1$: $$\frac{\ln(1+h) - \ln 1}{h} \longrightarrow \ln'(1) = 1.$$ By continuity of $\exp$, $\displaystyle \left(1 + \tfrac{1}{n}\right)^n = e^{n \ln(1 + 1/n)} \longrightarrow e^1 = e$.

With $n$ equal compounding periods, the balance after one year is $\left(1 + \tfrac{1}{n}\right)^n$. Letting $n \to \infty$ gives $\displaystyle \lim_{n \to \infty} \left(1 + \tfrac{1}{n}\right)^n = e \approx 2.718$ dollars.

Let $u = x/2$, so $\frac{2}{x} = \frac{1}{u}$ and $3 x = 6 u$: $$\left(1 + \frac{2}{x}\right)^{3 x} = \left(1 + \frac{1}{u}\right)^{6 u} = \left(\left(1 + \frac{1}{u}\right)^{u}\right)^{6}.$$ As $x \to \infty$, $u \to \infty$, and $\left(1 + \frac{1}{u}\right)^u \to e$, so the limit is $\mathbf{e^6}$.

Factor using the sum of cubes: $x^3 + 8 = (x + 2)(x^2 - 2 x + 4)$, so for $x \neq -2$, $$\frac{x^3 + 8}{x + 2} = x^2 - 2 x + 4.$$ Taking $x \to -2$: $(-2)^2 - 2(-2) + 4 = \mathbf{12}$.

Polynomial division gives $$f(x) = x - 3 + \frac{4}{x + 2}.$$ As $x \to \pm \infty$, $\frac{4}{x+2} \to 0$, so the oblique asymptote is $\mathbf{y = x - 3}$. Since the numerator does not vanish at $x = -2$ (it equals $4$ there), $f$ also has a vertical asymptote at $\mathbf{x = -2}$.

Recognize the negative of a difference quotient for $\cos$ at $0$: $$\lim_{x \to 0} \frac{1 - \cos x}{x} = -\lim_{x \to 0} \frac{\cos x - \cos 0}{x - 0} = -\cos'(0) = \sin(0) = \mathbf{0}.$$

Polynomial division: $x^3 = x(x^2 - 1) + x$, so $$f(x) = x + \frac{x}{x^2 - 1}.$$ As $x \to \pm \infty$, $\frac{x}{x^2 - 1} \to 0$, giving the oblique asymptote $\mathbf{y = x}$.

The denominator $x^2 - 1 = (x-1)(x+1)$ vanishes at $x = \pm 1$ while the numerator does not, so there are vertical asymptotes at $\mathbf{x = 1}$ and $\mathbf{x = -1}$.

Convert to polar form: $$|4 + 4 i \sqrt{3}| = \sqrt{16 + 48} = 8, \qquad \arg = \arctan(\sqrt{3}) = \frac{\pi}{3}.$$ So $4 + 4 i \sqrt{3} = 8 e^{i \pi / 3}$.

The three cube roots are $$w_k = 8^{1/3} \, e^{i(\pi/3 + 2 \pi k)/3} = 2 \, e^{i(\pi/9 + 2 \pi k / 3)}, \qquad k = 0, 1, 2.$$ Explicitly: $\displaystyle 2 e^{i \pi / 9}, \; 2 e^{i 7 \pi / 9}, \; 2 e^{i 13 \pi / 9}$.

By De Moivre's theorem, $(\cos \theta + i \sin \theta)^3 = \cos(3\theta) + i \sin(3\theta)$. Expanding the left side: $$\cos^3 \theta + 3 i \cos^2 \theta \sin \theta - 3 \cos \theta \sin^2 \theta - i \sin^3 \theta.$$ Taking the real part and using $\sin^2 \theta = 1 - \cos^2 \theta$: $$\cos(3 \theta) = \cos^3 \theta - 3 \cos \theta (1 - \cos^2 \theta) = \mathbf{4 \cos^3 \theta - 3 \cos \theta}.$$

This is a geometric series with ratio $\omega \neq 1$, so $$1 + \omega + \omega^2 + \cdots + \omega^{n-1} = \frac{1 - \omega^n}{1 - \omega}.$$ Since $\omega$ is an $n$-th root of unity, $\omega^n = 1$, so the numerator vanishes while the denominator $1 - \omega \neq 0$. Hence the sum is $\mathbf{0}$.

Case $\omega = 1$: the product is $(1)(1) = 1$.

Case $\omega \neq 1$ (a primitive cube root): then $1 + \omega + \omega^2 = 0$, so $\omega^2 = -1 - \omega$. Substituting, $$1 - \omega + \omega^2 = (1 + \omega + \omega^2) - 2\omega = -2\omega, \qquad 1 + \omega - \omega^2 = (1 + \omega + \omega^2) - 2\omega^2 = -2\omega^2.$$ Hence the product is $(-2\omega)(-2\omega^2) = 4\omega^3 = 4$ (using $\omega^3 = 1$).

The $n$-th roots of unity are $\omega_k = e^{2\pi i k / n}$ for $k = 0, 1, \ldots, n-1$. Their product is $$\prod_{k=0}^{n-1} e^{2\pi i k / n} = e^{\frac{2\pi i}{n} \sum_{k=0}^{n-1} k} = e^{\frac{2\pi i}{n} \cdot \frac{n(n-1)}{2}} = e^{\pi i (n-1)} = (-1)^{n+1}.$$ So the product is $1$ if $n$ is odd, and $-1$ if $n$ is even.

By the multinomial theorem, $$(a + b + c)^3 = \sum_{i+j+k=3} \binom{3}{i,\,j,\,k} a^i b^j c^k, \qquad \binom{3}{i,\,j,\,k} = \frac{3!}{i!\,j!\,k!}.$$ Group the terms by the shape of $(i, j, k)$:

• $(3,0,0)$ and permutations: coefficient $\frac{3!}{3!} = 1$, giving $a^3 + b^3 + c^3$;
• $(2,1,0)$ and permutations: coefficient $\frac{3!}{2!\,1!} = 3$, giving $3(a^2 b + a^2 c + b^2 a + b^2 c + c^2 a + c^2 b)$;
• $(1,1,1)$: coefficient $\frac{3!}{1!\,1!\,1!} = 6$, giving $6abc$.

Hence $$(a + b + c)^3 = a^3 + b^3 + c^3 + 3(a^2 b + a^2 c + b^2 a + b^2 c + c^2 a + c^2 b) + 6abc.$$

The three quantities are the elementary symmetric sums of $x, y, z$, so by Vieta's formulas $x, y, z$ are the roots of $$t^3 - 7 t^2 - 14 t + 120 = 0.$$ By the rational root theorem, any rational root divides $120$. Testing $t = 5$: $125 - 175 - 70 + 120 = 0$, so $t = 5$ is a root. Factoring, $$t^3 - 7 t^2 - 14 t + 120 = (t - 5)(t^2 - 2 t - 24) = (t - 5)(t - 6)(t + 4).$$ Hence $\{x, y, z\} = \{5, 6, -4\}$. Since the three values are distinct and the system is symmetric, every ordering gives a valid solution, so there are $3! = \mathbf{6}$ ordered solutions $(x, y, z)$.

Multiply both sides by the common denominator $L = abc\,(a-b)(a-c)(b-c)$, which is nonzero. The identity is then equivalent to $f(c) = 0$, where $$f(c) = bc(b-c) - ac(a-c) + ab(a-b) - (a-b)(a-c)(b-c).$$

Regard $a, b$ as fixed and $f$ as a polynomial in $c$. Each term is at most quadratic in $c$, so $\deg f \leq 2$. We check that $f$ vanishes at three distinct points:

• $f(0) = ab(a-b) - (a-b)\,a\,b = 0$;
• $f(a) = ab(b-a) + ab(a-b) = 0$ (the other two terms carry a factor $a-a$);
• $f(b) = -ab(a-b) + ab(a-b) = 0$ (the other two terms carry a factor $b-b$).

A polynomial of degree at most $2$ with three distinct roots $c = 0, a, b$ is identically zero. Hence $f \equiv 0$, and dividing back by $L$ gives the identity.

Since the square of a real number is non-negative, $$0 \leq (a + b + c)^2 = a^2 + b^2 + c^2 + 2(ab + bc + ca) = 1 + 2(ab + bc + ca),$$ so $ab + bc + ca \geq -\frac{1}{2}$.

Equality holds when $a + b + c = 0$ together with $a^2 + b^2 + c^2 = 1$, for instance $a = \frac{1}{\sqrt 2}$, $b = -\frac{1}{\sqrt 2}$, $c = 0$. So the minimum value is $\mathbf{-\frac{1}{2}}$.

The coefficient matrix is $$M = \begin{pmatrix} n & 1 & 0 \\ 0 & n & 1 \\ 1 & 0 & n \end{pmatrix}, \qquad \det M = n^3 + 1.$$ If $\det M \neq 0$ the system has a unique solution. When $\det M = 0$ the system is not guaranteed to be solvable: it has either no solution or infinitely many. So the only candidate for "no solution" is $n^3 + 1 = 0$, i.e. (over the reals) $n = -1$, and we must check which case occurs there.

For $n = -1$ the system is $$-x + y = 1, \qquad -y + z = 1, \qquad x - z = 1.$$ Adding the three equations, the left side is $(-x+y) + (-y+z) + (x-z) = 0$, while the right side is $3$. This gives $0 = 3$, a contradiction, so the system is inconsistent.

Hence the system has no solution exactly when $\mathbf{n = -1}$.

Complete the square: $$x^2 + 2x + 2 = (x + 1)^2 + 1.$$ Since $(x+1)^2 \geq 0$, the expression is at least $1$, with equality at $x = -1$. So the minimum value is $\mathbf{1}$.

We use the single elementary fact that $e^{t} \geq 1 + t$ for all real $t$. To justify it, let $g(t) = e^t - 1 - t$. Then $g'(t) = e^t - 1$, which is negative for $t \lt 0$ and positive for $t \gt 0$, so $g$ is decreasing on $(-\infty, 0]$ and increasing on $[0, \infty)$. Thus $g$ attains its global minimum at $t = 0$, where $g(0) = 0$. Hence $g(t) \geq 0$, i.e. $e^t \geq 1 + t$, with equality only at $t = 0$. Replacing $t$ by $t - 1$, this reads $e^{\,t-1} \geq t$.

Let $A = \dfrac{a_1 + \cdots + a_n}{n}$ be the arithmetic mean. Apply the inequality with $t = \dfrac{a_i}{A}$ for each $i$: $$e^{\,a_i/A - 1} \geq \frac{a_i}{A}.$$ Multiplying these $n$ inequalities (all sides positive), $$\exp\!\left( \frac{a_1 + \cdots + a_n}{A} - n \right) \geq \frac{a_1 a_2 \cdots a_n}{A^n}.$$ Since $a_1 + \cdots + a_n = nA$, the exponent on the left is $n - n = 0$, so the left side is $e^0 = 1$. Hence $$a_1 a_2 \cdots a_n \leq A^n \implies \sqrt[n]{a_1 a_2 \cdots a_n} \leq A,$$ which is exactly the claim. Equality requires $e^{\,t-1} = t$ at each step, i.e. every $a_i/A = 1$, so all the $a_i$ are equal.

Apply AM–GM to the non-negative pairs $x^2, y^2$ etc. For any two reals, $$\frac{x^2 + y^2}{2} \geq \sqrt{x^2 y^2} = |xy| \geq xy, \qquad\text{so}\qquad x^2 + y^2 \geq 2xy.$$ Likewise $y^2 + z^2 \geq 2yz$ and $z^2 + x^2 \geq 2zx$. Adding the three inequalities, $$2(x^2 + y^2 + z^2) \geq 2(xy + yz + zx),$$ hence $x^2 + y^2 + z^2 \geq xy + yz + zx$, with equality if and only if $x = y = z$.

If every $a_i = 0$ both sides are $0$ and the inequality holds. Otherwise $\sum a_i^2 \gt 0$, and we consider the function $$f(t) = \sum_{i=1}^{n} (a_i t + b_i)^2 = \left( \sum a_i^2 \right) t^2 + 2 \left( \sum a_i b_i \right) t + \left( \sum b_i^2 \right).$$ Being a sum of squares, $f(t) \geq 0$ for every real $t$. So this quadratic in $t$ (with positive leading coefficient) has at most one real root, which forces its discriminant to be $\leq 0$: $$\left( 2 \sum a_i b_i \right)^2 - 4 \left( \sum a_i^2 \right) \left( \sum b_i^2 \right) \leq 0.$$ Dividing by $4$ rearranges to $$\left( \sum a_i b_i \right)^2 \leq \left( \sum a_i^2 \right) \left( \sum b_i^2 \right),$$ which is the inequality. Equality holds iff $f$ has a real root, i.e. $a_i t + b_i = 0$ for all $i$ at some $t$, meaning the vectors $(a_i)$ and $(b_i)$ are proportional.

Work backwards. Multiplying by $n \gt 0$, the claim is equivalent to $$n \left( 1^2 + 2^2 + \cdots + n^2 \right) \geq (1 + 2 + \cdots + n)^2.$$ Writing $n = 1^2 + 1^2 + \cdots + 1^2$, this reads $$\left( 1^2 + \cdots + n^2 \right)\left( 1^2 + \cdots + 1^2 \right) \geq (1\cdot 1 + \cdots + n \cdot 1)^2,$$ which is Cauchy–Schwarz with $a_k = k$, $b_k = 1$. As the steps are equivalences, the original holds.

By AM–GM, $$\frac{x + y + z}{3} \geq \sqrt[3]{xyz} = \sqrt[3]{27} = 3,$$ so $x + y + z \geq 9$, with equality when $x = y = z = 3$. The minimum value is $\mathbf{9}$.

Let the box have edge lengths $x, y, z \gt 0$. Covering it uses paper equal to its surface area, so $$2(xy + yz + zx) = 96 \implies xy + yz + zx = 48.$$ We maximize the volume $V = xyz$. By AM–GM applied to the three positive numbers $xy, yz, zx$, $$\frac{xy + yz + zx}{3} \geq \sqrt[3]{(xy)(yz)(zx)} = \sqrt[3]{(xyz)^2},$$ so $16 \geq (xyz)^{2/3}$, giving $xyz \leq 16^{3/2} = 64$.

Equality holds when $xy = yz = zx$, i.e. $x = y = z$; then $6x^2 = 96$ gives $x = 4$ (a cube). The largest box has volume $\mathbf{64}$ cubic meters.

Method 1 (average bound): Since the smaller of two numbers is at most their average, $$\min(x, y) \leq \frac{x + y}{2} = 2,$$ with equality precisely when $x = y$, i.e. $x = y = 2$. So the maximum value of $\min(x, y)$ is $\mathbf{2}$.

Method 2 (order the variables): Without loss of generality, assume $x \geq y$, so $\min(x, y) = y$. Then $x + y \geq 2y$, i.e. $4 \geq 2y$, giving $y \leq 2$. So $\min(x, y) \leq 2$, with equality when $x = y = 2$, and the maximum is $\mathbf{2}$.

By the Cauchy–Schwarz inequality with $b_i = 1$ for all $i$, $$\left( \sum_{i=1}^{n} a_i \right)^2 = \left( \sum_{i=1}^{n} a_i \cdot 1 \right)^2 \leq \left( \sum_{i=1}^{n} a_i^2 \right) \left( \sum_{i=1}^{n} 1^2 \right) = n \sum_{i=1}^{n} a_i^2.$$ Dividing by $n^2$ gives $$\left( \frac{a_1 + \cdots + a_n}{n} \right)^2 \leq \frac{a_1^2 + \cdots + a_n^2}{n}.$$ The right-hand side is non-negative, so taking square roots, $$\frac{a_1 + \cdots + a_n}{n} \leq \left| \frac{a_1 + \cdots + a_n}{n} \right| \leq \sqrt{\frac{a_1^2 + \cdots + a_n^2}{n}},$$ which is the claim. Equality requires the Cauchy–Schwarz vectors to be proportional, i.e. all the $a_i$ equal, and the arithmetic mean to be non-negative.

Apply AM–GM to the positive reals $\frac{1}{a_1}, \ldots, \frac{1}{a_n}$: $$\frac{\frac{1}{a_1} + \cdots + \frac{1}{a_n}}{n} \geq \sqrt[n]{\frac{1}{a_1} \cdots \frac{1}{a_n}} = \frac{1}{\sqrt[n]{a_1 \cdots a_n}}.$$ Both sides are positive, so taking reciprocals reverses the inequality: $$\frac{n}{\frac{1}{a_1} + \cdots + \frac{1}{a_n}} \leq \sqrt[n]{a_1 \cdots a_n},$$ which is exactly $\mathrm{HM} \leq \mathrm{GM}$. Equality holds iff all the $\frac{1}{a_i}$ are equal, i.e. all the $a_i$ are equal.

Method 1 (AM–GM): Expand using the constraint: $$(x + y)^2 = x^2 + 2xy + y^2 = 1 + 2xy.$$ Since $x^2 + y^2 \geq 2xy$ for all reals (it rearranges to $(x - y)^2 \geq 0$), we have $2xy \leq x^2 + y^2 = 1$, so $$(x + y)^2 = 1 + 2xy \leq 2.$$ Equality requires $x = y$; combined with $x^2 + y^2 = 1$ this gives $x = y = \pm\frac{1}{\sqrt 2}$. The maximum value is $\mathbf{2}$.

Method 2 (trigonometry): Since $x^2 + y^2 = 1$, write $x = \cos\theta$, $y = \sin\theta$. Then $$(x + y)^2 = (\cos\theta + \sin\theta)^2 = 1 + 2\sin\theta\cos\theta = 1 + \sin 2\theta.$$ Since $\sin 2\theta \leq 1$, we get $(x + y)^2 \leq 2$, with equality when $\sin 2\theta = 1$, i.e. $\theta = \frac{\pi}{4}$ (so $x = y = \frac{1}{\sqrt 2}$) or $\theta = \frac{5\pi}{4}$ (so $x = y = -\frac{1}{\sqrt 2}$). The maximum value is $\mathbf{2}$.

It suffices to exhibit a family of valid $(x, y, z)$ on which the minimum grows without bound. For a parameter $n \gt 1$, take $$x = y = n, \qquad z = \frac{1}{n^2},$$ which is positive and satisfies $xyz = n \cdot n \cdot \frac{1}{n^2} = 1$.

The three pairwise sums are $$x + y = 2n, \qquad x + z = y + z = n + \frac{1}{n^2}.$$ For $n \gt 1$ we have $\frac{1}{n^2} \lt n$, so $n + \frac{1}{n^2} \lt 2n$, and therefore $$\min(x + y, \, x + z, \, y + z) = n + \frac{1}{n^2} \gt n.$$ As $n \to \infty$ this exceeds any fixed bound, so $\min(x + y, x + z, y + z)$ is unbounded above and has no maximum.

Method 1 (sum of the pairwise sums): Write $M = \max(x + y, \, x + z, \, y + z)$. Each of the three pairwise sums is at most $M$, and adding them gives $$2(x + y + z) = (x + y) + (x + z) + (y + z) \leq 3M,$$ so $M \geq \frac{2}{3}(x + y + z)$.

By AM–GM, $x + y + z \geq 3\sqrt[3]{xyz} = 3$, hence $$M \geq \frac{2}{3} \cdot 3 = 2.$$ So no triple makes the maximum smaller than $2$. The value $2$ is attained at $x = y = z = 1$ (where $xyz = 1$ and all three pairwise sums equal $2$), so the minimum of $\max(x + y, x + z, y + z)$ is exactly $\mathbf{2}$.

Method 2 (order the variables): Without loss of generality, assume $x \leq y \leq z$. Then the largest pairwise sum is the sum of the two largest variables, so $M = y + z$.

Since $x$ is the smallest, $x \leq 1$: otherwise $x \gt 1$ would force $y, z \gt 1$ as well, giving $xyz \gt 1$, a contradiction. By AM–GM, $x + y + z \geq 3\sqrt[3]{xyz} = 3$, so $$M = y + z = (x + y + z) - x \geq 3 - x \geq 2,$$ with equality at $x = y = z = 1$. Hence the minimum is $\mathbf{2}$.

Without loss of generality, assume $x \leq y \leq z$. Then the smallest pairwise product is that of the two smallest variables, so $\min(xy, xz, yz) = xy$.

Since $z$ is the largest, $z \geq 1$ (the largest of three numbers averaging $1$), so $x + y = 3 - z \leq 2$. By AM–GM, $$xy \leq \left(\frac{x + y}{2}\right)^2 \leq 1,$$ with equality at $x = y = z = 1$. Hence the maximum is $\mathbf{1}$.

Apply AM–GM to the two non-negative numbers $2ab$ and $a^2 + b^2$: $$\sqrt{2ab(a^2 + b^2)} \leq \frac{2ab + (a^2 + b^2)}{2} = \frac{(a + b)^2}{2},$$ which is the claim. Equality holds when $2ab = a^2 + b^2$, i.e. $a = b$.

The $n$ numbers $x + r_1, \ldots, x + r_n$ are positive, so AM–GM applies: $$\sqrt[n]{(x + r_1)(x + r_2) \cdots (x + r_n)} \leq \frac{(x + r_1) + (x + r_2) + \cdots + (x + r_n)}{n} = x + \frac{r_1 + \cdots + r_n}{n}.$$ Raising both sides to the $n$-th power gives the claim. Equality holds when all the $x + r_i$ are equal, i.e. all the $r_i$ are equal.

Let the roots be $p, q, r \geq 0$. By Vieta's formulas, $$p + q + r = 12, \qquad pq + qr + rp = a, \qquad pqr = 64.$$ By AM–GM, $$\frac{p + q + r}{3} \geq \sqrt[3]{pqr} \quad\Longrightarrow\quad 4 \geq \sqrt[3]{64} = 4.$$ Equality holds, which forces $p = q = r = 4$. Therefore $$a = pq + qr + rp = 3 \cdot 16 = \mathbf{48}.$$

Raising both sides to the $2n$-th power, the claim is equivalent to $n^n \leq (n!)^2$. Write $$(n!)^2 = \prod_{k=1}^{n} k \cdot \prod_{k=1}^{n} (n + 1 - k) = \prod_{k=1}^{n} k(n + 1 - k),$$ where the second product just runs over the same factors in reverse order. For each $k$ with $1 \leq k \leq n$, $$k(n + 1 - k) - n = (k - 1)(n - k) \geq 0,$$ so $k(n + 1 - k) \geq n$. Multiplying these $n$ inequalities gives $(n!)^2 \geq n^n$, which is the claim.

Count pairs $(A, B)$ with $A \subseteq B \subseteq \{1, \ldots, n\}$, $|B| = k$, $|A| = m$ in two ways.

Picking $B$ then $A$: $\binom{n}{k}$ ways for $B$, then $\binom{k}{m}$ for $A$ inside $B$.

Picking $A$ then $B$: $\binom{n}{m}$ ways for $A$, then $\binom{n - m}{k - m}$ for the remaining elements of $B$, chosen from outside $A$.

Let $S = \sum_{k=0}^{n} k\binom{n}{k}$. Using $\binom{n}{k} = \binom{n}{n-k}$ and reindexing, write the same sum in reverse: $$S = \sum_{k=0}^{n} (n - k)\binom{n}{n - k} = \sum_{k=0}^{n} (n - k)\binom{n}{k}.$$ Adding the two expressions for $S$, $$2S = \sum_{k=0}^{n} \big(k + (n - k)\big)\binom{n}{k} = n \sum_{k=0}^{n} \binom{n}{k} = n \cdot 2^n,$$ so $S = n \cdot 2^{n-1}$.

Count the ways to choose an $n$-element committee from a group of $n$ men and $n$ women, which is $\binom{2n}{n}$.

Split by the number $k$ of men chosen: pick $k$ of the $n$ men in $\binom{n}{k}$ ways and $n - k$ of the $n$ women in $\binom{n}{n - k} = \binom{n}{k}$ ways, giving $\binom{n}{k}^2$ committees. Summing over $k$ from $0$ to $n$ counts every committee once, so $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$.

The general term is $$\binom{6}{k}(x^2)^{6 - k}\left(\frac{1}{x}\right)^k = \binom{6}{k} x^{12 - 3k}.$$ The exponent vanishes when $12 - 3k = 0$, i.e. $k = 4$, giving the constant term $\binom{6}{4} = \mathbf{15}$.

The exponents $2 + 3 + 1 + 4 = 10$ match the power, so the coefficient is the multinomial coefficient $$\binom{10}{2,\,3,\,1,\,4} = \frac{10!}{2!\,3!\,1!\,4!} = \mathbf{12600}.$$

$$(x + y + z)^n = \sum_{\substack{i + j + k = n \\ i,\, j,\, k \geq 0}} \frac{n!}{i!\,j!\,k!}\, x^i y^j z^k,$$ where the sum runs over all non-negative integer triples $(i, j, k)$ with $i + j + k = n$.

Count the $m$-element subsets of an $(n + m)$-element set partitioned into a part $X$ of size $n$ and a part $Y$ of size $m$. There are $\binom{n + m}{m} = \binom{n + m}{n}$ of them.

Split by the number $k$ of elements taken from $X$: pick $k$ from $X$ in $\binom{n}{k}$ ways and the remaining $m - k$ from $Y$ in $\binom{m}{m - k} = \binom{m}{k}$ ways, giving $\binom{n}{k}\binom{m}{k}$ subsets. Summing over $k$ counts every $m$-subset once.

The inner sum is $\sum_{k=1}^{i} \binom{i}{k} = 2^i - \binom{i}{0} = 2^i - 1$. Therefore $$\sum_{i=1}^{10} (2^i - 1) = \sum_{i=1}^{10} 2^i - 10 = (2^{11} - 2) - 10 = 2046 - 10 = \mathbf{2036}.$$

Start from the right-hand side and repeatedly apply Pascal's rule $\binom{m}{j} = \binom{m - 1}{j} + \binom{m - 1}{j - 1}$, each time splitting off one term of the sum: $$\binom{n + k + 1}{k + 1} = \binom{n + k}{k + 1} + \binom{n + k}{k} = \binom{n + k}{k + 1} + \binom{n + k - 1}{k} + \binom{n + k - 1}{k - 1} = \cdots$$ Splitting the rightmost binomial each step peels off the terms $\binom{n + k}{k + 1}, \binom{n + k - 1}{k}, \ldots, \binom{n}{1}$ in turn, and the last remainder is $\binom{n}{0} = \binom{n - 1}{0}$. Collecting these is exactly the left-hand side.

Alternative proof by counting subsets. The right-hand side $\binom{n + k + 1}{k + 1} = \binom{n + k + 1}{n}$ counts the $n$-element subsets of $\{1, 2, \ldots, n + k + 1\}$. Classify each subset by its largest element $m$: the other $n - 1$ elements lie in $\{1, \ldots, m - 1\}$, giving $\binom{m - 1}{n - 1}$ subsets, and $m$ ranges from $n$ to $n + k + 1$. Writing $m = n + j$ for $j = 0, \ldots, k + 1$, this term is $\binom{n - 1 + j}{n - 1} = \binom{n - 1 + j}{j}$, the $j$-th term of the left-hand side. Summing over $m$ counts every subset once.

The sum of the coefficients is the value of the expansion at $a = b = c = d = 1$, namely $(1 + 1 + 1 + 1)^{10} = \mathbf{4^{10}}$.

The sum is $\sum_{k \text{ odd}} k\binom{n}{k}$. Using the absorption identity $k\binom{n}{k} = n\binom{n - 1}{k - 1}$, $$\sum_{k \text{ odd}} k\binom{n}{k} = n \sum_{k \text{ odd}} \binom{n - 1}{k - 1} = n \sum_{j \text{ even}} \binom{n - 1}{j}.$$ The even-indexed binomial coefficients of any positive integer $m$ sum to $2^{m - 1}$; with $m = n - 1$ this gives $\mathbf{n \cdot 2^{n-2}}$.

Alternative proof. Let $S_{\text{odd}} = \sum_{k \text{ odd}} k\binom{n}{k}$ and $S_{\text{even}} = \sum_{k \text{ even}} k\binom{n}{k}$. From the earlier identity $\sum_{k} k\binom{n}{k} = n \cdot 2^{n-1}$, $$S_{\text{odd}} + S_{\text{even}} = n \cdot 2^{n-1}.$$ For the difference, use $k\binom{n}{k} = n\binom{n - 1}{k - 1}$: $$S_{\text{even}} - S_{\text{odd}} = \sum_{k} (-1)^k\, k\binom{n}{k} = n \sum_{k} (-1)^k \binom{n - 1}{k - 1} = -n\,(1 - 1)^{n-1} = 0$$ for $n \geq 2$. Hence $S_{\text{odd}} = S_{\text{even}}$, and adding the two relations gives $S_{\text{odd}} = n \cdot 2^{n-2}$.

Count the $(n + 1)$-element subsets of a set split into two parts $X$ and $Y$ of size $n$ each, of which there are $\binom{2n}{n + 1}$. Splitting by the number $k$ of elements taken from $X$: pick $k$ from $X$ in $\binom{n}{k}$ ways and the remaining $n + 1 - k$ from $Y$ in $\binom{n}{n + 1 - k} = \binom{n}{k - 1}$ ways. Summing over $k$ gives $$\sum_{k=1}^{n} \binom{n}{k}\binom{n}{k - 1} = \binom{2n}{n + 1}.$$

Both sides count the pairs $(A, B)$ with $A \subseteq B \subseteq \{1, \ldots, n\}$ and $|B| = m$.

Picking $A$ then $B$: choose $A$ of size $k$ in $\binom{n}{k}$ ways, then the remaining $m - k$ elements of $B$ from the $n - k$ elements outside $A$ in $\binom{n - k}{m - k}$ ways. Summing over $k = 0, \ldots, m$ gives the left-hand side.

Picking $B$ then $A$: choose the $m$-element set $B$ in $\binom{n}{m}$ ways, then any subset $A \subseteq B$ in $2^m$ ways, giving the right-hand side.

Split the sum with $k^2 = k(k - 1) + k$: $$\sum_{k=1}^{n} k^2 = \sum_{k=1}^{n} k(k - 1) + \sum_{k=1}^{n} k.$$ Since $k(k - 1) = 2\binom{k}{2}$, the hockey-stick identity $\sum_{i=r}^{n} \binom{i}{r} = \binom{n + 1}{r + 1}$ gives $\sum_{k=1}^{n} k(k - 1) = 2\sum_{k=1}^{n} \binom{k}{2} = 2\binom{n + 1}{3}$, and $\sum_{k=1}^{n} k = \binom{n + 1}{2}$. Therefore $$\sum_{k=1}^{n} k^2 = 2\binom{n + 1}{3} + \binom{n + 1}{2} = \frac{n(n + 1)(2n + 1)}{6}.$$

Factor the denominator as $x^2 - 4x + 3 = (x - 1)(x - 3)$ and write $$\frac{2x - 1}{(x - 1)(x - 3)} = \frac{A}{x - 1} + \frac{B}{x - 3}, \qquad 2x - 1 = A(x - 3) + B(x - 1).$$ Setting $x = 1$ gives $1 = -2A$, so $A = -\frac{1}{2}$; setting $x = 3$ gives $5 = 2B$, so $B = \frac{5}{2}$. Therefore $$\frac{2x - 1}{x^2 - 4x + 3} = -\frac{1}{2(x - 1)} + \frac{5}{2(x - 3)}.$$

Write $n = (n+1) - 1$ in the numerator: $$\frac{n}{(n+1)(n+2)} = \frac{(n+1) - 1}{(n+1)(n+2)} = \frac{1}{n+2} - \frac{1}{(n+1)(n+2)}.$$ The second piece telescopes: $\dfrac{1}{(n+1)(n+2)} = \dfrac{1}{n+1} - \dfrac{1}{n+2}$, so $\displaystyle\sum_{n=1}^{\infty} \frac{1}{(n+1)(n+2)} = \frac{1}{2}$ converges. The first piece $\displaystyle\sum_{n=1}^{\infty} \frac{1}{n+2}$ is a tail of the harmonic series, which diverges. A convergent series minus a divergent one diverges, so the sum diverges.

Let $S = \displaystyle\sum_{n=1}^{\infty} \frac{2n}{3^{n+1}}$ and subtract a shifted copy: $$S = \frac{2}{3^2} + \frac{4}{3^3} + \frac{6}{3^4} + \cdots, \qquad \frac{S}{3} = \frac{2}{3^3} + \frac{4}{3^4} + \cdots.$$ Subtracting term by term, each numerator difference is $2$: $$S - \frac{S}{3} = \frac{2}{3^2} + \frac{2}{3^3} + \frac{2}{3^4} + \cdots = 2\sum_{k=2}^{\infty} \frac{1}{3^k} = 2 \cdot \frac{1/9}{1 - 1/3} = \frac{1}{3}.$$ Thus $\dfrac{2}{3}S = \dfrac{1}{3}$, giving $S = \dfrac{1}{2}$.

The powers of $i$ repeat with period $4$: $i^0 = 1$, $i^1 = i$, $i^2 = -1$, $i^3 = -i$. Group the terms into blocks of four starting at $k = 4m$. Using $i^{4m} = 1$, the block is $$(4m+1) + (4m+2)i - (4m+3) - (4m+4)i = -2 - 2i,$$ the same constant for every block. Since $n$ is a multiple of $4$, the terms $k = 0, \ldots, n-1$ form exactly $\frac{n}{4}$ complete blocks, leaving the final term $(n+1)i^n = n+1$. Therefore $$S = \frac{n}{4}(-2 - 2i) + (n+1) = \frac{(n+2) - ni}{2}.$$

Summing the recurrence from $1$ to $n-1$ telescopes: $$a_n = a_1 + \sum_{k=1}^{n-1} 2k = 2 + (n-1)n = n^2 - n + 2.$$ Hence $a_{100} = 100^2 - 100 + 2 = 9902$.

A purchase is determined by how many of each type we take: nonnegative integers $x_1, x_2, \ldots, x_r$ with $$x_1 + x_2 + \cdots + x_r = n.$$ Encode such a solution as a row of $n$ stars and $r - 1$ bars: the stars before the first bar give $x_1$, those between the first and second bar give $x_2$, and so on. Every arrangement of $n$ stars and $r - 1$ bars corresponds to exactly one solution and vice versa. There are $n + r - 1$ symbols, and a purchase is fixed by choosing which $r - 1$ of them are bars, so the number of ways is $$\binom{n + r - 1}{r - 1} = \binom{n + r - 1}{n}.$$

Represent a solution by $n$ stars split into $r$ groups by $r - 1$ bars, where the number of stars in the $i$-th group is $x_i$: $$\underbrace{\star\cdots\star}_{x_1}\;\big|\;\underbrace{\star\cdots\star}_{x_2}\;\big|\;\cdots\;\big|\;\underbrace{\star\cdots\star}_{x_r}.$$ Each arrangement of the $n + r - 1$ symbols gives exactly one solution, so the count is the number of ways to place the $r - 1$ bars among the $n + r - 1$ positions: $$\binom{n + r - 1}{r - 1} = \binom{n + r - 1}{n}.$$

The slack variable $x_4 = 50 - (x_1 + x_2 + x_3)$ is a nonnegative integer exactly when the inequality holds, so solutions correspond to those of $x_1 + x_2 + x_3 + x_4 = 50$. By stars and bars with $n = 50$, $r = 4$, $$\binom{53}{3}.$$

First choose the $5$ occupied chairs so that no two are adjacent, then seat the $5$ distinct people in them. Line up the $15$ empty chairs; they create $16$ gaps (one before each empty chair, one after the last) into which the occupied chairs may be inserted. Choosing $5$ of these gaps, at most one per gap, guarantees no two occupied chairs are adjacent, so there are $\binom{16}{5}$ valid sets of chairs. The $5$ people can then be arranged in $5!$ ways, giving $$\binom{16}{5}\cdot 5!.$$

The squares occupy $3$ distinct rows and $3$ distinct columns. Choose the rows in $\binom{5}{3}$ ways, the columns in $\binom{5}{3}$ ways, then pair them up in $3!$ ways: $$\binom{5}{3}^{2}\cdot 3!.$$

Alternative solution. Place the squares in order: $25$ choices for the first, $16$ for the second (a $4 \times 4$ subgrid remains), $9$ for the third, then divide by $3!$ since the squares are unordered, giving $\frac{25 \cdot 16 \cdot 9}{3!}$.

Count the complement by inclusion-exclusion, using $\lfloor 1000/d \rfloor$ for the multiples of $d$. The number divisible by at least one of $2, 3, 5$ is $$(500 + 333 + 200) - (166 + 100 + 66) + 33 = 734,$$ so the answer is $1000 - 734 = 266$.

Since $n(S) = 2^{|S|}$, the hypothesis reads $2^{101} + 2^{|C|} = 2^{|A \cup B \cup C|}$. A sum of two powers of $2$ is a power of $2$ only when the two are equal, forcing $|C| = 101$ and $|A \cup B \cup C| = 102$. Writing $t = |A \cap B \cap C|$, inclusion-exclusion gives $$102 = 301 - \big(|A \cap B| + |A \cap C| + |B \cap C|\big) + t.$$ All three sets lie in the $102$-element union, so $|X \cap Y| \ge |X| + |Y| - 102$, making the pairwise sum at least $98 + 99 + 99 = 296$ and hence $t \ge 97$. Taking $U = \{1, \ldots, 102\}$ with $A = U \setminus \{1,2\}$, $B = U \setminus \{3,4\}$, $C = U \setminus \{102\}$ attains it, so the minimum is $97$.

Setting $y_i = x_i - 1$ makes the $y_i$ nonnegative with $y_1 + \cdots + y_8 = 11$, so stars and bars with $n = 11$, $r = 8$ gives $$\binom{18}{7}.$$

Alternative solution. Lay out $19$ stars and split them into $8$ nonempty groups by placing $7$ bars in the $18$ gaps between consecutive stars, at most one per gap.

For the lower bound, restrict to walks that only ever step right or up. Along such a walk the sum $x + y$ of the coordinates increases by $1$ at each step, so all $n + 1$ visited points are distinct and the walk is self-avoiding; the $2^n$ step sequences give $2^n$ distinct walks. For the upper bound, the first step has $4$ choices, and every later step must avoid reversing its predecessor, which would return the walk to the point two steps back, leaving at most $3$ choices.

The leading digit of a $2n$-digit number is $1$, so the remaining $2n - 1$ digits carry $n - 1$ ones and $n$ zeros. Sum by place value rather than by number. The leading place, worth $2^{2n-1}$, holds a $1$ in every one of the $\binom{2n-1}{n-1}$ such numbers. A lower place $2^k$ with $0 \le k \le 2n-2$ holds a $1$ in $\binom{2n-2}{n-2}$ of them, since fixing that digit and the leading digit to $1$ leaves $n - 2$ ones to distribute among the other $2n - 2$ places. As $\sum_{k=0}^{2n-2} 2^k = 2^{2n-1} - 1$, the total is $$\binom{2n-1}{n-1}2^{2n-1} + \binom{2n-2}{n-2}\left(2^{2n-1} - 1\right),$$ where the second binomial is $0$ when $n = 1$.

The pair is a point $(x, y)$ distributed uniformly over the square $[0, 10]^2$, so the probability is a ratio of areas. The complementary event $|x - y| \gt 5$ is the union of the two corner triangles above $y = x + 5$ and below $y = x - 5$, each a right triangle with legs $5$, of combined area $25$. Hence the probability is $$1 - \frac{25}{100} = \frac{3}{4}.$$

Your initial guess is correct with probability $\frac{1}{3}$, and the host's move cannot change that number: whatever door you point at, he is able to open an empty one, so seeing him do it tells you nothing about your own door. Its probability stays $\frac{1}{3}$, the prize is somewhere, and the only other closed door absorbs the rest, so switching wins with probability $\frac{2}{3}$, twice as often as staying.

With $1000$ doors the same argument gives $\frac{1}{1000}$ for your door against $\frac{999}{1000}$ for the survivor, and at that scale the mechanism is hard to miss: you were almost certainly wrong at the start, and the host, forbidden from opening the prize door, has swept that entire $\frac{999}{1000}$ onto a single door.

Let $W$ be the event that the drawn ball is white. Drawing from $X$ gives white with probability $\frac{5}{7}$ and from $Y$ with probability $\frac{3}{8}$, and the two boxes are equally likely, so those equal priors cancel in Bayes' theorem: $$P(X \mid W) = \frac{\frac{5}{7}}{\frac{5}{7} + \frac{3}{8}} = \frac{40}{61}.$$

A team ends the series at game $6$ precisely when it takes game $6$ and exactly $3$ of the first $5$, since winning $4$ of the first $5$ would have ended the series earlier. That leaves $\binom{5}{3}$ sequences for a given team, each of probability $2^{-6}$, and the two teams cannot both win, so the events are disjoint: $$2\binom{5}{3}\frac{1}{2^{6}} = \frac{5}{16}.$$

Conditioning on all three rolls exceeding $3$ leaves each one uniform on $\{4, 5, 6\}$ and still independent of the others, so the $3^3$ triples are equally likely. Three of them are constant, giving $$\frac{3}{27} = \frac{1}{9}.$$

Alternative solution. Let $E$ be the event that the three rolls are equal and $F$ the event that all three exceed $3$. Then $E \cap F$ consists of the three outcomes $444$, $555$, $666$ among the $6^3$ equally likely triples, while $F$ has probability $\left(\frac{1}{2}\right)^3$, so $$P(E \mid F) = \frac{P(E \cap F)}{P(F)} = \frac{3/216}{1/8} = \frac{1}{9}.$$

Work with the complementary event, that no two girls are adjacent. Number the seats $1$ through $10$ around the table; only which of them hold girls matters, and the $\binom{10}{5} = 252$ such choices are equally likely. Five pairwise non-adjacent seats in a circle of $10$ must be every other seat, leaving just two possibilities, the odd-numbered seats and the even-numbered ones. Hence the answer is $$1 - \frac{2}{252} = \frac{125}{126}.$$

Alternative solution. Treat the students as distinct, so that identifying rotations leaves $9!$ circular orderings. To keep the girls apart, seat the $5$ boys first, in $4!$ circular orders, then place the girls one per gap into the $5$ gaps they create, in $5!$ ways. This gives $$1 - \frac{4!\,5!}{9!} = \frac{125}{126}.$$

Let $R$ be the event that it is raining and $Y$ the event that all three answer yes. If it is raining, a person answers yes exactly when truthful, so $P(Y \mid R) = \left(\frac{4}{5}\right)^3$; if it is not, a person answers yes exactly when lying, giving $\left(\frac{1}{5}\right)^3$. The two prior probabilities are equal, so they cancel in Bayes' theorem: $$P(R \mid Y) = \frac{\left(\frac{4}{5}\right)^3}{\left(\frac{4}{5}\right)^3 + \left(\frac{1}{5}\right)^3} = \frac{64}{65}.$$

Write $v_p(n)$ for the exponent of the prime $p$ in $n$, so that $n$ is a perfect square precisely when $v_p(n)$ is even for every $p$. Fix a prime $p$. Since $ab$ is a square, $v_p(a) + v_p(b) = v_p(ab)$ is even. Coprimality forbids $p$ from dividing both $a$ and $b$, so one of $v_p(a)$, $v_p(b)$ is $0$ and the other equals that even sum, making both even. As $p$ was arbitrary, every prime occurs to an even power in $a$ and in $b$.

Reducing the coefficients modulo $24$ gives $1233 \equiv 9$, $45 \equiv 21$ and $9090 \equiv 18$, so the congruence becomes $$9x \equiv -3 \equiv 21 \pmod{24}.$$ Here $\gcd(9, 24) = 3$ divides $21$, so the congruence is solvable and dividing it through by $3$, modulus included, yields the equivalent $3x \equiv 7 \pmod 8$. Multiplying by $3$, which is its own inverse modulo $8$, gives $x \equiv 21 \equiv 5 \pmod 8$, that is $$x \equiv 5, \; 13, \; 21 \pmod{24}.$$

The divisors of $n$ are exactly the products $p_1^{b_1} \cdots p_k^{b_k}$ with $0 \le b_i \le a_i$, each arising from one choice of the exponents. Expanding the product below therefore produces every divisor exactly once, so the sum factors into geometric series: $$\sigma(n) = \prod_{i=1}^{k}\left(1 + p_i + p_i^2 + \cdots + p_i^{a_i}\right) = \prod_{i=1}^{k}\frac{p_i^{a_i + 1} - 1}{p_i - 1}.$$

Put $p = 2^{k+1} - 1$, so the number in question is $n = 2^k p$. Being prime, $p$ is not $1$, which rules out $k = 0$. So $k \ge 1$, and $p$ is odd, hence a prime different from $2$. This makes $2^k p$ the prime factorization of $n$, and the formula above gives $$\sigma(n) = \frac{2^{k+1} - 1}{2 - 1} \cdot \frac{p^2 - 1}{p - 1} = p(p + 1) = p \cdot 2^{k+1} = 2 \cdot 2^k p = 2n.$$

Consider the $p - 1$ numbers $a, 2a, \ldots, (p-1)a$ modulo $p$. None is divisible by $p$, since $p$ divides neither $a$ nor any of $1, \ldots, p-1$, and no two are congruent: $ia \equiv ja$ gives $p \mid a(i - j)$, hence $p \mid i - j$ and $i = j$. Being $p - 1$ distinct nonzero residues, they are a rearrangement of $1, 2, \ldots, p-1$, so multiplying them all together gives $$a^{p-1}(p-1)! \equiv (p-1)! \pmod p.$$ Finally $(p-1)!$ is a product of integers none of which $p$ divides, so it is coprime to $p$ and may be cancelled.

Consider the $p - 1$ powers $g, g^2, \ldots, g^{p-1}$. None is divisible by $p$, since $p \nmid g$. They are also pairwise incongruent: if $g^i \equiv g^j$ with $1 \le i \lt j \le p - 1$, then cancelling $g^i$, which is legitimate as $g$ is coprime to $p$, leaves $g^{j-i} \equiv 1$ with $0 \lt j - i \lt p - 1$, contradicting that the order of $g$ is $p - 1$. So the powers occupy $p - 1$ distinct classes among the $p - 1$ nonzero classes modulo $p$, which forces them to occupy all of them.

First observe that $g^m \equiv 1$ holds precisely when $(p-1) \mid m$: writing $m = q(p-1) + r$ with $0 \le r \lt p - 1$ leaves $g^r \equiv 1$, and the minimality in the definition of the order forces $r = 0$. Now take $h = g^{(p-1)/d}$, which makes sense since $d$ divides $p - 1$. Then $h^d = g^{p-1} \equiv 1$, so $h$ has some order at most $d$, and if $h^e \equiv 1$ then $g^{e(p-1)/d} \equiv 1$, so the observation gives $(p-1) \mid e(p-1)/d$, that is $d \mid e$. The smallest positive $e$ with $h^e \equiv 1$ is therefore $d$ itself.

For $p = 2$ the claim reads $1 \equiv -1$, which holds, so take $p$ odd. Every $a$ in $\{1, \ldots, p-1\}$ has an inverse there, since Fermat's little theorem gives $a \cdot a^{p-2} \equiv 1$. Such an $a$ is its own inverse exactly when $a^2 \equiv 1$, that is when $p \mid (a-1)(a+1)$, which for prime $p$ leaves only $a = 1$ and $a = p - 1$. The other $p - 3$ elements therefore fall into pairs $\{a, a^{-1}\}$ of distinct elements, each pair contributing a factor $1$ to the product, so $$(p-1)! \equiv 1 \cdot (p-1) \equiv -1 \pmod p.$$

Factor $p^2 - 1 = (p-1)(p+1)$. Being a prime above $3$, $p$ is odd, so $p - 1$ and $p + 1$ are consecutive even numbers and one of the two is divisible by $4$, making their product divisible by $8$. Again because $p$ is a prime above $3$, it is not divisible by $3$, yet exactly one of the three consecutive integers $p - 1$, $p$, $p + 1$ must be, so $3$ divides $(p-1)(p+1)$ as well. Since $8$ and $3$ are coprime, their product $24$ divides $p^2 - 1$.

Taking $n = 2$ gives $2^5 - 2 = 30$, so any integer dividing them all divides $30$. Conversely $30$ always works. Fermat's little theorem in the form $n^q \equiv n \pmod q$, valid for every integer $n$ since the case $q \mid n$ is immediate, gives $n^5 \equiv n \pmod 5$ at once; modulo $3$ it gives $n^3 \equiv n$, so $n^5 = n^2 n^3 \equiv n^3 \equiv n$; and modulo $2$ it gives $n^2 \equiv n$, so $n^5 \equiv n$ likewise. Thus $2$, $3$ and $5$ each divide $n^5 - n$, and as distinct primes so does their product. The answer is $30$.

Alternative solution. Fermat can be avoided by factoring further, $n^5 - n = (n-1)\,n\,(n+1)\,(n^2+1)$. The first three factors are consecutive integers, so one is even and one is a multiple of $3$, giving $6$. For the factor $5$, argue on $n$ modulo $5$: if $n \equiv 0$ or $\pm 1$ then one of $n - 1$, $n$, $n + 1$ is divisible by $5$, while if $n \equiv \pm 2$ then $n^2 \equiv 4$ and $5$ divides $n^2 + 1$.

The last digit is the residue modulo $10$, where the powers of $7$ repeat with period $4$, running $7, 9, 3, 1$. So only the exponent $7^7$ modulo $4$ matters, and there $7 \equiv -1$, giving $7^7 \equiv (-1)^7 \equiv 3 \pmod 4$. The last digit is thus the same as that of $7^3 = 343$, namely $3$.

None. Such an $m$ is $n! + k$ for some $k$ with $2 \le k \le n$, and this $k$ is one of the factors making up $n!$, so $k$ divides $n!$ and therefore divides $n! + k$ as well. Since $n! + k$ is strictly larger than $k$, which is itself larger than $1$, this makes $n! + k$ a proper multiple of $k$, hence composite. Letting $n$ grow, this produces runs of consecutive composite numbers of any desired length.

Both $p$ and $p + 2$ are primes larger than $3$, so both are odd and neither is divisible by $3$. Since $p$ is odd, $p + 1$ is even. Exactly one of the three consecutive integers $p$, $p + 1$, $p + 2$ is a multiple of $3$, and it is neither $p$ nor $p + 2$, so it has to be $p + 1$. As $2$ and $3$ are coprime, their product divides $p + 1$.

Alternative solution. A prime larger than $3$ must be congruent to $1$ or $5$ modulo $6$, the classes $0$, $2$, $4$ being even and the class $3$ divisible by $3$. Were $p \equiv 1$, then $p + 2 \equiv 3 \pmod 6$ would be divisible by $3$ and could not be prime. So $p \equiv 5$, which is exactly $p + 1 \equiv 0 \pmod 6$.

A run of $k$ consecutive integers starting at $a$ sums to $ka + \frac{k(k-1)}{2}$, so writing $n$ this way with $k \ge 2$ and $a \ge 1$ is the same as factoring $$2n = k\,(2a + k - 1).$$ The two factors differ by $2a - 1$, which is odd and positive, so exactly one of them is odd and the second is the larger. If $n = 2^m$, then $2n$ has no odd divisor beyond $1$, forcing the odd factor to be $1$; it cannot be the larger one, so it would have to be $k$, contradicting $k \ge 2$. If instead $n$ is not a power of $2$, write $n = 2^m q$ with $q \ge 3$ odd, so that $2n = 2^{m+1} q$ is a product of an even and an odd factor, each at least $2$. Let $k$ be the smaller of the two and $l$ the larger, and put $a = \frac{l - k + 1}{2}$, a positive integer because $l - k$ is odd and positive. Then $2a + k - 1 = l$, so $k(2a + k - 1) = 2n$ and the run works.

Induct on the number of edges. With $E = 0$, connectedness leaves $G$ a single vertex and the plane uncut, so $V - E + F = 1 - 0 + 1 = 2$. For $E \ge 1$ there are two cases, and each deletes one edge while keeping the drawing connected and free of crossings, so the induction hypothesis applies to what is left.

Suppose first that some edge $e$ lies on a cycle. That cycle is a closed curve, so $e$ has a different face on either side of it. Deleting $e$ merges the two into a single face and leaves $G$ connected, the rest of the cycle still joining the endpoints of $e$. So $V$ stays put while $E$ and $F$ each fall by $1$, and $V - E + F$ is unchanged.

Suppose instead that no edge lies on a cycle, and take a path in $G$ of greatest length. Its last vertex $v$ meets only one edge, since a second one would either lengthen the path or close a cycle. Deleting $v$ along with that edge leaves $G$ connected, and leaves the faces alone, an edge with a free end enclosing nothing. So $V$ and $E$ each fall by $1$ while $F$ stays put, and again $V - E + F$ is unchanged.

Count the pairs made of a face and an edge on its boundary, an edge that borders the same face on both sides being counted twice. Each edge has two sides and so occurs in exactly $2$ pairs, giving $2E$ in total. Each face contributes at least $3$, since with at least $3$ vertices, no loops and no multiple edges the boundary of a region cannot be closed up in fewer than $3$ steps. Comparing the two counts gives $3F \le 2E$.

Fix a drawing without crossings and let $F$ be its number of faces. Euler's formula rearranges to $F = E - V + 2$, while the previous exercise gives $F \le \frac{2}{3}E$. Putting the two together, $$E - V + 2 \le \tfrac{2}{3}E, \qquad \text{so} \qquad \tfrac{1}{3}E \le V - 2,$$ which is the claim.

$K_5$ is connected, has more than $3$ vertices and has neither loops nor multiple edges, so were it planar the previous exercise would apply. But its $V = 5$ vertices and $E = \binom{5}{2} = 10$ edges give $$3V - 6 = 9 \lt 10 = E,$$ contradicting that bound. No crossing-free drawing of $K_5$ exists.

It has $n - 1$, by induction on $n$. A tree with a single vertex has no edge. For $n \ge 2$, take a path of greatest length in the tree; its last vertex meets exactly one edge, since a second one would either lengthen the path or close a cycle. Removing that vertex together with its edge leaves a graph still connected and still without cycles, so a tree on $n - 1$ vertices, which by induction has $n - 2$ edges. Restoring the vertex gives $n - 1$.

A bipartite graph has no cycle of odd length, since travelling along a cycle alternates between the two groups and returning to the starting vertex takes an even number of steps. Its shortest cycle therefore has length at least $4$, so in a crossing-free drawing the boundary of a face closes up only after at least $4$ steps. Counting pairs of a face and an edge on its boundary as before, each edge still contributing $2$, this gives $4F \le 2E$, that is $F \le \frac{E}{2}$. Euler's formula rearranges to $F = E - V + 2$, so $$E - V + 2 \le \tfrac{1}{2}E, \qquad \text{so} \qquad \tfrac{1}{2}E \le V - 2,$$ which is the claim.

$K_{s,t}$ is connected and bipartite with no multiple edges, and it has $V = s + t \ge 6$ vertices and $E = st$ edges. Were it planar, the previous exercise would give $E \le 2V - 4$. But $$E - (2V - 4) = st - 2(s + t) + 4 = (s - 2)(t - 2) \ge 1,$$ because $s$ and $t$ are both at least $3$. So $E$ exceeds $2V - 4$ and no crossing-free drawing exists.

A drawing suffices. Put the two vertices of the first group at $(0, 1)$ and $(0, -1)$, put the $t$ vertices of the second group at $(1, 0), (2, 0), \ldots, (t, 0)$, and draw every edge as a straight segment. The segments leaving $(0,1)$ head in pairwise distinct directions, so they meet only at that vertex, and the same holds for those leaving $(0,-1)$. A segment of the first kind stays in the half plane $y \ge 0$ and reaches $y = 0$ only at its endpoint on the axis, while a segment of the second kind stays in $y \le 0$ and likewise, so the two kinds can meet only at a shared endpoint. No two edges cross.

The bound is $E \le \frac{g}{g-2}(V-2)$. Note first that $g \ge 3$ on its own rules out loops and multiple edges, which would be cycles of length $1$ and $2$. In a crossing-free drawing the boundary of a face closes up only after at least $g$ steps, while each edge contributes $2$ to the count of pairs of a face and an edge on its boundary, so $gF \le 2E$, that is $F \le \frac{2E}{g}$. Euler's formula rearranges to $F = E - V + 2$, whence $$E - V + 2 \le \frac{2E}{g}, \qquad \text{so} \qquad E\left(1 - \frac{2}{g}\right) \le V - 2.$$ Multiplying by $\frac{g}{g-2}$, which is positive because $g \ge 3$, gives the bound. Setting $g = 3$ and $g = 4$ returns $E \le 3V - 6$ and $E \le 2V - 4$.

Count in two ways the pairs made of an edge and one of its two ends. Every edge has exactly two ends and so supplies exactly two pairs, giving $2E$ in total. Grouping the same pairs by vertex instead, a vertex $v$ belongs to exactly $\deg(v)$ of them, a loop at $v$ supplying two of its ends and being counted twice, which is precisely the convention above. The two counts agree.

Write $V$ for the number of vertices and $d$ for the common degree. The previous exercise gives $Vd = 2 \cdot 20 = 40$, so $V$ divides $40$ and $d = 40/V$. Having no loops and no multiple edges caps a degree at $V - 1$, so $40/V \le V - 1$, that is $40 \le V(V-1)$, which forces $V \ge 7$. The divisors of $40$ that are at least $7$ are $8$, $10$, $20$ and $40$, with $d = 5, 4, 2, 1$ respectively, and each is realised: delete an $8$-cycle from $K_8$; join every vertex of a $10$-cycle to the two vertices two steps away; take a $20$-cycle; take $20$ disjoint edges.

Send each player to the pair of teams they belong to, which is well defined because every player is on exactly two. The map is injective, as two players sent to the same pair would leave that pair with two common members. It is surjective, since any two teams share a member and that member, belonging to exactly two teams, belongs to those two. Players therefore correspond one to one with pairs of teams, so $$N = \binom{7}{2} = 21.$$

With no loops and no multiple edges, a graph on $V$ vertices has at most one edge per pair of vertices, hence at most $\binom{V}{2}$ edges. Now $\binom{10}{2} = 45$ falls short of $50$, so ten vertices cannot suffice, while $\binom{11}{2} = 55$, and deleting any $5$ edges from $K_{11}$ leaves a graph on eleven vertices with exactly $50$. The answer is $11$.

The bound $E \le 3V - 6$ proved above turns into $50 \le 3V - 6$, that is $V \ge \frac{56}{3}$, so at least $19$ vertices are needed. Nineteen suffice. Begin with a triangle, which has $V = 3$ and $E = 3 = 3V - 6$, and repeatedly drop a new vertex inside a triangular face, joining it to the three corners of that face: each step keeps the drawing planar while adding one vertex and three edges, so it preserves $E = 3V - 6$. After sixteen steps $V = 19$ and $E = 51$, and deleting a single edge leaves $50$. The answer is $19$.

Work inside a single connected component $H$, which is legitimate because a component carries all the edges at its own vertices, so degrees in $H$ agree with degrees in the whole graph. If $H$ has at most $2$ vertices, no degree there exceeds $1$ and there is nothing to prove. Otherwise suppose every vertex of $H$ had degree at least $6$. Summing over the $V$ vertices of $H$ and using $\sum_v \deg(v) = 2E$ gives $2E \ge 6V$, that is $E \ge 3V$, while $H$ is connected and planar with at least $3$ vertices and so satisfies $E \le 3V - 6$. These cannot both hold.

Every vertex having degree $4$, the identity $\sum_v \deg(v) = 2E$ gives $4V = 2E$, so $E = 2V$. Euler's formula then reads $V - 2V + 10 = 2$, leaving $V = 8$. Such a graph does exist: the square antiprism, two squares joined by a band of eight triangles, has $8$ vertices of degree $4$, $16$ edges and $10$ faces.

A function has an inverse exactly when it is a bijection. A function from $A$ to $A$ is built by choosing an image for each of the $13$ elements independently, giving $13^{13}$ of them, while a bijection amounts to listing the $13$ images in order with no repetition, giving $13!$. The fraction is $$\frac{13!}{13^{13}}.$$

Write the original population as $a^2$. The two conditions say $a^2 + 100 = b^2 + 1$ and $a^2 + 200 = c^2$, that is $$b^2 - a^2 = 99, \qquad c^2 - a^2 = 200.$$ In the second, $(c-a)(c+a) = 200$ has two factors of equal parity, necessarily both even since their product is; writing $c - a = 2m$ and $c + a = 2n$ turns it into $mn = 50$ with $a = n - m$. The factorizations $50 = 1 \cdot 50 = 2 \cdot 25 = 5 \cdot 10$ therefore leave $a = 49$, $23$ or $5$. Only the first also satisfies $b^2 = a^2 + 99$, since $49^2 + 99 = 2500 = 50^2$ while $23^2 + 99 = 628$ and $5^2 + 99 = 124$ are not squares. The population was $49^2 = 2401$.