Difference between revisions of "2020 USAMO Problems/Problem 5"

(Created page with "== Problem == A finite set <math>S</math> of points in the coordinate plane is called <i>overdetermined</i> if <math>|S| \ge 2</math> and there exists a nonzero polynomial <ma...")
 
(Solution)
 
(One intermediate revision by one other user not shown)
Line 7: Line 7:
 
{{Solution}}
 
{{Solution}}
  
{{USAMO box|year=2020|num-b=4|num-a=6}}
+
{{USAMO newbox|year=2020|num-b=4|num-a=6}}
 +
The answer is <math>2^{n-1}-n</math>. To construct this, have <math>n-1</math> points on a horizontal line and <math>1</math> 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 <math>S</math> and <math>T</math> are overdetermined subsets with <math>|S|=|T|=k</math> but <math>S</math> and <math>T</math> only differ by one element (one is swapped out for another), then <math>S\cup T</math> is overdetermined.\
 +
 
 +
Consider the minimal polynomial of <math>S</math>. It has degree at most <math>k-2</math> since <math>S</math> is overdetermined, and similarly with the minimal polynomial of <math>T</math>. However, there is a unique polynomial of degree at most <math>k-2</math> passing through <math>S\cap T</math> since it has <math>k-1</math> points. Thus, this unique polynomial also passes through <math>S</math> and <math>T</math>. Thus, this polynomial passes through all points of <math>S\cup T</math>, as desired.\
 +
 
 +
We now use this claim to inductively bound the number of overdetermined subsets with <math>k</math> elements. Let <math>m_k</math> denote the number of overdetermined subsets of size <math>k</math>. Clearly, <math>m_n=0</math>.\
 +
 
 +
Claim 2: We have <cmath>m_k\leq \frac{m_{k+1}(k+1)+{n\choose k+1}-m_{k+1}}{n-k}.</cmath> Proof: Each overdetermined subset of size <math>k+1</math> can have up to <math>k+1</math> overdetermined subsets of size <math>k</math>, but by the previous claim each non-overdetermined subset of size <math>k+1</math>, which there are <math>{n\choose k+1}-m_{k+1}</math> of, can have at most one. Each subset of size <math>k</math> feeds into <math>n-k</math> subsets of size <math>k+1</math>. Note that this is increasing in <math>m_{k+1}</math>.\
 +
 
 +
Claim 3: We have <cmath>m_k\leq {n-1\choose k}.</cmath> Proof: Use induction. Note that the expression in Claim 2 is nondecreasing in <math>m_{k+1}</math>, and verify that <cmath>\frac{{n-1\choose k+1}(k+1)+{n\choose k+1}-{n-1\choose k+1}}{n-k}={n-1\choose k}.</cmath>
 +
 
 +
Thus, we have that the number of overdetermined subsets is at most <cmath>\sum_{k=2}^n {n-1\choose k}=2^{n-1}-n,</cmath> as desired.
  
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 13:25, 4 December 2024

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 (ProblemsResources)
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. AMC logo.png