Problem

Source: 2020 USOMO 5, by Carl Schildkraut

Tags: combinatorics, Hi



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. Proposed by Carl Schildkraut