# Putnam Seminar

## Cody Johnson

Request a solution by email at ctj@math.cmu.edu. X

# 2006 B1

#### Problem

Show that the curve $x^3+3xy+y^3=1$ contains only one set of three distinct points, $A$, $B$, and $C$, which are vertices of an equilateral triangle, and find its area.

#### Discussion

A first idea is to try to visualize what this set should look like. The intuition is that curves of this form generally look something like this:

Obviously for a Putnam B1, they don't expect you to analyze curves this complex, so there is probably some convoluted identity behind this problem. We proceed with this in the back of our minds.

With that in mind, we start trying to manipulate. Seeing the $3xy$ term and also thinking about the similarly-looking equation $(x+y)^3=x^3+3x^2y+3xy^2+y^3$ we might want to complete the cube. We get $(x+y)^3=1+3x^2y+3xy^2-3xy=1+3xy(x+y-1)$ where we have grouped similar looking terms on the right-hand side. From here, seeing the lingering $1$ on the right-hand side, we think to subtract the $1$ to the other side because maybe it will factor. It turns out it does! We get $3xy(x+y-1)=(x+y)^3-1=(x+y-1)((x+y)^2+(x+y)+1)$ From here, we have $x+y-1=0\quad\text{or}\quad3xy=(x+y)^2+(x+y)+1$ But now what we have on the right is something we're happy about - a quadratic! We employ the quadratic formula to solve for $y$ in terms of $x$: $3xy=(x+y)^2+(x+y)+1\implies0=y^2+(1-x)y+(x^2+x+1)$ or $y=\frac{(x-1)\pm\sqrt{(1-x)^2-4(x^2+x+1)}}2=\frac{(x-1)\pm\sqrt{-3x^2-6x-1}}2=\frac{(x-1)\pm\sqrt{-3(x+1)^2}}2$ The only way we can get a real solution is if $x=-1$, because otherwise the thing under the square root would be negative! From $x=-1$, we get $y=-1$. Therefore, this curve consists of two parts: the set where $x+y=1$ or the point $(-1,-1)$:

Now we get to the geometry part of the problem. The three points can't all be part of the line. Therefore, one of the points is $(-1,-1)$. Also, the height of the equilateral triangle is the distance from the point $(-1,-1)$ to the line $x+y=1$. But we already know by symmetry that the altitude from $(-1,-1)$ to that line is the point $\left(\frac12,\frac12\right)$ (and the height of this altitude is $\sqrt{\left(\frac12-(-1)\right)^2+\left(\frac12-(-1)\right)^2}=\frac3{\sqrt2}$ Using $\tan30^\circ=\frac1{\sqrt3}$, we get that the other two points of the equilateral triangle are the two points at distance $\frac3{\sqrt6}$ away from $\left(\frac12,\frac12\right)$ on either side. Thus, the triangle is unique, and its area is $\frac12\cdot\text{base}\cdot\text{height}=\frac12\cdot\frac3{\sqrt2}\cdot\frac3{\sqrt6}=\boxed{\frac{3\sqrt3}4}$ With that, we have solved the problem.

# 2006 B2

#### Problem

Prove that, for every set $X=\{x_1,x_2,\dots,x_n\}$ of $n$ real numbers, there exists a non-empty subset $S$ of $X$ and an integer $m$ such that $\left\lvert m+\sum_{s\in S}s\right\rvert\le\frac1{n+1}$

#### Discussion

This is one of those problems where good training can really help you get an advantage. It reminds us of that one problem that appears on every introductory pigeonhole principle handout:

Problem: Prove that among any $n$ integers, there is some subset of them whose sum is divisible by $n$.

Solution: Let the integers be $a_1,\dots,a_n$. Consider sums of the form $a_1$, $a_1+a_2$, $\dots$, $a_1+\dots+a_n$ (let $s_k:=a_1+\dots+a_k$). If any of them is divisible by $n$, then we're already done. Otherwise, each of them leaves a remainder of either $1$, $2$, $\dots$, or $n-1$ when divided by $n$. Therefore, by pigeonhole principle, since there are $n$ sums and $n-1$ residues they can be, two of them have the same residue. Call these $s_i$ and $s_j$ for $i \lt j$. Subtracting them, we get that $s_j-s_i\equiv0\pmod n$. But $s_j-s_i=x_{i+1}+\dots+x_j$, and thus the subset $\{x_{i+1},\dots,x_j\}$ has sum divisible by $n$.

Another very relevant problem that appears in most pigeonhole handouts is:

Problem: Prove that for any irrational number $\alpha$ and any $n\in\mathbb N$, there are integers $p\in\mathbb Z$, $0\neq q\in\mathbb Z$ such that $\left\lvert p\alpha-q\right\rvert\lt\frac1n$.

Solution: Consider the numbers $\alpha,2\alpha,3\alpha,\dots$, and look at the fractional part of each of them. That is, look at the residue modulo $1$. For example, $3.14\equiv0.14\pmod1$. The holes will be the intervals $\left[0,\frac1n\right)$, $\left[\frac1n,\frac2n\right)$, $\left[\frac2n,\frac3n\right)$, $\dots$, $\left[\frac{n-1}n,1\right)$, and the pigeons will be the numbers $\alpha,2\alpha,\dots$. Since there are $n$ holes and $\infty\gt n$ pigeons, two of them lie in the same hole. That is, there are integers $0\lt a\lt b$ such that $a\alpha\pmod1$ and $b\alpha\pmod1$ lie in the same interval. But lying in the same hole implies that they differ by at most $\frac1n$. Therefore, $-\frac1n\lt(b-a)\alpha\pmod1\lt\frac1n$ Thus, $m\le\left\lvert(b-a)\alpha\right\rvert\lt m+\frac1n\implies\left\lvert(b-a)\alpha-m\right\rvert\lt\frac1n$ for some $m\in\mathbb Z$. Taking $p=b-a$ and $q=m$, we conclude.

With these two relevant problems in mind, we proceed to attempt the problem. We will consider the numbers $s_k:=x_1+\dots+x_k$ modulo $1$. All of these residues live within the interval $[0,1)$, which we break into the intervals $\left[0,\frac1{n+1}\right)$, $\left[\frac1{n+1},\frac2{n+1}\right)$, $\dots$, $\left[\frac{n}{n+1},1\right)$. The problem now is that we have only $n$ pigeons but $n+1$ holes! Now in lecture, I did something silly like throwing the numbers $0$ and $1$ into the set because I wanted to add pigeons, but instead I will do the smarter thing and remove holes: if any $s_i$ lives in $\left[0,\frac1{n+1}\right)$ or $\left[\frac{n}{n+1},1\right)$, then we're already done. We now only have $n$ holes, which means some two pigeons lie in the same hole (which means they differ by at most $\frac1{n+1}$. That is, there are $i\lt j$ such that $\left\lvert s_j-s_i\right\rvert\lt\frac1{n+1}\implies\left\lvert x_{i+1}+\dots+x_j\right\rvert\lt\frac1{n+1}$ so we can just take $S$ to be the set $\{i+1,\dots,j\}$. The problem is thus solved.

# 2006 B3

#### Problem

Let $S$ be a finite set of points in the plane. A linear partition of $S$ is an unordered pair $\{A,B\}$ of subsets of $S$ such that $A\cup B=S$, $A\cap B=\varnothing$, and $A$ and $B$ lie on opposite sides of some straight line disjoint from $S$ ($A$ or $B$ may be empty). Let $L_S$ be the number of linear partitions of $S$. For each positive integer $n$, find the maximum of $L_S$ over all sets $S$ of $n$ points.

#### Discussion

This problem can be solved by just playing with it, but I was equipped with one slightly suggestive problem that I had solved before:

Problem: Consider the set of points $\{(i,j):1\le i\le n\}$. What's the minimum number of lines we need to draw on the plane to divide the plane into regions in such a way that each region has at most one of these points?

Solution: First, we can guess that the solution will be around $2(n-1)$ since we can draw the lines $x=i+\frac12$ for each $1\le i\le n-1$ and $y=i+\frac12$ for each $1\le i\le n-1$, as illustrated:

But the clever way to prove the lower bound in this problem is by considering each of the $4(n-1)$ segments along the perimeter of the figure:

Since each of these segments must have some line going through it, and each line can go through at most $2$ segments, then there must be at least $2(n-1)$ lines.

Now we get back to the problem. The problem I just mentioned is just something to keep in the back of your head. Another thing you should think of is wanting to minimize the number of collinear points in the configuration of points. Upon drawing a regular $n$-gon for small values of $n$ and seeing how good they do, we can guess the pattern that each time we guess that $L_{\text{regular}~n\text{-gon}}=\binom{n}2+1$. But how can we prove such a bound? In fact, if we are bold enough, we can conjecture the following claim: for any set $S$ such that no three points in $S$ are collinear, there are exactly $\binom{n}2+1$ linear partitions.

The following idea is motivated by the fact that $\binom{n}2$ is the number of ways to choose pairs of points from these $n$ points, and the $+1$ corresponds to some trivial linear partition (for example, the partition of $S$ into $\{S,\varnothing\}$). We will try to find a bijection between the number of nontrivial linear partitions and the number of ways to choose two points. For each pair of points $\{X,Y\}$ such that $X,Y\in S$, we are going to draw a line $\ell$ through $X$ and $Y$ and then rotate it sliiiightly clockwise about the midpoint of $X$ and $Y$. How slightly though? Slightly enough so that it doesn't hit any other point in $S$ while we're rotating it. This is always possible because there is a finite number of points and an infinite number of small angles we can rotate it, which means one angle is small enough so that it doesn't hit any other ponit. Therefore, we can call $f(X,Y)$ to be the partition we get by this process. How do we know that $f$ is a bijection? That takes a little more proving.

First we show that $f$ is surjective (except for the trivial case). Given a linear partition of $S=A\sqcup B$ by $\ell$ such that $A,B\neq\varnothing$, we can slide $\ell$ in a parallel fashion until it hits some element of $X\in A$ (in the event that $\ell$ is hitting two elements $X_1,X_2\in A$ at this moment, choose the one that is counterclockwise along the convex hull of $A$. And if you want to be super pedantic, you should also address the case where the convex hull of $A$ only has two points on it, but I'm not going to do that). We will then traverse the convex hull of $A$ via the following process, which should look like a windmill: rotate $\ell$ counterclockwise about $X$ until $\ell$ hits another vertex $X'\in\mathcal{C}(A)$, then use $X'$ as the new pivot until $\ell$ hits yet another vertex in $\mathcal{C}(A)$, and so on. We stop at the first moment that $\ell$ hits an element of $Y\in\mathcal{C}(B)$. Since no three points are collinear in $S$, at this moment $\ell$ is passing through two unique points $X\in A$ and $Y\in B$. From here, it's not extremely hard to prove that $f(X,Y)=\{A,B\}$, it involves just noting something about the convex hull. I will elaborate if requested to do so.

Now to show that $f$ is injective, suppose $\{A,B\}=f(X_1,Y_1)=f(X_2,Y_2)$ for $X_1,X_2\in A$ and $Y_1,Y_2\in B$, where $(X_1,Y_1)\neq(X_2,Y_2)$. Really all you have to do now is just do some casework on how $\{X_1,X_2,Y_1,Y_2\}$ are configured.

Having proven this claim, it's not too hard to finish. We have to prove that $\binom{n}2+1$ is maximal. The idea now is to take a maximal configuration and modify the points just a tiny amount so that it does not decrease the number of linear partitions, but move them enough so that no three points in the resulting set are collinear. At this point the set will have $\binom{n}2+1$ lines, which means that would be the maximum. Now how do we do this? Take a configuration with a maximal number of linear partitions, and let $\{\ell_i\}_{i=1}^m$ be a set representatives from each of the $m$ partitions. For each point $X\in S$, each $\ell_i$ divides the plane into two regions, one of which contains $X$. Thus, let $R(X)$ be the intersection of all such regions. But each $R(X)$ is a convex polygon since it is the intersection of half-planes! Therefore, we can perform the following algorithm: let $S=\{X_1,\dots,X_n\}$, and for $i=3,4,\dots,n$, let $X_i'\in R(X_i)$ be such that $X_i'$ is not collinear with any of $X_1,X_2,X_3',X_4',\dots,X_{i-1}'$. Such a point exists since there are only a finite number of lines it can lie on but an infinite number of places in $R(X_i)$ to choose from. After the algorithm, we will have a new set $S'=\{X_1,X_2,X_3',\dots,X_n'\}$ such that each of the linear partitions of $S$ are also linear partitions of $S'$, but $S'$ has no three collinear points. Therefore, $m\le\binom{n}2+1$. With this, we have solved the problem.