Art of Problem Solving
Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2020 USAMO Problems/Problem 5: Difference between revisions

← Older edit
Martin.s (talk | contribs)
editor
16 edits
Martin13579 (talk | contribs)
editor
35 edits
mNo edit summary
 
Line 5: Line 5:


== Solution ==
== Solution ==
{{Solution}}


{{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.\\
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.\\


Line 24: Line 22:
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.
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.


{{USAMO newbox|year=2020|num-b=4|num-a=6}}
{{MAA Notice}}
{{MAA Notice}}

Latest revision as of 22:27, 30 September 2025

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

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.


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

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. Error creating thumbnail: File missing

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_USAMO_Problems/Problem_5&oldid=261965"