9. [35] Let $S$ be the set of ordered pairs of integers $(x, y)$ with $1 \leq x \leq 5$ and $1 \leq y \leq 3$. How many subsets $R$ of $S$ have the property that all the points of $R$ lie on the graph of a single cubic? A cubic is a polynomial of the form $y=a x^{3}+b x^{2}+c x+d$, where $a, b, c$, and $d$ are real numbers (meaning that $a$ is allowed to be 0 ).
Answer: 796 We observe that $R$ must contain at most 1 point from each column of $S$, because no function can contain more than 1 point with the same $x$-coordinate. Therefore, $|R| \leq 5(|R|$ denotes the number of elements of $R$ ). Note that 4 points determine a cubic, so if $R$ is any subset of points in distinct columns and $|R| \leq 4$, then $R$ has the desired property. There are $4^{5}$ ways to choose at most 1
point from each column and $3^{5}$ ways to choose exactly 1 point from each column. There are therefore $4^{5}-3^{5}=781$ subsets $R$ of $S$ such that $|R| \leq 4$ and all points of $R$ lie in distinct columns. As noted, these sets all automatically have the desired property.
Now we consider all sets $R$ of size 5 . As before, each point in $R$ must come from a different column. Let us shift our origin to $(3,2)$, and let $p$ be the polynomial containing all 5 points of $R$. Then $R=\{(-2, p(-2)),(-1, p(-1)),(0, p(0)),(1, p(1)),(2, p(2))\}$.
By the method of finite differences ${ }^{3}$, or alternately by Lagrange Interpolation ${ }^{4}$, there is a unique polynomial $p$ of degree less than 5 going through 5 specified points, and this polynomial is of degree less than 4 if and only if $p(-2)-4 p(-1)+6 p(0)-4 p(1)+p(2)=0$.
Then $p(-2)+p(2)+6 p(0)=4(p(-1)+p(1))$, where $p(-2)+p(2) \in\{-2-1,0,1,2\}, p(-1)+p(1) \in$ $\{-2,-1,0,1,2\}$, and $p(0) \in\{-1,0,1\}$. We know that $6 p(0)$ and $4(p(-1)+p(1))$ are necessarily even, thus we must have $p(-2)+p(2) \in\{-2,0,2\}$ in order for the equation to be satisfied.
Let $(a, b, c)=(p(-2)+p(2), 6 p(0), 4(p(-1)+p(1)))$. The possible values of $(a, b, c)$ that are solutions to $a+b=c$ are then $\{(-2,-6,-8),(-2,6,4),(0,0,0),(2,-6,-4),(2,6,8)\}$.
If $(a, b, c)=(-2,-6,-8)$, then we need $p(-2)+p(2)=-2, p(0)=-1, p(-1)+p(1)=-2$. There is only 1 possible solution to each of these equations: $(p(-2), p(2))=(-1,-1)$ for the first one, $p(0)=-1$ for the second, and $(p(1))=(-1,-1)$ for the third. Hence there is 1 possible subset $R$ for the case $(a, b, c)=(-2,-6,-8)$.
If $(a, b, c)=(-2,6,4)$, then there is again 1 possible solution to $p(-2)+p(2)=1$. There are two solutions to $p(-1)+p(1)=1:(p(-1), p(1))=(0,1),(1,0)$. Also, $p(0)$ can only be 1 , so there are 2 possible subsets for this case.
If $(a, b, c)=(0,0,0)$, then there there are 3 possible solutions to $p(-2)+p(2)=0:(p(-2), p(2))=$ $(-1,1),(0,0),(1,-1)$. Similarly, there are 3 possible solutions to $p(-1)+p(1)=0$. Also, $p(0)$ can only be 0 , so there are 9 possible subsets for this case.
If $(a, b, c)=(2,-6,-4)$, then there is 1 possible solution to $p(-2)+p(2)=2:(p(-2), p(2))=(1,1)$. There are 2 possible solutions to $p(-1)+p(1)=-1:(p(-1), p(1))=(0,-1),(-1,0)$. Also, $p(0)$ can only be -1 , so there are 2 possible subsets for this case.
If $(a, b, c)=(2,6,8)$, then there is 1 possible solution to $p(-2)+p(2)=2$, as shown above. There is 1 solution to $p(-1)+p(1)=2:(p(-1), p(1))=(1,1)$. Also, $p(0)$ can only be 1 , so there is 1 possible subset for this case.
Then there are $1+2+9+2+1=15$ total possible subsets of size 5 that can be fit to a polynomial of degree less than 4 . Hence there are $781+15=796$ possible subsets total.