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
Given a finite set of points in the coordinate plane, a set is called \textit{overdetermined} if and there exists a nonzero polynomial with real coefficients of degree at most , such that for every point .
For each integer , our task is to find the largest integer such that there exists a set of distinct points that is \textit{not} overdetermined but has overdetermined subsets.
### Step-by-step Solution
1. Understand Overdetermined Sets:
- A set of points is overdetermined if it can lie on a polynomial of degree at most .
- The condition implies the minimum size for considering such sets.
2. Non-Overdetermined Set:
- A set is non-overdetermined if any polynomial fitting all points of the set must have a degree strictly larger than .
3. Finding the Set and Overdetermined Subsets:
- Choose a set of distinct points in general position (e.g., no three are collinear etc.), such that the entire set is not on a single polynomial of degree .
- A configuration where there is no nonzero polynomial of degree passing through all points is possible.
4. Counting Overdetermined Subsets:
- Any subset of with at least 2, but at most points can potentially be overdetermined.
- For any subset with points (where ), there exists a polynomial of degree passing through the points, hence making it overdetermined. The entire set with points is chosen such that it does not allow for such polynomials of degree .
5. Calculating Number of Such Subsets:
- The total number of subsets of with size ranging from 2 to is calculated by:
- This sum can be represented as the total number of subsets of a set of elements minus the subsets of size 0, 1, and :
- Since we're excluding the empty set and all elements together, we confirm that:
Thus, the largest integer is:
```