2020 USAMO Problems/Problem 5

Problem

A finite set $S$ of points in the coordinate plane is called overdetermined if $|S| \ge 2$ and there exists a nonzero polynomial $P(t)$ , with real coefficients and of degree at most $|S| - 2$ , satisfying $P(x) = y$ for every point $(x, y) \in S$ .

For each integer $n \ge 2$ , find the largest integer $k$ (in terms of $n$ ) such that there exists a set of $n$ distinct points that is not overdetermined, but has $k$ overdetermined subsets.

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it.

2020 USAMO (Problems • Resources)
Preceded by Problem 4	Followed by Problem 6
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

The answer is $2^{n-1}-n$ . To construct this, have $n-1$ points on a horizontal line and $1$ point not on it. Then, any subset that does not include the last point is overdetermined.\\

For the bound, the main idea of the problem is the following claim.\\

Claim: If $S$ and $T$ are overdetermined subsets with $|S|=|T|=k$ but $S$ and $T$ only differ by one element (one is swapped out for another), then $S\cup T$ is overdetermined.\\

Consider the minimal polynomial of $S$ . It has degree at most $k-2$ since $S$ is overdetermined, and similarly with the minimal polynomial of $T$ . However, there is a unique polynomial of degree at most $k-2$ passing through $S\cap T$ since it has $k-1$ points. Thus, this unique polynomial also passes through $S$ and $T$ . Thus, this polynomial passes through all points of $S\cup T$ , as desired.\\

We now use this claim to inductively bound the number of overdetermined subsets with $k$ elements. Let $m_k$ denote the number of overdetermined subsets of size $k$ . Clearly, $m_n=0$ .\\

Claim 2: We have $m_k\leq \frac{m_{k+1}(k+1)+{n\choose k+1}-m_{k+1}}{n-k}.$ Proof: Each overdetermined subset of size $k+1$ can have up to $k+1$ overdetermined subsets of size $k$ , but by the previous claim each non-overdetermined subset of size $k+1$ , which there are ${n\choose k+1}-m_{k+1}$ of, can have at most one. Each subset of size $k$ feeds into $n-k$ subsets of size $k+1$ . Note that this is increasing in $m_{k+1}$ .\\

Claim 3: We have $m_k\leq {n-1\choose k}.$ Proof: Use induction. Note that the expression in Claim 2 is nondecreasing in $m_{k+1}$ , and verify that $\frac{{n-1\choose k+1}(k+1)+{n\choose k+1}-{n-1\choose k+1}}{n-k}={n-1\choose k}.$

Thus, we have that the number of overdetermined subsets is at most $\sum_{k=2}^n {n-1\choose k}=2^{n-1}-n,$ as desired.

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

Page

Toolbox

Search

2020 USAMO Problems/Problem 5

Problem

Solution