2020 USAMO Problems/Problem 5
Problem
A finite set of points in the coordinate plane is called overdetermined if
and there exists a nonzero polynomial
, with real coefficients and of degree at most
, satisfying
for every point
.
For each integer , find the largest integer
(in terms of
) such that there exists a set of
distinct points that is not overdetermined, but has
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 . To construct this, have
points on a horizontal line and
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 and
are overdetermined subsets with
but
and
only differ by one element (one is swapped out for another), then
is overdetermined.\\
Consider the minimal polynomial of . It has degree at most
since
is overdetermined, and similarly with the minimal polynomial of
. However, there is a unique polynomial of degree at most
passing through
since it has
points. Thus, this unique polynomial also passes through
and
. Thus, this polynomial passes through all points of
, as desired.\\
We now use this claim to inductively bound the number of overdetermined subsets with elements. Let
denote the number of overdetermined subsets of size
. Clearly,
.\\
Claim 2: We have Proof: Each overdetermined subset of size
can have up to
overdetermined subsets of size
, but by the previous claim each non-overdetermined subset of size
, which there are
of, can have at most one. Each subset of size
feeds into
subsets of size
. Note that this is increasing in
.\\
Claim 3: We have Proof: Use induction. Note that the expression in Claim 2 is nondecreasing in
, and verify that
Thus, we have that the number of overdetermined subsets is at most as desired.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.