Maths Olympiad Prep

Library / /87 of 115

Algebra Difficulty 7.6 National olympiad, round 2 Find the answer

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

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

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

For each integer n2 n \ge 2 , our task is to find the largest integer k k such that there exists a set of n n distinct points that is \textit{not} overdetermined but has k k overdetermined subsets.

### Step-by-step Solution

1. Understand Overdetermined Sets:
- A set S S of points is overdetermined if it can lie on a polynomial of degree at most S2 |S| - 2 .
- The condition S2 |S| \ge 2 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 S2 |S| - 2 .

3. Finding the Set and Overdetermined Subsets:
- Choose a set of n n 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 n2 n-2 .
- A configuration where there is no nonzero polynomial of degree n2 n-2 passing through all n n points is possible.

4. Counting Overdetermined Subsets:
- Any subset of S S with at least 2, but at most n1 n-1 points can potentially be overdetermined.
- For any subset with k k points (where 2kn1 2 \le k \le n-1 ), there exists a polynomial of degree k2 k-2 passing through the points, hence making it overdetermined. The entire set S S with n n points is chosen such that it does not allow for such polynomials of degree n2 n-2 .

5. Calculating Number of Such Subsets:
- The total number of subsets of S S with size ranging from 2 to n1 n-1 is calculated by:
k=2n1(nk). \sum_{k=2}^{n-1} \binom{n}{k}.
- This sum can be represented as the total number of subsets of a set of n n elements minus the subsets of size 0, 1, and n n :
2n(n0)(n1)(nn)=2n1n1=2nn2. 2^n - \binom{n}{0} - \binom{n}{1} - \binom{n}{n} = 2^n - 1 - n - 1 = 2^n - n - 2.
- Since we're excluding the empty set and all n n elements together, we confirm that:
k=2n1n. k = 2^{n-1} - n.

Thus, the largest integer k k is:
2n1n. \boxed{2^{n-1} - n}.
```

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.