Putnam 2017

Key idea: the two rules together let you add $5$, so everything reduces to residues mod $5$; the multiples of $5$ and the number $1$ can never be reached.

What is excluded. Let $T$ be the set of positive integers that are not multiples of $5$, with $1$ removed. Then $2\in T$. If $n^2\in T$ then $n\in T$: $n$ is not a multiple of $5$, and $n\ne1$ because $1^2=1\notin T$. If $n\in T$ then $(n+5)^2\in T$: it is not a multiple of $5$, and it exceeds $1$. So $T$ obeys all three rules. Since $S$ is the smallest such set, $S\subseteq T$, and none of $1,5,10,15,\dots$ is in $S$.

Everything else is included.

Adding $5$. If $n\in S$ then $(n+5)^2\in S$, and so $n+5\in S$ by the square-root rule. So $S$ is closed under adding $5$.

A large number $\equiv1 \pmod 5$. From $2$ we get $49\in S$. From $49$ we get $54^2=2916\in S$, and $2916\equiv1\pmod5$. By adding $5$ repeatedly, every integer $N\ge2916$ with $N\equiv1\pmod5$ lies in $S$.

Back down by square roots. Let $n\ge2$ with $5\nmid n$. By Fermat’s little theorem $n^4\equiv1\pmod5$, so $n^{2^j}\equiv1\pmod5$ for all $j\ge2$. Choose $j\ge2$ with $n^{2^j}\ge2916$. Then $n^{2^j}\in S$, and taking square roots $j$ times shows $n\in S$.

So the integers not in $S$ are exactly $1$ and the multiples of $5$.

Key idea: the polynomials follow the linear rule $P_n=xP_{n-1}-P_{n-2}$, and a conserved quantity shows that this linear sequence also obeys the given rule.

Define integer polynomials by $P_0=1$, $P_1=x$, and $P_n=xP_{n-1}-P_{n-2}$ for $n\ge2$. We show $Q_n=P_n$ for all $n$, which proves the claim.

A conserved quantity. Let $D_n=P_n^2-P_{n+1}P_{n-1}$ for $n\ge1$. Using $P_{n+1}=xP_n-P_{n-1}$, $$D_n=P_n^2-xP_nP_{n-1}+P_{n-1}^2=P_n\,(P_n-xP_{n-1})+P_{n-1}^2=-P_nP_{n-2}+P_{n-1}^2=D_{n-1}.$$ And $D_1=x^2-(x^2-1)\cdot1=1$. So $D_n=1$ for all $n\ge1$, which says $$P_{n-1}^2-1=P_nP_{n-2}\qquad(n\ge2).$$

Induction. $Q_0=P_0$ and $Q_1=P_1$. Suppose $Q_{n-1}=P_{n-1}$ and $Q_{n-2}=P_{n-2}$. Then $$Q_n=\frac{P_{n-1}^2-1}{P_{n-2}}=\frac{P_nP_{n-2}}{P_{n-2}}=P_n ,$$ as rational functions. $P_{n-2}$ is not the zero polynomial, since its leading term is $x^{n-2}$ by induction. So every $Q_n$ is the integer polynomial $P_n$.

Key idea: with $r=f/g$, the difference $I_{n+1}-I_n$ becomes an integral of $g\,(r^{n+1}-1)(r-1)$, which is never negative.

Let $r=f/g$, a positive continuous function on $[a,b]$. Then $I_n=\int_a^b g\,r^{n+1}$, and the hypothesis $\int f=\int g$ reads $\int_a^b g\,(r-1)=0$.

Increasing. We have $$I_{n+1}-I_n=\int_a^b g\,r^{n+1}(r-1)=\int_a^b g\,(r^{n+1}-1)(r-1),$$ where we subtracted $\int g\,(r-1)=0$. For a positive number $r$, the factors $r^{n+1}-1$ and $r-1$ have the same sign, so the integrand is $\ge0$. Since $f\ne g$, $r\ne1$ at some point, and by continuity on a whole interval, where the integrand is strictly positive. Hence $I_{n+1}>I_n$.

Unbounded. Since $\int g(r-1)=0$ and $r-1$ is not identically zero, $r-1$ must be positive somewhere. By continuity there are $\delta>0$ and an interval $[c,d]$ with $r\ge1+\delta$ on it. Let $m=\min g>0$. Then $$I_n\ \ge\ \int_c^d g\,r^{n+1}\ \ge\ m\,(d-c)\,(1+\delta)^{n+1}\ \longrightarrow\ \infty .$$

Key idea: start from the weakest half and raise its total by exactly one point per swap; because every score from $0$ to $10$ occurs, such a swap is always available until the target is reached.

The total is $T=7.4\cdot2N=\frac{74N}{5}$. It is an integer and $\gcd(74,5)=1$, so $5\mid N$ and the target $T/2=\frac{37N}{5}$ is an integer. A group of $N$ students with sum $T/2$ has average $7.4$, and so does the other group. So we need a group of $N$ students with sum exactly $T/2$.

Start with a group $X$ made of $N$ students with the lowest scores. Its sum is at most $T/2$.

Claim. If $X$ has $N$ students and sum $<T/2$, then some $x\in X$ and some $y\notin X$ have $\operatorname{score}(y)=\operatorname{score}(x)+1$.

Suppose not. Let $v$ be the lowest score in $X$. Then no student outside $X$ scores $v+1$. So every student scoring $v+1$ is in $X$, and there is at least one, since every score occurs (when $v<10$). Applying the same reasoning to $v+1$, all students scoring $v+2$ are in $X$, and so on up to $10$. So every student outside $X$ scores at most $v$, and every student in $X$ scores at least $v$. Both groups have $N$ students, so the sum of $X$ is at least the sum of the rest, i.e. at least $T/2$. That is a contradiction.

So while the sum is below $T/2$, swapping such $x$ and $y$ keeps the group size at $N$ and raises the sum by exactly $1$. Repeating, the sum reaches $T/2$ exactly.

Key idea: the number of draws has generating function $\prod_{m=1}^n\frac{x+m-1}{m}$. Each player’s chance is controlled by the angle of this product at a cube root of unity, and that angle grows slowly without bound.

Generating function. Let $K$ be the number of draws with $n$ cards, and $E_n(x)=\mathbb E[x^K]$, with $E_0=1$. The first card is uniform on $1,\dots,n$; if it is $j$, the game goes on with the deck $1,\dots,j-1$ (and ends if $j=1$). So $$E_n(x)=\frac{x}{n}\sum_{j=1}^{n}E_{j-1}(x).$$ Subtracting the same relation for $n-1$ gives $nE_n-(n-1)E_{n-1}=xE_{n-1}$, that is, $$E_n(x)=E_{n-1}(x)\,\frac{x+n-1}{n}=\prod_{m=1}^{n}\frac{x+m-1}{m}.$$

Who wins. A wins when $K\equiv1$, B when $K\equiv2$, and C when $K\equiv0 \pmod 3$. Let $\omega=e^{2\pi i/3}$. Filtering with roots of unity, and using $E_n(1)=1$ and $E_n(\bar\omega)=\overline{E_n(\omega)}$, $$P(K\equiv r)=\tfrac13\sum_{j=0}^{2}\omega^{-jr}E_n(\omega^j)=\tfrac13+\tfrac23\operatorname{Re}\big(\omega^{-r}E_n(\omega)\big).$$ Write $E_n(\omega)=R_ne^{i\theta_n}$ with $R_n>0$ (no factor vanishes). The three chances are $$\tfrac13+\tfrac23R_n\cos\big(\theta_n-\tfrac{2\pi r}{3}\big),\qquad r=1\ (\text{A}),\ r=2\ (\text{B}),\ r=0\ (\text{C}).$$ So the leader is the player whose direction $\frac{2\pi r}{3}$ is closest to $\theta_n$.

The angle wanders around. $\theta_n$ is the sum of the arguments of $\omega+m-1$ for $m=1,\dots,n$ (taken mod $2\pi$). For $m\ge2$, $\omega+m-1=(m-\tfrac32)+\tfrac{\sqrt3}{2}i$ has argument in $(0,\pi)$, roughly $\frac{\sqrt3}{2m}$ for large $m$. These steps are positive, tend to $0$, and have a divergent sum (like the harmonic series). So $\theta_n$ increases without bound, in smaller and smaller steps. It therefore passes within any small distance of $0$, $\frac{2\pi}3$ and $\frac{4\pi}{3}$ (mod $2\pi$) infinitely often. Whenever $\theta_n$ is within $\frac\pi3$ of a player’s direction, that player has the strictly highest chance. Hence each of A, B, C leads for arbitrarily large $n$.

Key idea: with colors in $\mathbb Z/3$, a face is good exactly when the sum of its three edge colors is nonzero. So we count solutions of a linear system over $\mathbb F_3$.

Translating the condition. Name the colors $0,1,2$. Three colors $a,b,c$ have $a+b+c\equiv0\pmod3$ exactly when they are all equal ($3a\equiv0$) or all different ($0+1+2=3$). If exactly two are equal, say $a,a,b$ with $b\ne a$, then $2a+b\equiv0$ would force $b\equiv a$. So a face is good exactly when its color sum is nonzero mod $3$.

A linear map. Let $L:\mathbb F_3^{30}\to\mathbb F_3^{20}$ send an edge coloring to the list of the $20$ face sums. We want the number of colorings $c$ with every coordinate of $L(c)$ nonzero.

$L$ is onto. If not, some nonzero vector $w\in\mathbb F_3^{20}$ (a weight on faces) is orthogonal to the image. That means: for each edge, the weights of its two faces add to $0$, i.e. $w_F=-w_{F'}$ for adjacent faces. Around any vertex of the icosahedron, five faces form a cycle of adjacent faces. Going once around, $w_F=(-1)^5w_F=-w_F$, so $2w_F=0$ and $w_F=0$ in $\mathbb F_3$. Every face touches a vertex, so $w=0$. This contradiction shows $L$ has rank $20$.

Counting. Since $L$ is onto, every target vector has exactly $3^{30-20}=3^{10}$ preimages. The targets with all $20$ coordinates nonzero number $2^{20}$. So the count is $$2^{20}\cdot3^{10}=61{,}917{,}364{,}224 .$$

Key idea: the points $A_2$ with $\overrightarrow{PA_2}=\lambda\overrightarrow{PA_1}$, $A_1\in L_1$, form the image of $L_1$ under a scaling about $P$, which is a line parallel to $L_1$.

For fixed $\lambda\ne0$ and $P$, let $h$ be the scaling with center $P$ and ratio $\lambda$. Then $A_2=h(A_1)$. So suitable points exist exactly when the line $h(L_1)$ meets $L_2$. A scaling sends a line to a parallel line (or the same line).

If $L_1$ and $L_2$ intersect. They are not parallel. Then $h(L_1)$, being parallel to $L_1$, is not parallel to $L_2$, so it meets $L_2$. The points exist for every $\lambda\ne0$ and every $P$.

If they do not intersect. They are distinct and parallel. Take $\lambda=1$ and any $P$ off both lines. Then $h$ is the identity, $h(L_1)=L_1$ does not meet $L_2$, and the condition fails.

So the condition holds for all $\lambda$ and $P$ exactly when the lines intersect.

Key idea: representations of $N$ as sums of consecutive positive integers correspond to odd divisors of $N$. Having only one nontrivial representation forces $N=2^e\cdot2017$.

The correspondence. $N=a+(a+1)+\dots+(a+k-1)$ with $a\ge1$ means $2N=k\,(2a+k-1)$. Here $k<2a+k-1$, and the two factors have opposite parity. Conversely, write $2N=uv$ with $u<v$ of opposite parity. Then $k=u$, $a=\frac{v-u+1}{2}$ gives a representation. Such factorizations match the odd divisors $d$ of $N$: put the odd part $d$ and the even part $2N/d$ in increasing order. The divisor $d=1$ gives $k=1$. So the number of representations with $k>1$ equals the number of odd divisors of $N$ minus one.

The condition. Only $k=2017$ works, so $N$ has exactly two odd divisors, $1$ and an odd prime $p$. So $N=2^e p$. That prime gives $k=\min(p,\,2^{e+1})$, which must equal $2017$. A power of $2$ is never $2017$, so $p=2017$ and $2^{e+1}>2017$, i.e. $e\ge10$.

The smallest $a$. With $k=2017$, $N=2017a+\frac{2017\cdot2016}{2}=2017(a+1008)$. So $a+1008=2^e$ with $e\ge10$. The smallest choice is $e=10$, giving $a=1024-1008=16$.

Key idea: a rational value at $\tfrac12$ makes the coefficients eventually periodic, so $f$ is a polynomial over $1-x^p$. A parity check at $x=\tfrac23$ then fails.

Suppose $f(\tfrac12)=\sum c_i2^{-i}$ is rational. This sum is a binary expansion. Every binary expansion of a rational number repeats from some point (dyadic rationals end in all $0$s or all $1$s). So there are $m\ge0$ and $p\ge1$ with $c_{i+p}=c_i$ for all $i\ge m$.

Then the coefficients of $(1-x^p)f(x)$ are $c_i-c_{i-p}$, which vanish for $i\ge m+p$. So $$(1-x^p)f(x)=A(x)=\sum_{i=0}^{D-1}a_ix^i,\qquad a_i\in\mathbb Z,\ D=m+p\ge p .$$ At $x=\frac23$ (inside the radius of convergence) this gives $A(\frac23)=\frac32\big(1-(\frac23)^p\big)$. Multiply by $2\cdot3^{D-1}$: $$2\sum_{i=0}^{D-1}a_i\,2^i\,3^{D-1-i}=3^{D}-2^p\,3^{D-p}.$$ All exponents are nonnegative because $D\ge p$. The left side is even. On the right, $3^D$ is odd and $2^p3^{D-p}$ is even, so the right side is odd. This contradiction shows $f(\frac12)$ is irrational.

Key idea: split the coefficient pattern into an alternating part and a part on even indices; most of it cancels and $\ln 2\cdot\ln2$ is left over.

The series is $\sum_{n\ge2}c_n\frac{\ln n}{n}$, where $c_n=3$ if $n\equiv2\pmod4$ and $c_n=-1$ otherwise. Check that $$c_n=(-1)^n-2\,[n\text{ even}]\,(-1)^{n/2}.$$ For $n$ odd this gives $-1$. For $n=2m$ it gives $1-2(-1)^m$: that is $3$ for odd $m$ ($n\equiv2$) and $-1$ for even $m$ ($n\equiv0$).

Take partial sums up to $n=4K+1$, which ends a block of the original series. Then $$\sum_{n=2}^{4K+1}c_n\frac{\ln n}{n}=\sum_{n=2}^{4K+1}(-1)^n\frac{\ln n}{n}-\sum_{m=1}^{2K}(-1)^m\frac{\ln(2m)}{m},$$ and the last sum equals $\ln2\sum_{m=1}^{2K}\frac{(-1)^m}{m}+\sum_{m=1}^{2K}(-1)^m\frac{\ln m}{m}$.

Each series $\sum(-1)^n\frac{\ln n}{n}$ and $\sum\frac{(-1)^m}{m}$ converges (alternating, with terms decreasing to $0$ from $n=3$ on). Call the first $L$. Letting $K\to\infty$, $$L-\big(\ln2\cdot(-\ln2)+L\big)=(\ln2)^2,$$ using $\sum_{m\ge1}\frac{(-1)^m}{m}=-\ln2$. The partial sums inside a block differ from these by terms tending to $0$, so the whole series converges to $(\ln2)^2$.

Key idea: both conditions turn into “$x+y$ and $xy$ are fixed” for the two cut lengths at a vertex, so the cuts come from the roots of one quadratic per vertex. Signs of that quadratic at the side lengths show that the vertices give $0$, $1$, and $0$, $1$ or $2$ lines. Exactly two lines means a double root, which becomes a Diophantine equation.

Let the side lengths be $a>b>c$, with opposite vertices $A,B,C$, and let $s=\frac{a+b+c}2$.

Step 1: the quadratic at a vertex. A line that splits the triangle into two regions meets the boundary in two points. So it cuts off a small triangle at one vertex $V$. (A line through a vertex is included, with one cut point at another vertex.) Let the two sides at $V$ have lengths $p,q$, the opposite side $r$, and let the cuts be at distances $x\in[0,p]$ and $y\in[0,q]$ from $V$.

• Equal areas: $\frac12xy\sin V=\frac12\cdot\frac12pq\sin V$, so $xy=\frac{pq}2$.
• Equal perimeters: the two boundaries share the cut segment, so $x+y=2s-(x+y)$, which gives $x+y=s$.

So $x,y$ are the two roots of $f(t)=t^2-st+\frac{pq}2$, in some order. A short computation gives $$f(p)=\frac{p(p-r)}2,\qquad f(q)=\frac{q(q-r)}2 .$$ Each root of $f$, placed on a side, gives a line, provided it is at most the length of the side it is placed on.

Step 2: vertex $A$ gives none. Here $\{p,q\}=\{b,c\}$ and $r=a$. Both $f(b)$ and $f(c)$ are negative, so the roots $u<v$ satisfy $u<c<b<v$. Whichever of $x,y$ equals $v$ is longer than its side. So there is no line.

Step 3: vertex $B$ gives exactly one. Here the sides are $a$ (for $x$) and $c$ (for $y$), and $r=b$. Now $f(c)<0<f(a)$, so the roots are real and $u<c<v<a$. The only valid choice is $y=u$, $x=v$, with both cut points strictly inside their sides. So there is exactly one line.

Step 4: vertex $C$ gives $0$, $1$ or $2$. Here the sides are $a$ and $b$, and $r=c$, so $f(a)>0$ and $f(b)>0$. There are three cases.

• If $f$ has no real roots, there is no line.
• Otherwise, $b$ lies outside $[u,v]$. If $b<u$, the root placed on side $b$ is too long, so there is no line.
• If $b>v$, then both roots are less than $b<a$, and both orders work. That gives two lines when $u\neq v$, and one line when $u=v$.

The case $b>v$ happens exactly when $b>\frac s2$, the midpoint of the roots. The cut points are then strictly inside sides $a$ and $b$.

Lines from different vertices meet different pairs of sides at interior points, so they are distinct. (A line meets the boundary only twice.) The total is therefore $1$, $2$ or $3$. It is exactly $2$ precisely when $f$ has a double root at $C$ and $b>\frac s2$: $$s^2=2ab\quad\text{and}\quad a+c<3b .$$

Step 5: the smallest integer case. Let $n=a+b+c$. Then $s^2=2ab$ means $n^2=8ab$, so $8\mid n^2$. That forces $4\mid n$, so write $n=4m$. Then $ab=2m^2$ and $c=4m-a-b$.

The triangle inequality $a<b+c$ becomes $a<2m$. Then $b=\frac{2m^2}{a}>m$, which also gives $a+c=4m-b<3b$. So we need a factorization $ab=2m^2$ with $m<b<a<2m$, plus the checks $c>0$ and $b>c$.

• $m\le5$: no such factorization. For $m=1,2$ there is no room. For $m=3$ the only candidate is $b=4$, and $4\nmid18$. For $m=4$, neither $5$ nor $6$ divides $32$. For $m=5$, none of $6,7,8$ divides $50$.
• $m=6$: $72=9\cdot8$ with $6<8<9<12$. Then $c=24-17=7$.
• $m\ge7$: $a>b>m$ forces $a\ge9$, with $a=9$ only for $m=7$, $b=8$. But $9\cdot8\ne98$.

So the least possible $a$ is $9$, and the triple is $(9,8,7)$. Check it: $9<8+7$, $s=12$, $s^2=144=2\cdot9\cdot8$, and $b=8>6=\frac s2$. The double root is $x=y=6$, cut from the vertex between the sides $9$ and $8$. Together with the line from Step 3, this triangle has exactly two lines.

Key idea: count with roots of unity. To handle the distinctness, expand over set partitions. The coefficients $1,1,2,\dots,63$ add up to exactly $2017$, so only the one-block partition survives.

Let $p=2017$. The numbers $1,\dots,2017$ form a full set of residues mod $p$, so we count injective maps $x:\{0,\dots,63\}\to\mathbb Z_p$ with $\sum c_ix_i\equiv0$, where $c=(1,1,2,3,\dots,63)$. Note $\sum c_i=1+\frac{63\cdot64}{2}=2017$.

Roots of unity. With $\zeta=e^{2\pi i/p}$, the count is $$N=\frac1p\sum_{t\in\mathbb Z_p}\ \sum_{x\ \text{injective}}\ \zeta^{\,t\sum_ic_ix_i}.$$ The $t=0$ term counts all injective maps: $\frac{p!}{(p-64)!}$.

Sums over injective maps. For any functions $g_i$, inclusion-exclusion over which coordinates coincide gives $$\sum_{x\ \text{injective}}\prod_i g_i(x_i)=\sum_{\pi}\mu(\pi)\prod_{B\in\pi}\Big(\sum_{y\in\mathbb Z_p}\prod_{i\in B}g_i(y)\Big).$$ Here $\pi$ runs over set partitions of the $64$ indices, each block $B$ means “all coordinates in $B$ are equal”, and $\mu(\pi)=\prod_{B}(-1)^{|B|-1}(|B|-1)!$. This is Möbius inversion on the lattice of set partitions.

Take $g_i(y)=\zeta^{tc_iy}$ with $t\ne0$. The inner sum is $\sum_y\zeta^{t(\sum_{i\in B}c_i)y}$, which is $p$ if $\sum_{i\in B}c_i\equiv0\pmod p$ and $0$ otherwise. Every $c_i$ lies between $1$ and $63$, and all of them add to $2017$. So a block sum is divisible by $2017$ only if the block is everything. Only the one-block partition survives, with $\mu=(-1)^{63}\,63!=-63!$. So each $t\ne0$ contributes $-63!\cdot p$.

Total. $$N=\frac1p\Big(\frac{p!}{(p-64)!}-(p-1)\cdot63!\cdot p\Big)=\frac{2016!}{1953!}-2016\cdot63!.$$