Yo is not reading nonzero a dock?

@above shoot, I made that mistake too

I got 2^(n-1)-n, but couldn’t completely prove it.

Solution: The answer is $2^{n-1}-n$, so let's prove it. Construction is take $(0,1)$ and $(k,1)$ for $1\le k<n$. Basically, we'll prove that for all $1<p<n$, the number of overdetermined sets of size $p$ is at most $\binom{n-1}{p}$. Now, let's say there are $k$ distinct curves that are formed by overdetermined sets of size $p$ that have degree $p-2$. Call the curves $A_1,\dots,A_k$. Let $|A_i|$ be the number of points on $A_i$ in $S$. Then, note that $p-1$ points define a curve of degree at most $p-2$, so each of these sets of points shares at most $p-2$ with any other. And then, the number of overdetermined subsets of size p from these curves is $$\sum \binom{|A_i|}{p}$$so we want to prove $$\sum\binom{|A_i|}{p}\le\binom{n-1}{p}.$$ This inequality is a little annoying, but it's actually really weak. Take a point $x$ in $|A_1|$. Then, the total number of subsets of size p not containing $x$ is $\binom{n-1}{p}$, so this means that in order to prove the above inequality, we just need to show that there are more nonoverdetermined sets not containing $x$ than overdetermined sets containing $x$. This is because $\sum\binom{|A_i|}{p}$-overdetermined containing $x$+nonoverdetermined not containing $x$ is equal to $\binom{n-1}{p}$, or the number of sets of size p not containing x. But the number of nonoverdetermined sets not containing $x$ can be bounded from below by taking $p-1$ points from a certain curve, and then another point that cannot be on that curve. This works because $p-1$ points determine a curve. For every curve $A_i$ that $x$ lies on, this produces at least $(n-|A_i|)\binom{|A_i|-1}{p-1}$ because there are $n-|A_i|$ choices for points not in $A_i$ so also not $x$, since $x$ is in $A_i$. This is clearly at least one, because $|A_i|$ can't contain all $n$ points. Also, this produces distinct sets of points when we sum over the different $A_i$, because the $p-1$ points uniquely determine the curve. But here's the thing, if we count the number of overdetermined sets of size $p$ containing $x$, we just take all $A_i$ that contain $x$, and choose $p-1$ other points, because they must lie on a curve with $x$. There are $\binom{|A_i|-1}{p-1}$ ways to do this. However, we already showed above that the number of nonoverdetermined sets of size p not containing $x$ is at least $\binom{|A_i|-1}{p-1}$, so we're done.

We claim the answer is $k = 2^{n-1}-n$. We denote the $n$ points by $A$. Throughout the solution we will repeatedly use the following fact: Lemma: If $S$ is a finite set of points in the plane there is at most one polynomial with real coefficients and of degree at most $|S|-1$ whose graph passes through all points of $S$. Proof. If any two of the points have the same $x$-coordinate then obviously no such polynomial may exist at all. Otherwise, suppose $f$ and $g$ are two such polynomials. Then $f-g$ has degree at most $|S|-1$, but it has $|S|$ roots, so is the zero polynomial. $\blacksquare$ Remark: Actually Lagrange interpolation implies that such a polynomial exists as long as all the $x$-coordinates are different! \medskip Construction: Consider the set $A = \left\{ (1,a), (2,b), (3,b), (4,b), \dots, (n,b) \right\}$, where $a$ and $b$ are two distinct nonzero real numbers. Any subset of the latter $n-1$ points with at least one element is overdetermined, and there are $2^{n-1}-n$ such sets. \medskip Bound: Say a subset $S$ of $A$ is flooded if it is not overdetermined. For brevity, an $m$-set refers simply to a subset of $A$ with $m$ elements. Claim: If $S$ is an flooded $m$-set for $m \ge 3$, then at most one $(m-1)$-subset of $S$ is not flooded. Proof. Let $S = \left\{ p_1, \dots, p_m \right\}$ be flooded. Assume for contradiction that $S - \{p_i\}$ and $S - \{p_j\}$ are both overdetermined. Then we can find polynomials $f$ and $g$ of degree at most $m-3$ passing through $S - \{p_i\}$ and $S - \{p_j\}$, respectively. Since $f$ and $g$ agree on $S - \{p_i, p_j\}$, which has $m-2$ elements, by the lemma we have $f = g$. Thus this common polynomial (actually of degree at most $m-3$) witnesses that $S$ is overdetermined, which is a contradiction. $\blacksquare$ Claim: For all $m = 2, 3, \dots, n$ there are at least $\binom{n-1}{m-1}$ flooded $m$-sets of $A$. Proof. The proof is by downwards induction on $m$. The base case $m = n$ is by assumption. For the inductive step, suppose it's true for $m$. Each of the $\binom{n-1}{m-1}$ flooded $m$-sets has at least $m-1$ flooded $(m-1)$-subsets. Meanwhile, each $(m-1)$-set has exactly $n-(m-1)$ parent $m$-sets. We conclude the number of flooded sets of size $m-1$ is at least \[ \frac{m-1}{n-(m-1)} \binom{n-1}{m-1} = \binom{n-1}{m-2} \]as desired. $\blacksquare$ This final claim completes the proof, since it shows there are at most \[ \sum_{m=2}^n \left( \binom nm - \binom{n-1}{m-1} \right) = 2^{n-1} - n \]overdetermined sets, as desired. Remark: [On repeated $x$-coordinates] Suppose $A$ has two points $p$ and $q$ with repeated $x$-coordinates. We can argue directly that $A$ satisfies the bound. Indeed, any overdetermined set contains at most one of $p$ and $q$. Moreover, given $S \subseteq A - \{p,q\}$, if $S \cup \{p\}$ is overdetermined then $S \cup \{q\}$ is not, and vice-versa. (Recall that overdetermined sets always have distinct $x$-coordinates.) This gives a bound $\left[ 2^{n-2}-(n-2)-1 \right] + \left[ 2^{n-2}-1 \right] = 2^{n-1}-n$ already. Remark: [Alex Zhai] An alternative approach to the double-counting argument is to show that any overdetermined $m$-set has an flooded $m$-superset. Together with the first claim, this lets us pair overdetermined sets in a way that implies the bound.

My solution follows a different approach by using an Injective Map to show the bound $k \le 2^{n-1} -n$. Throughout the solution, $OD$ means Overdetermined. If $D$ is a subset of $S$, we say that $P_D$ is the unique polynomial with degree at most $|D|-1$ such that all points in $D$ lie on the $P_D$ graph. For every $OD$ subset $D$, say that the Parent of $D$ is the greatest $OD$ subset $A$ of $S$ such that $P_A = P_D$. The main claim is the following: Claim. If we take a Map $M : \{D \subset S | D \text{ is OD}\} \rightarrow 2^S$ satisfying, for all $D$, that $M(D)= D \cup \{x\}$ for some $x \in S-A$ (here $A$ is the parent of $D$), then this map takes $OD$ subsets to non $OD$ subsets. Furthermore, this map is injective. Notice that $x$ exists since $S$ is non $OD$ Proof First we see that $D \cup \{x\}$ is non $OD$. If it were, we would have $\deg P_{D \cup \{x\}} \le (|D|+1)-2$, hence $P_{D \cup \{x\}}=P_D$, therefore $A \cup \{x\}$ is still $OD$, contradicting the maximality of $A$. Now we see that this map is injective. Say that $M(E)= E\cup \{x\} = F \cup \{y\} = M(F)$. Since $E \neq F$, we see that there is a set $T$ such that $E=T \cup \{y\}$ and $F = T \cup \{x\}$. Since both $E$ and $F$ are $OD$, we have that $\deg P_E \le |E|-2 = |T|-1$ and $P_E$ covers all points of $T$. And now we see that we must have $P_E=P_T=P_F$. Therefore $E$ and $F$ have the same parent, hence $x$ and $y$ are in this common parent, contradicting the definition of $M$. Finally, we just count everything. Notice that all sets in $\text{Im} M$ have size at least $3$. Therefore, if $L$ is the number of $2$-sets that are non $OD$, we must have that: $$2^n \ge 2k + L +n +1$$ (In the RHS we are also counting the $0,1,2$-sets that are not taken into account in the $2k$, hence we are counting $2k + L +n +1$ distinct subets). Assuming $k \ge 1+2^{n-1}-n$, we get $$2^n \ge 3-n+L+2^n$$ Hence $L \le n-3$. Now we notice that a $2$-set $\{(x_1,y_1),(x_2,y_2)\}$ is $OD$ iff $y_1=y_2 \neq 0$. Divide the points in $S$ according to their $y$-coordinate and get the subsets $A_1,...,A_m$. Notice that $m\ge 2$. Finally, $$L \ge \sum |A_i||A_j| = \frac{1}{2}( \sum |A_i| (n-|A_i|))= \frac{1}{2}( n^2 - \sum |A_i|^2 )\ge \frac{1}{2}(n^2 -1^2-(n-1)^2)) = n-1$$ Contradiction.

Here is a proof of the upper bound using induction on $n.$ As with most of the above solutions, show that if $T \cup \{a\}$ and $T \cup \{b\}$ are both overdetermined, so is $T \cup \{a, b\}.$ This is the "key lemma." The base cases when $n = 2$ or $n = 3$ are both trivial. Suppose it holds for $n \le k$. When $n = k+1$, note that v_Enhance 's first remark deals with the case where there is a repeated $x-$coordinate. Henceforth, suppose all $x-$coordinates of the points are distinct. Say the points are $P_1 = (x_1, y_1), P_2 = (x_2, y_2), \cdots, P_{k+1} = (x_{k+1}, y_{k+1})$ with the $x_i$'s distinct. In view of the key lemma, there exists an $1 \le i \le k+1$ such that $\{P_1, P_2, \cdots, P_{k+1} \} / \{P_i \}$ is not overdetermined. We can assume WLOG that $\{P_1, P_2, \cdots, P_k\}$ is not overdetermined. It's also clear that translating all the points by the same vector preserves the number of overdetermined sets, and so we can assume that $x_{k+1} = y_{k+1} = 0.$ Now, the induction hypothesis on $\{ P_1, P_2, \cdots, P_k \}$ yields that there are at most $2^{k-1} - k$ overdetermined sets not including $P_{k+1}.$ It suffices to show there are at most $2^{k-1} - 1$ including $P_{k+1}.$ After assuming $x_{k+1} = y_{k+1} = 0$, let $Q_i$ be the point $(x_i, \frac{y_i}{x_i})$ for each $1 \le i \le k$. This is defined because $x_i \neq 0$ (else there was a repeated $x-$coordinate originally). Note that for a subset $\{a_1, a_2, \cdots, a_t \} \in [k]$ with size $\ge 2$, the set $\{Q_{a_1}, Q_{a_2}, \cdots, Q_{a_t} \}$ is overdetermined if and only if $\{P_{k+1}, P_{a_1}, P_{a_2}, \cdots, P_{a_t} \}$ is. Indeed, the polynomial of degree at most $t$ going through the points $P_{k+1}, P_{a_1}, P_{a_2}, \cdots, P_{a_t}$ is simply $x$ times the polynomial of degree at most $t-1$ going through the points $Q_{a_1}, Q_{a_2}, \cdots, Q_{a_t}.$ Thus, the induction hypothesis on the $Q_i$'s yields that there are at most $2^{k-1} - k$ overdetermined sets of size at least $3$ containing $P_{k+1}.$ (Note that since $\{P_1, P_2, \cdots, P_{k+1} \}$ is not overdetermined, neither is $\{Q_1, Q_2, \cdots, Q_k \}$ and therefore we are allowed to apply induction on it). There are exactly $k$ sets of size two containing $P_{k+1}$, and they cannot all be overdetermined as then the entire set of points lies on a horizontal line (and is thus overdetermined). Combining these results, there are at most $2^{k-1} - k + k - 1 = 2^{k-1} - 1$ overdetermined sets containing $P_{k+1}.$ Combining with the sets not containing $P_{k+1}$, the induction is complete. $\square$

lifeisgood03 wrote: Solution Hey! I'm wondering if this approach is valid. Did anybody else try to solve the problem this way? Also, because this is rather different from the official solutions and the other solutions in this thread, it's difficult for me to evaluate it. Does anybody have any thoughts?

Sad problem indeed

The answer is $2^{n-1}-n$. To construct this, consider the set of points $\{(1,1),(2,1),\ldots, (n-1,1), (n,0)\}$. Every subset of the first $n-1$ points with at least 2 elements is overdetermined, and there are $2^{n-1}-(n-1)-1=2^{n-1}-n$ such subsets. Now we prove the bound. Actually, we can reduce the algebraic formulation to a completely combinatorial problem by the following lemma. Lemma: Let $S$ be a set of points, and let $a,b$ be two points. If $S\cup \{a\}$ and $S\cup\{b\}$ are overdetermined, then $S\cup \{a,b\}$ is overdetermined. Proof: Let $A=S\cup \{a\}$ and $B=S\cup \{b\}$. Suppose $|A|=|B|=k$. We know $A,B$ are overdetermined and $|A\cap B|=k-1$. We want to show $A\cup B$ (which has $k+1$ elements) is overdetermined. All $k$ points on $A$ lie on a polynomial of degree $\le k-2$, but actually this polynomial is determined by any $k-1$ of the points in $A$ (if there were two polynomials of degree $\le k-2$ that agreed at $k-1$ points, then their difference must be the 0 polynomial). In particular, if we let $P(x)$ be the polynomial for $S$ and let $a=(a_x,a_y)$, then $P(a_x)=a_y$. Similarly, if $b=(b_x,b_y)$, then $P(b_x)=b_y$. So $a,b$ both lie on $P$, implying all points on $S\cup \{a,b\}$ lie on a polynomial of degree $\le k-2$, which means it is (``doubly'') overdetermined. $\blacksquare$ Note: Actually, the above proof also shows that any $k$-subset of $S\cup \{a,b\}$ is also overdetermined for any point $x$, but we won't need that. Now the problem is just about sets. Call a set good if it's overdetermined and bad if not. The key is to focus on the bad sets. The following claim is basically all we need: Claim: [Key claim] Every bad $k$-set has at most 1 good $(k-1)$-subset. Proof: Follows directly from contrapositive of the lemma. $\blacksquare$ Consider the poset of bad sets, ordered by inclusion. The top level is level $n$, and it decreases down to level 2. The following is the equality case for $n=5$, with the good sets being all $\ge 2$ element subsets of $abcd$. Claim: Level $k$ has at least $\tbinom{n-1}{k-1}$ elements. Proof: Suppose there are $a_k$ elements on level $k$; we want to show $a_k \ge \tbinom{n-1}{k-1}$. Induct on $k$ going down. We know the full set is bad, so the top level has exactly $a_n=\tbinom{n-1}{n-1}=1$ element, proving the base case. Let $N$ be the number of edges between level $k$ and level $k-1$. We double count $N$. By the claim, each element on level $k$ has at least $k-1$ edges going down, so \[ N \ge (k-1)a_k \ge (k-1) \binom{n-1}{k-1}\]by induction. On the other hand, for any string of length $k-1$, it is contained in at most $n-(k-1)$ strings above it. So \[ N \le a_{k-1} (n-k+1). \]Therefore, \[ a_{k-1} \ge \frac{k-1}{n-k+1}\binom{n-1}{k-1} = \binom{n-1}{k-2}, \]completing the induction. $\blacksquare$ Now, the total number of good sets is at most \[ \sum_{k=2}^{n}\left( \binom{n}{k} - \binom{n-1}{k-1} \right) = (2^n-n-1) - (2^{n-1}-1) = 2^{n-1}-n,\]and we are done.

The answer is $2^{n-1}-n$. Construction is attained by taking $(1,1),(2,1),\dots,(n-1,1),(n,2)$. This construction works because any set of points with $i$ elements including $(n,2)$ and a polynomial $P$ corresponding to them would have $i-1$ roots to $P(x)-1$ but also be nonzero, so a set of some of these points is overdetermined iff it has at least two points and all of its points are of the form $(i,1)$, which yields $2^{n-1}-n$ overdetermined subsets. First, we translate the problem into combinatorics. For a set $S$ of points, observe that it is overdetermined if two of its subsets $T,U$ with $|S|-1$ elements are also overdetermined. This is because if that were the case, then the intersection of those two subsets would have $|S|-2$ elements which would have minimal polynomial equal to both the polynomial for $T$ and the polynomial for $U$, so those two polynomials would be the same and $S$ would be overdetermined. Now, consider some set of points $S$ with $n$ elements. We prove the following claim for all $2\le k\le n-2$; if the number of overdetermined subsets of $S$ containing $k$ elements is at least $\binom{n-1}{k}$. then there are at least $\binom{n-1}{k+1}$ overdetermined subsets of $S$ containing $k+1$ elements. Moreover, if equality does not hold in the condition for $k$, equality does not hold in the conclusion. Proving this claim is remarkably reasonable, so let's get to it. Let $A$ denote the number of overdetermined subsets of $S$ containing $k+1$ elements and $B$ denote the number of non-overdetermined subsets of $S$ with $k+1$ elements. Let $f(k)$ denote the number of overdetermined subsets of $S$ containing $k$ elements; this is essentially a dummy variable to extract the second part of the claim. By double-counting, we have \begin{align*} A+B&=\binom{n}{k+1}\\ (k+1)A+B&\ge (n-k)f(k) \ge (n-k)\binom{n-1}{k}. \end{align*}Subtract the first equation from the latter to yield \[kA \ge (n-k)\binom{n-1}{k}-\binom{n}{k+1} = (n-k)\cdot\frac{(n-1)!}{(n-k-1)!k!} - \frac{n!}{(n-k-1)!(k+1)!} = \left(n-k-\frac{n}{k+1}\right)\cdot\frac{(n-1)!}{(n-k-1)!k!} = \frac{kn-k^2-k}{k+1}\cdot\frac{(n-1)!}{(n-k-1)!k!}.\]Divide through by $k$ to yield \[A\ge \frac{(n-1)!}{(n-k-2)!(k+1)!} = \binom{n-1}{k+1}.\]Since equality can only hold if $f(k)=\binom{n-1}{k}$, the claim is proven. Now, observe that the claim means that if there exists any $2\le k\le n-1$ for which $S$ has more than $\binom{n-1}{k}$ overdetermined subsets containing $k$ elements, then $S$ has at least two overdetermined sets containing $n-1$ elements and is hence overdetermined over all, absurd. Otherwise, we see that $S$ contains at most \[\sum_{k=2}^{n-1} \binom{n-1}{k} = 2^{n-1}-n\]overdetermined subsets, as desired.

Didn't manage to completely solve the problem. I identified the key claim but my combinatorial reasoning was flawed.

The answer is \(2^{n-1}-n\), achieved by \(S=\{(1,0),(2,1),(3,1),(4,1),\ldots,(n,1)\}\). Claim: Let \(T\) be a non-overdetermiend set. Then there is at most one overdetermined subset of \(T\) with size \(|T|-1\). Proof. If there are two distinct overdetermined subsets of size \(|T|-1\), they intersect at \(|T|-2\) points. But each overdetermined set of size \(|T|-1\) represents a polynomial of degree \(|T|-3\). The two polynomials share \(|T|-2\) points in common, so they are the same polynomial. Hence \(T\) is overdetermined. \(\blacksquare\) Claim: There are at most \(\binom{n-1}k\) overdetermined subsets of \(S\) with size \(k\). Proof. The claim is equivalent to showing there are at least \(\binom{n-1}{k-1}\) non-overdetermined subsets of size \(k\). We will prove this by downward induction on \(k\). The base case \(k=n\) is trivial. Now assume there are at least \(\binom{n-1}k\) non-overdetermined subsets of size \(k+1\). Consider a bipartite graph between \(A\), the set of non-overdetermined subsets of size \(k+1\), and \(B\), the set of non-overdetermined subsets of size \(k\). Draw an edge between \(a\in A\) and \(b\in B\) whenever \(b\subset a\). Then by the first claim, each element of \(A\) has degree at least \(\binom{k+1}1-1=k\). Obviously, each element of \(B\) has degree at most \(n-k\), so \[|B|\ge\frac k{n-k}\cdot|A|\ge\frac k{n-k}\binom{n-1}k=\binom{n-1}{k-1}.\]\(\blacksquare\) Finally, the number of overdetermined subsets of \(S\) is at least \[\sum_{k\ge2}\binom{n-1}k=2^{n-1}-n.\]

Remark: Nice problem nevertheless, but what's with the algebraic flavortext . Clearly a combo problem. Clearly a degree $P$ polynomial is uniquely determined by $p$ distinct points (with different $x$ coordinates) in the Cartesian plane, say by Lagrange Interpolation. The answer is $2^{n-1} - n$, say when we have\[S = \{(0, 0)\} \cup \{(1, 1), (2, 1), \ldots , (n-1, 1)\}.\]This set itself is clearly not overdetermined $-$ the polynomial passing through all these points has degree $\geq |S| - 1$. The only overdetermined subsets are those with size $\geq 2$ containing some of $(i, 1)$ from $i \in [1, n-1]$ for a total of\[2^{n-1} - \tbinom{n-1}{1} - \tbinom{n-1}{0} = 2^{n-1} - n\]indeed. Call non-overdetermined sets unsure. Given an unsure set $T$, we will show that among its $|T|$ size $|T| - 1$ subsets, at most $1$ is overdetermined. FTSoC suppose $T \backslash p_i$ and $T \backslash p_j$ for distinct points $p_i, p_j \in T$ are both overdetermined, say by polynomials $P_i(x)$ and $P_j(x)$, respectively, each with degrees $|T| - 3$. Note that these two polynomials share $|T \backslash p_i, p_j| = |T| - 2$ points, but both have degree $|T| - 3$, so they must be the same everywhere and thus the same polynomial which passes through all points in $T$. But $T$ is unsure, indeed impossible. Next, we show for each $k \in [2, n]$, that among the $\tbinom nk$ subsets of any unsure $T$, at least $\tbinom {n-1}{k-1}$ are unsure. We induct down; the result is clearly true for $k = n$. Suppose it is true for some $k$: we will show it is also true for $k-1$. We know that there are at least $\tbinom{n-1}{k-1}$ unsure $k$ sized sets, each of which produces at least $k-1$ unsure $k-1$ sized sets. There may be overlaps $-$ each unsure $k-1$ sized set is a susbet of exactly $n - k + 1$ many $k$-sized sets, only some of which are unsure, so among the total count\[C \geq (k-1)\binom{n-1}{k-1}\]each unsure $k-1$ sized set is counted at most $n - k + 1$ times in unsure $k$ sized sets, hence the number of unsure $k-1$ sized sets is\[\geq \frac{k-1}{n - k + 1}\binom{n-1}{k-1} = \binom{n-1}{k-2}\]completing the induction. So indeed, our final answer is\[\leq \sum_{k = 2}^n \left(\binom{n}{k} - \binom{n-1}{k-1}\right) = (2^n - (n+1)) - (2^{n-1} - 1) = 2^{n-1} - n\]as desired. $\blacksquare$

The answer is $\boxed{2^{n-1}-n.}$ For the construction, consider the points $(1,0),(2,0),\dots,(n-1,0),(n,1)$. This equality case will motivate the solution that follows. First, we convert this problem to combinatorics. Remark that for set $S$ that is not overdetermined, there exists at most one subset of $S$ with $|S|-1$ elements that is overdetermined. Say a subset is sharp if it is not overdetermined. Claim: For all positive integers $2 \leq k \leq n-1$, there are at most $\tbinom{n-1}{k}$ overdetermined sets with $k$ elements. Proof: We induct down on $n$, with the base case following from the fact that $S$ is not overdetermined. For the inductive step, suppose that there are at most $\tbinom{n-1}{k-1}$ overdetermined subsets of $S$ with $k$ elements. Now we double count the number of pairs of subsets $(A,B)$ of $S$ such that $A$ is a $k$-element subset of $S$, and $B$ is a $k-1$-element sharp subset of $A$. On one hand, each sharp $k$-element subset of $S$ must have at least $k-1$ sharp $k-1$-element subsets, so the number of pairs $(A,B)$ must be at least $\left(k-1\right)\tbinom{n-1}{k-1}$. On the other hand, once we choose a sharp $k-1$-element subset of $S$, we can construct $A$ in exactly $n-k+1$ ways. Thus the number of sharp subsets is at least $$\frac{k-1}{n-k+1} \binom{n-1}{k-1} = \binom{n-1}{k-2},$$so the number of overdetermined subsets is at most $\tbinom{n}{k-1} - \tbinom{n-1}{k-2} = \tbinom{n-1}{k-1}.$ Now the total number of overdetermined sets is at most $$\sum _{k=2} ^n \binom{n-1}{k} = \sum _{k=0} ^n \binom{n-1}{k} - \left(\binom{n}{0}+\binom{n}{1}\right) = 2^{n-1}-n,$$as desired. Remarks: Nice problem. This solution is motivated by the following: first, in the equality case, there are exactly $\tbinom{n-1}{k}$ overdetermined subsets with $k$ elements, so it thus follows that we want to focus on subsets with the same size, and hints at the main claim we want to prove. Furthermore, this problem has a distinct "top-down" structure: in particular, whether or not larger subsets are overdetermined determine whether its subsets can be overdetermined. This lends itself nicely to induction, and a simple double-count finishes. I feel that this problem is quite similar to USAMO 2015/3. Two other problems that are similar to varying degrees include TSTST 2018/7 and USEMO 2020/2.

The answer is $2^{n-1}-n.$ Claim: Given a set $S$ of $k$ points, there exists at most one overdetermined subset of size $k-1.$ Moreover, there exists at most one overdetermined superset of size $k+1.$ Proof. Suppose there exists two distinct overdetermined subsets $|P| = |Q| = k-1$ with polynomials $f,g$ with $\deg f, \deg g \le k-3.$ Note that $|P\cap Q| = k-2$ lies on $f,g,$ which by Lagrange Interpolation implies $f=g,$ implying $|P|, |Q| \ne k-1.$ Contradiction. Similarly, if there are two distinct overdetermined supersets $|P| = |Q| = k+1,$ then polynomials $f,g$ with $\deg f, \deg g \le k-1,$ but $S$ lies on $f,g$ implying $f=g$. Contradiction. $\blacksquare$ Claim: For $1\le k\le n-2,$ there are at most $\binom{n-1}{k-1}$ overdetermined subsets of $S$ with size $n-k.$ Proof. We may choose a sequence of subsets $S_n \to S_{n-1} \to \cdots \to S_{n-k}$ where $|S_i| = i$ and $S_{i-1}\subset S_i$ and $S_n, S_{n-1}, \dots, S_{n-k+1}$ are non overdetermined. Note that the number of overdetermined subsets of size $n-k$ is maximized when every nonoverdetermined set of size $t$ has one overdetermined subset of size $t-1.$ From the earlier claim, there are $(n-1)(n-2)\cdots (n-k+1)$ many such sequences. Moreover, since each set of size $n-k$ has $k-1$ non overdetermined supersets, there are at least $(k-1)!$ many such sequences for a given $S_{n-k}$ by considering the reverse direction of the form $S_{n-k} \to S_{n-k+1} \to \cdots \to S_n.$ Hence, dividing for multiplicity, there are at most $$\frac{(n-1)(n-2)\cdots (n-k+1)}{(k-1)!} = \binom{n-1}{k-1}$$overdetermined subsets of size $n-k.$ $\blacksquare$ Hence, there are at most $$\sum_{k=1}^{n-2} \binom{n-1}{k-1} = 2^{n-1} - n$$Overdetermined subsets. Finally, for a construction, let $n-1$ points lie on the $x$ axis and let the $n$th point lie on $(2020,2020).$

Used a bit of help on this one. A funny story: I was totally stuck after reading the "automated" OTIS hints, so I dm'ed Evan for help. While describing what I had tried so far I suddenly figured out the key claim The answer is $2^{n-1}-n$. Refer to the set of $n$ points as $A$. For a construction, let $A=\{(0,1),(1,1),\ldots,(n-1,1), (n,0)\}$. Clearly any subset of size at least $2$ containing only the first $n-1$ points is overdetermined, of which there are $2^{n-1}-n$. Further, if some overdetermined subset $S$ contains $(n,0)$ and $k \geq 1$ other points, then there exists a polynomial $p$ with degree at most $k-1$ passing through every point in $S$, but $p-1$ has $k$ roots, so $p-1$ is the zero polynomial. However, this doesn't pass through $(n,0)$: contradiction. Hence no other overdetermined subsets exist, so this construction gives $2^{n-1}-n$. It remains to prove that this is maximal. First, we will define the zero polynomial to be degree $0$, and allow it to be included as an interpolating polynomial for a set of points. For example, the set $\{(0,0),(1,0),(2,0)\}$ is overdetermined—clearly this cannot decrease the number of overdetermined subsets. We now introduce the following key claim: Lemma: Given a non-overdetermined set $S$, there is at most one overdetermined subset $T$ of $S$ such that $|T|=|S|-1$. Proof: Suppose we have two overdetermined subsets $T_1,T_2$. Let $p_1,p_2$ be interpolating polynomials of $T_1,T_2$ respectively with degree at most $|S|-3$. Since $p_1$ and $p_2$ are equal over $T_1 \cap T_2$, which contains $|S|-2$ elements, hence $p_1=p_2$. Since $T_1 \cup T_2=S$, this means $p_1$ interpolates $S$. As $\deg p_1\leq |S|-2$, it follows that $S$ is overdetermined, which is a contradiction. $\blacksquare$ Now let $f(k)$ denote the number of overdetermined subsets of $A$ containing $k$ elements, where $2 \leq k \leq n$. I will establish the following claims: Claim 1: Any subset $S$ of $A$ with size $k$ is also a subset of some non-overdetermined subset of $A$ with size $k+1$, for $2 \leq k < n$. Proof: Suppose otherwise. Let $T_1,T_2$ be two subsets of $A$ and supersets of $S$ with size $k+1$, and let $p_1,p_2$ be polynomials of degree at most $k-1$ which interpolate $T_1,T_2$ respectively. Since $p_1,p_2$ agree over $S$ (which is $k$ points), it follows that $p_1=p_2$. Since $T_1,T_2$ are chosen arbitrarily, it follows that the same polynomial interpolates any superset of $S$ with size $k+1$, hence this polynomial interpolates their union, which is just $A$. However since $k-1\leq n-2$ this means $A$ is overdetermined, which is a contradiction. $\blacksquare$ Claim 2: We have $f(k)+f(k-1) \leq \binom{n}{k}$ for $3 \leq k \leq n$. Proof: Clearly there are $\binom{n}{k}$ subsets of $A$ with size $k$ in total, so there are $\binom{n}{k}-f(k)$ such subsets which are also non-overdetermined. By claim 1, any overdetermined subset with size $k-1$ must be a subset of at least one of these $\binom{n}{k}-f(k)$ non-overdetermined subsets of size $k$. However, by the lemma, any non-overdetermined subset of size $k$ has at most $1$ subset of size $k-1$ which is overdetermined. This yields $f(k-1)\leq \binom{n}{k}-f(k)$, which is what we wanted to prove. $\blacksquare$ Now note that summing this inequality from $3$ to $n$ gives $$f(n)+2(f(n-1)+\cdots+f(3))+f(2)= 2(f(n-1)+\cdots+f(3))+f(2)\leq \sum_{k=3}^n \binom{n}{k},$$as we have $f(n)=0$. We need one final claim before we're done: Claim 3: We have $f(2) \leq \binom{n-1}{2}$. Proof: Note that if a set with $2$ elements in it is overdetermined, it must be constant. If we create a graph $G$ where a vertex represents an element of $A$ and an edge between two vertices means the two elements form an overdetermined set, $G$ must be disconnected, otherwise the $y$-coordinates of $A$ are constant and $A$ is overdetermined, which is impossible. Hence it is well-known that $G$ must have at most $\binom{n-1}{2}$ edges. $\blacksquare$ Combining claim 3 with our previous inequality, it follows that $$2(f(n-1)+\cdots+f(2))\leq \binom{n-1}{2}+\sum_{k=3}^n \binom{n}{k}=2^n-(n-1)-n-1=2^n-2n.$$From this we obtain $f(n-1)+\cdots+f(2)\leq 2^{n-1}-n$, which is the desired bound. $\blacksquare$

I have a really weird solution. I skimmed through the posts and I didn't see any solution similar to mine. The answer is $2^{n-1}-n$, obtained by $\{(x_1,y),(x_2,y),\ldots,(x_{n-1},y),(x_n,y')\}$. Claim: Suppose $S_1$ and $S_2$ are overdetermined sets such that $|S_1|=|S_2|=|S_1 \cap S_2|+1$. Then, $S_1 \cup S_2$ is also overdetermined. Proof: The polynomials that interpolate $S_1$ and $S_2$ must be the same since they are of degree at most $|S_1|-2$ and pass through the same $|S_1|-1$ points. Thus, $S_1 \cup S_2$ is interpolated by a polynomial of degree at most $|S_1|-2$, so it is overdetermined. Call any collection of subsets of size at least $2$ of $\{1,2,\ldots,n\}$ good if for any sets $S_1$ and $S_2$ in the collection with $|S_1|=|S_2|=|S_1 \cap S_2|+1$, $S_1 \cup S_2$ is also in the collection. We create an algorithm that would turn any good collection of sets into a good collection with $2^{n-1}-n$ sets while keeping the number of sets nondecreasing. Notice that there can be at most one set of size $n-1$. If there isn't, then add one. Assume WLOG that the set of size $n-1$ is $\{1,2,\ldots,n-1\}$. We claim by induction that we can create an algorithm that keeps the number of sets nondecreasing and ends up with a collection of subsets of $\{1,2,\ldots,n-1\}$. The base case of $n-1$ is already proven. Suppose that all sets of size $k+1$ in the collection are subsets of $\{1,2,\ldots,n-1\}$. We look at all the sets of size $k$. If there is such a set $S$ that includes $n$, then change $n$ to any other integer between $1$ and $n-1$, inclusive, that isn't already in $S$. This will work because there cannot be any other set of size $k$ that shares $k-1$ elements with $S$; if there was such a set $T$, then that means $S \cup T$ is a set of size $k+1$ that includes $n$. However, that contradicts our inductive hypothesis, so our induction is finished. Thus, the number of overdetermined sets is at most the number of subsets of $\{1,2,\ldots,n-1\}$ of size at least $2$. That number is $2^{n-1}-n$, so we are done.

Solved with rama1728. The answer is $\boxed{2^{n-1} -n}.$ Construction: Take $(0,0); (1,0); \dots (n-2,0); (n-1,1).$ Any polynomial going through all of these points must have $n-1$ roots and is not zero everywhere, so its degree is at least $n-1.$ However, note that any subset of $(0,0); (1,0); \dots (n-2,0)$ with size at least $2$ is overdetermined. $\square$ Lemma: If two overdetermined sets of size $k$ have an intersection of size $k-1,$ their union is overdetermined. Proof: The difference between the two polynomials going through the two overdetermined sets has degree at most $k-2,$ and also has $k-1$ roots. So it's a zero polynomial. So the two polynomials are in fact identical and there is one polynomial with degree at most $k-2$ passing through the union of the two sets. $\square$ Bound: It suffices to prove that for all $1 < p < n,$ the number of overdetermined sets of size $p$ is at most $\binom{n-1}{p},$ since $$\binom{n-1}{2} + \binom{n-1}{3} + \dots + \binom{n-1}{n-1} = 2^{n-1} - \binom{n-1}{1} - \binom{n-1}{0} = 2^{n-1}-n.$$We prove with induction downwards. The base case $p = n-1$ follows from our lemma. Suppose we have proven for $p.$ So there are at least $\binom{n-1}{p-1}$ not overdetermined subsets of size $p.$ Each not overdetermined set of size $p$ contains at least $p-1$ not overdetermined sets of size $p-1$ by our lemma. Each not overdetermined set of size $p-1$ is in $n-p+1$ sets of size $p.$ So there are at least $$\binom{n-1}{p-1} \cdot \frac{p-1}{n-p+1} = \binom{n-1}{p-2}$$not overdetermined subsets of size $p-1,$ which is finishes our inductive step. $\blacksquare$

The answer is $2^{n-1}-n$, which can be constructed by $S=\{(1,0),(2,1),(3,1),(4,1),\ldots,(n,1)\}$. In what follows, call sets that are overdetermined good and sets that are not overdetermined bad. Lemma: [characterization of good sets] If $S \cup \{x\}$ and $S \cup \{y\}$ are good, then so is $S \cup \{x, y\}$. Proof. Let the points in $S \cup \{x\}$ be represented by the polynomial $f$ and the points in $S \cup \{y\}$ be represented by the polynomial $g$. Note that both $f$ and $g$ have degree at most $|S|-1$, and thus $f-g$ has degree at most $|S|-1$. However, $f-g$ has $|S|$ roots, so it must be identically zero, so $f=g$. Therefore using the polynomial $f$ on the set of points $S \cup \{x, y\}$, we conclude. Taking the contrapositive of the lemma, we have the following claim. Claim: Every bad $k$-size set has at most one good $(k-1)$-sized subset. At this point, the rest of our solution is purely combinatorial. Claim: There are at most $\tbinom{n-1}{k-1}$ bad $k$-sized subsets of $S$, or equivalently there are at least $\tbinom{n-1}{k}$ good $k$-sized subsets of $S$ (as there exactly $\tbinom{n}{k}$ subsets that are $k$-sized). Proof. We induct downwards on $k$. The base case $k=n$ is trivially true. Suppose there are at least $\tbinom{n-1}{k}$ bad $k+1$-sized subsets of $S$. Consider the Hasse diagram of the poset of bad subsets where ordering is by inclusion (i.e./ $S_1 < S_2$ iff $S_1 \subset S_2$); we double count the number $M$ of edges between the set of $k+1$-sized elements to and the set of $k$-sized elements. First, we have \[ M \ge k \cdot \binom{n-1}{k} \]by counting the number of edges from the perspective of the $k+1$-sized elements, and \[ M \le N \cdot (n-k) \]where $N$ is the number of bad $k$-sized subsets of $S$, by counting the number of edges from the perspective of the $k$-sized elements. Combining the above two inequalities we have \[ N \ge \frac{k}{n-k}\binom{n-1}{k} = \binom{n-1}{k-1}, \]completing the inductive step. Thus the number of good subsets of $S$ is at least \[ \sum_{k \ge 2} \binom{n-1}{k}=2^{n-1}-n, \]and we are done.

Nice problem solved it after several hours. Here is my solution Claim: $k=2^{n-1}-n$ We First provide a construction then prove the bound. Construction : Set $S=\{(1,2),(2,2),...,(n-1,2),(n,1)\}$ . Showing this works is easy. First we prove $S$ is not overdetermined. If $S$ was Then the polynomial of smallest degree[easy to show uniqueness] passing through $\{(1,2),(2,2),..,(n-1,2)\}$ Must go through $\{(n,1)\}$ However the polynomial is $P(x)=2$ that implies $1=2$ which is not true. Now to prove it as $2^{n-1}-n$ overdetermined subsets Is also not too hard Case 1: $(n,1)$ is in the ovedetermined subset. This means atleast one element is from $(1,2),(2,2)...,(n-1,2)$ We then can easily show this implies $1=2$ again. So its a subset of $\{(1,2),(2,2),...,(n-1,2)\}$ Easy to see all subsets with atleast two elements work , so giving us $2^{n-1}-n$ . Now the hard to part is to prove the bound. We do by induction for $n=2$ its easy to check Proof for $n+1$ using $n$ Say we have a set of $n+1$ elements with more than $2^{n}-n-1$ overdetermined subsets . Call it $\{P_1,P_2,..,P_{n+1}\}$ . We will bound the number of overdetermined subsets containing $P_{n+1}$. Observe we can assume $P_{n+1}=(0,0)$ if $P_i=(x_i,y_i)$ . Its then easy to see if $T$ is one such over determined subsets the elements of $T$ belonging to $\{(1,2),(2,2),...,(n-1,2)\}$ are say $(a_1,b_1),(a_2,b_2),..,(a_k,b_k)$ Then the condition holds iff $a_i$ is never zero and $(a_1,\frac{b_1}{a_1}),(a_2,\frac{b_2}{a_2}),...,(a_k,\frac{b_k}{a_k})$ is over determined too. if $k=1$ however $b_1=0$ is necessary and sufficient. So the answer would just be the no of over determined subsets of $(a_1,\frac{b_1}{a_1}),(a_2,\frac{b_2}{a_2}),...,(a_{n},\frac{b_n}{a_n})$ + the no of $0$'s in $b_i$ Which due to indcution is $\leq 2^{n-1}-(n)$+no of $0$'s in $b_i$ Now if $b_i$ is not always $0$ Which it cannot otherwise $S$ also is overdetermined. The value of no of 0's is clearly $\leq n-1$ so the answer is max to max $2^{n-1}-1$ And for the number of overdetermined subsets not containing last term the value is at max $2^{n-1}-n$ So $k \leq 2^{n-1}-1+2^{n-1}-n=2^{n}-(n+1)$ As required

The answer is $2^{n-1}-n$. This is attainable by choosing the points \[ (1,1), (2,1), \dots, (n-1, 1), (n,2).\]Then, any subset of the first $n-1$ points with at least $2$ elements is overdetermined (since the polynomial $f(x) = 1$ with degree $0$ passes through those points). Furthermore, the entire set of points is not overdetermined because for any polynomial $f(x)$ passing through these points, $f(x) = 1$ has at least $n-1$ roots. Call a set of points "normal" if it is not overdetermined. We construct a function $f$ from overdetermined sets to normal sets as follows: for each overdetermined set $\mathcal S$, choose a point $P$ which does not lie on the polynomial through $\mathcal S$; then, let $f ( \mathcal S) = \mathcal S \cup \{ P \}$. Claim: $f$ is an injection. Proof: First, note that in our definition of $f$, $\mathcal S \cup \{ P \}$ is in fact a normal set. This is because if $\mathcal S \cup \{ P \}$ was overdetermined, the points in $\mathcal S$ alone would be enough to determine the polynomial of lowest degree through the points in $\mathcal S \cup \{ P \}$, yet this is clearly not the case. Now, to show that $f$ is an injection: suppose, FTSOC, that there are two overdetermined sets $\mathcal A$ and $\mathcal B$ which both map to the same normal set $\mathcal A \cup \mathcal B$. But then, $\mathcal A$ and $\mathcal B$ differ by only one element, so the polynomial determined by the points in $\mathcal A \cap \mathcal B$ should pass through all the points in both $\mathcal A$ and $\mathcal B$. But this contradicts the fact that $\mathcal A \cup \mathcal B$ is normal. Claim: There are at least $2n$ normal sets with two points or less. Proof: The empty set and the singletons give us $n+1$ normal sets. We can find $n-1$ sets of size $2$ as follows: if there are $a$ points with a particular $y$-coordinate, then we have at least $a(n-a) \geq n-1$ pairs of points with different $y$-coordinates, so these pairs are not overdetermined. To finish, note that any normal set in the image of $f$ will, by definition, have three points or more, so the points in the domain/image of $f$ are all among $2^n - 2n$ points or less. Since $f$ is an injection, there are at most $2^{n-1} - n$ overdetermined sets, as desired.

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.