Valentin Vornicu wrote: Let $ n$ be a positive integer. Consider \[ S = \left\{ (x,y,z) \mid x,y,z \in \{ 0, 1, \ldots, n\}, x+y+z > 0 \right \}\] as a set of $ (n+1)^{3}-1$ points in the three-dimensional space. Determine the smallest possible number of planes, the union of which contains $ S$ but does not include $ (0,0,0)$. answer is 3n,isnt it

Yup, many people got the value and the example (including me), but failed to show it's the extreme value. I think this problem is as hard as yesterday's problem based on what I heard from the China IMO Team.

Let there be k planes: $ a_{1}x + b_{1}y + c_{1}z = d_{1}$, ...... $ a_{k}x + b_{k}y + c_{k}z = d_{k}$, and consider polynomial $ P(x,y,z) = (x + y + z)\prod_{i = 1}^{k}{(a_{i}x + b_{i}y + c_{i}z - d_{i})}$. We look at subsets of set {0,1,2,...,n} and there exists $ t_{1},t_{2},t_{3}$ such that $ t_{1} + t_{2} + t_{3} = k + 1$ such that coeficient of $ x^{t_{1}}y^{t_{2}}z^{t_{3}}\neq 0$ (if it's doesn't exists then $ t_{1} + t_{2} + t_{3}$ is smaller and we get sharper inequality). Using the Combinatorial Nullstellensatz we get condradiction unless $ k\geq 3n$. We can easily construct equaility case... This is solution of student from Serbia Marko

I haven't used the Nullstellensatz much, so I may just be missing something here, but where exactly does the contradiction arise? For example, why is it not possible that $ k=3n-1$ and $ t_{1}=2n-1, t_{2}=t_{3}=\frac{n}{2}$ (in which case the corresponding set $ S_{1}$ is too large to fit inside $ \{0, \dots n\}$)?

vedran6 wrote: Let there be k planes: $ a_{1}x + b_{1}y + c_{1}z = d_{1}$, ...... $ a_{k}x + b_{k}y + c_{k}z = d_{k}$, This solution was given by Radchenko Danylo, from the Ukraine team: Let $ P(x,y,z) = \prod_{i = 1}^{k}{(a_{i}x + b_{i}y + c_{i}z - d_{i})} - \alpha\prod_{j = 1}^{n}{(x - j)(y - j)(z - j)}$ where $ \alpha$ is choosen so that P(0,0,0)=0. Then, if $ k < 3n$ then coefficient at $ x^{n}y^{n}z^{n}$ is not zero, so from the Combinatorial Nullstellensatz it follows that for $ S_{1},S_{2},S_{3} = \{0,1,...,n\}$ There must be an $ x_{0}\in S_{1}, y_{0}\in S_{2}, z_{0}\in S_{3}$, so that $ P(x_{0},y_{0},z_{0}) \neq 0$. Contradiction.

This is a special case of a result of Alon and F\"uredi from 1993. It says that if $ n_{1},\ldots,n_{k}\geq 0$, then the minimal number of hyperplanes in $ \mathbb{R}^{k}$ needed to cover all but one points of the grid $ 0 \leq x_{i}\leq n_{i}$, $ 1 \leq i \leq k$, is $ n_{1}+\cdots+n_{k}$. This is proven in exactly the same way by the polynomial method. Another special case was discussed in the mathlinks forum long ago, where I showed the same solution: http://www.mathlinks.ro/viewtopic.php?search_id=1233358814&t=20525 . Strange then that this appeared on IMO, all the more that quite a lot of ML members know the combinatorial nullstellensatz from the numerous discussions here.

Well, you dont need CNS: Just consider the finite differences (P(x+1,y,z)-P(x,y,z) and similarly for y and z) and take it n times in each direction. by induction, you see that they are zero on rectangular parallelepipeds except for one vertex. thus, at the end, we get something nonzero on (0,0,0). on the other hand, if the degree was too small(less than 3n), it must be the zero polynomial(observe that finite differences decrease the degree by at least one). contradiction. Thus, i think the point with this problem is not CNS but the idea of writing down that polynomial. Knowing CNS doesnt really help.

Peter Scholze wrote: Knowing CNS doesnt really help. Except that it solves the problem as it becomes instantly clear which polynomial to write down . Really, what you wrote is essentially CN in slight disguise, without the redundant full generality (but I agree that a more adequate description would be "the polynomial method of Alon" instead of "the CN"). Has anyone found a combinatorial solution?

I have a simple combinatorial solution for the two-dimensional case, but I don't get it generalized to the three-dimensional case needed here. Maybe someone can help? My idea for the 2-D case is as follows. Let S_{m,n} be the (n,m)-"cube", ie, the collection of all pairs (x,y) with x in 0,1,...,m and y in 0, ..., n, but excluding (0,0), and let T_{m,n} be the boundary (all such points with x in {0,m} and y in {0,n}. So T_{m,n} has 2m+2n-1 points. Now consider a collection of "hyperplanes" (lines) not containing (0,0) and covering all points in S_{m,n}. We want to show that there are at least m+n lines needed. Now, if there is a line that covers more than two points from the boundary, then it is a boundary line, hence one of the two boundary lines through (m,n). In that case, the other lines lines cover S_{m,n-1} or S_{m-1,n}, and the desired result follows by induction. On the other hand, if all lines cover at most two boundary points, then there are at least (2m+2n-1)/2 lines, hence at least n+m lines. Can perhaps a similar idea work in 3-D?

I couldn't spent much time today on the problems but my idea was a recursion after proving it for two dimensions I think I got a solution in that direction but I'm gonna check it and post again tomorrow.

How about the cube with $ \{0,1,\dots,n+m\}$ without the cube with $ \{0,1,\dots,m-1\}$ and $ m\in \mathbb N$? Is it still $ 3n$ ?

mszew wrote: How about the cube with $ \{0,1,\dots,n+m\}$ without the cube with $ \{0,1,\dots,m-1\}$ and $ m\in \mathbb N$? Is it still $ 3n$ ? Probably yes... However, you need to adjust your notation slightly: to cover the cube with $ \{0,1,\ldots,n+m\}$ without the cube with $ \{0,1,\ldots,m\}$, you need(?) at least $ 3n$ planes. The CN argument can be modified to show that you need at least $ 3n-3m$ planes, which is probably not sharp unless $ m=0$ (the original problem). More generally, to cover an $ n_{1}\times \cdots \times n_{k}$ grid without an $ \ell_{1}\times \cdots \times \ell_{k}$ subgrid, one needs at least $ \sum_{i=1}^{k}\max (n_{i}-2\ell_{i}+2, 0)$ hyperplanes. Perhaps this bound may be improved to $ \sum_{i=1}^{k}(n_{i}-\ell_{i}+1)$ in the case that each $ n_{i}> \ell_{i}> 0$, but I can't show this at the moment. Let me demonstrate the version with $ 3n$ and $ 3$ dimensions (the general case being only notationally different). Let $ a_{i}x+b_{i}y+c_{i}z = d_{i}$ be the planes, $ 1 \leq i \leq s$; and suppose $ s < 3n-3m$. Let $ P(x,y,z) : = \prod_{i=1}^{s}(a_{i}x+b_{i}y+c_{i}z-d_{i})$, and let $ Q(x,y,z)$ be the polynomial, of degree $ \leq m$ in each variable $ x,y,z$, obtained from $ P(x,y,z)$ modulo the relations $ \prod_{j=0}^{m}(x-j) = \prod_{j=0}^{m}(y-j) = \prod_{j=0}^{m}(z-j) = 0$ (that is, we replace successively each $ x^{m+1},y^{m+1}, z^{m+1}$ with linear combinations of smaller powers using these relations, until there is no monomial left with partial degree $ > m$). By construction, $ Q(x,y,z) = P(x,y,z)$ for $ x,y,z \in{0,\ldots,m}$. Let as well $ R(x,y,z)$ be the polynomial, again of degree $ \leq m$ in each variable, obtained from the polynomial $ S(x,y,z) : = \prod_{j=m+1}^{n+m}(x-j)(y-j)(z-j)$ modulo these same relations. Once again, $ S(x,y,z)$ and $ R(x,y,z)$ take the same values on $ \{0,\ldots,m \}^{3}$. Consider the polynomial $ T(x,y,z) : = P(x,y,z) R(x,y,z)-Q(x,y,z)S(x,y,z)$. The first summand, $ PR$, has total degree $ s+\deg{R}= s+3m < 3n = \deg{S}\leq \deg{QS}$, and in $ QS$ the partial degrees in $ x,y,z$ are all $ \leq n+m$. The contradiction follows from the combinatorial nullstellensatz, since $ T(x,y,z)$ vanishes identically on $ \{0,1,\ldots,n+m\}^{3}$. The question you pose remains open to me, but [needless to say] I might well have missed the key that could make your question an easy prey to a modified CN argument.

In another thread, Darij implied that a solution using Combinatorial Nullstellensatz would obtain only 1 point. Is this true (readers' opinion, of course)? If his claim is true, would providing a proof of Combinatorial Nullstellensatz during the exam obtain 7 points (if there are no mistakes)? I am curious if/how such theorems are accepted during such competitions. Also, I would like to express my opinion about this problem; In my opinion, this is a very beautiful problem, but knowing this theorem trivializes it.

It seems that approaching the plane case will not give the student any points (unless he can somehow successfully relate it with the 3-dimensional case).

boxedexe wrote: In another thread, Darij implied that a solution using Combinatorial Nullstellensatz would obtain only 1 point. Is this true (readers' opinion, of course)? If his claim is true, would providing a proof of Combinatorial Nullstellensatz during the exam obtain 7 points (if there are no mistakes)? Surely, if you prove everything you use during the exam (e.g. a clean proof of the combinatorial nullstellensatz, but not the full version is needed), you'll obtain 7 points . You might initially solve the problem with CN (rather: note that it's a direct consequence), and then describe the polynomial proof in such self-contained manner as to even leave no sign that you knew the theorem. (E.g. as in Peter's proof above). About demonstrating that this problem is a consequence of a theorem called combinatorial nullstellensatz (and stating that theorem), I wouldn't be surprised if you receive just 1 point (probably this is what is going to happen; those people there are very jealous about theorems trivializing their problems... ). But that would be a stupid thing to do: if you knew that CN does it, why not at least sketch a proof of CN? (this is problem 6 on IMO, after all...) Or, if you don't remember a proof or don't want to mention CN, you at least know that the problem admits an algebraic solution, and you know which polynomial to consider to obtain a contradiction -- and may be able to carry the idea to a self-contained solution avoiding explicit mention of CN -- again, such is Peter's solution above (and I suspect that the authors' solution is along similar lines, if not exactly the same! For this is simply an algebraic combinatorics problem, it is the way it was created! ) The comment in the brackets restrains me from admiring such problem at IMO. Not only it is merely a special case of the algebro-combinatorial result of Alon and Furedi stated above in this thread, but a similar problem was stated and solved on this forum in the link I provided above! It is my opinion that there may well not be a natural combinatorial solution.

boxedexe wrote: In another thread, Darij implied that a solution using Combinatorial Nullstellensatz would obtain only 1 point. I didn't say this! I said that the things I had done (generalizing to rectangular parallelpipeda instead of cubes, proving it in the 2D case, and writing "looks like Cauchy-Davenport" on the scratch paper) are likely to get you 1 point. But this seems to be not the case. Darij

I think anyone that solves the problem (using CN or not) should get 7 points. Knowledge should be rewarded. It is not the fault of the competitors that the Committee made such a poor choice in the problem selection phase. Whether they knew about CN or they did not know about it, it seems that choosing the problem was their error in either case.

I have two separate comments. 1. shunka wrote: I think anyone that solves the problem (using CN or not) should get 7 points. Knowledge should be rewarded. It is not the fault of the competitors that the Committee made such a poor choice in the problem selection phase. Whether they knew about CN or they did not know about it, it seems that choosing the problem was their error in either case. I agree completely. However, I think that, in reality, if you use CN as frivolously as you use, e.g., the cosine theorem in a geometry problem, they're going to reward you with 1 or 2 points (problems 3 & 6 are usually graded harsher on IMOs then the other problems). Absolutely this problem is a poor choice by the Committe. The more I think about a combinatorial approach, the more I realize that this is totally not a combinatorial problem: it was invented (i.e. discovered) in 1993 (Alon - Furedi) as an application of the (algebraic) polynomial method of N. Alon, and I don't believe that it has a combinatorial meaning, at least in the general case (for the 3-D case the proposers may have found a combinatorial solution, I don't know yet; but I doubt it would generalize. I actually find it quite likely that all known proofs are algebraic!). Those planes and their incidence with the lattice points have absolutely no "natural" combinatorial meaning, which is why this problem is so difficult to organize combinatorially ad hoc. Some people call such problems algebro-combinatorial, some put them in the realm of combinatorial geometry (both are reasonable: the known solutions are algebraic, while the objects of study, planes and integral points on them, are geometric)... And some would call such problems artificial. But [or moreover] such questions abound in the literature on combinatorial geometry/combinatorial group theory/algebraic combinatorics. This is not a generalization, but a (more interesting, actually) finite analog: for a finite abelian group $ A$ with identity $ 0$, what is the minimal number of cosets [of subgroups $ H < A$] whose union is $ A \setminus \{0\}$? For the answer and proof, and similar questions, here is an interesting article for the interested reader: http://www.citebase.org/fulltext?format=application%2Fpdf&identifier=oai%3AarXiv.org%3Amath%2F0411244 . 2. Above was proposed the following generalization for which I proved a weaker version: To cover the cube with $ \{0,1,\ldots,n+m\}$ without the cube with $ \{0,1,\ldots,m\}$, we need at least 3n planes. I showed that we need at least $ 3(n-m)$ planes. But actually, the proof shows more: Suppose that: (1) we have covered all points of the cube with $ \{0,1,\ldots,n+m\}$ except possibly some points of the cube with $ \{0,1,\ldots,m\}$; and (2) we have not covered at least one point of the cube with $ \{0,1,\ldots,m\}$. Then we have used at least $ 3(n-m)$ hyperplanes. Similarly for the obvious generalization. Indeed, all that we used about the polynomial $ Q$ constructed in the proof that it was not the zero polynomial. This follows from the assumption that $ Q$ does not vanish on the cube with $ \{0,1,\ldots,m\}$. But it suffices to assume that $ Q$ does not vanish at just one point to reach the conclusion. Again, this is probably not sharp in general. That said, I believe one can prove the sharp result conjectured by mszew as follows. I use the notation for my proof of the special case above. Instead of constructing $ Q$ and $ R$ as we did, construct ("kinds of inverses") polynomials $ Q, R$ of partial degrees all $ \leq m$ as follows: (i) $ PQ$ takes the value $ 1$ on the cube with $ \{0,1,\ldots,m\}$ (here we use with full force that $ P$ does not vanish on this cube, i.e. that the union of our planes is exactly the cube with $ \{0,1,\ldots,n+m\}$ minus the cube with $ \{0,1,\ldots,m\}$); and $ RS$ as well takes the value $ 1$ identically on the cube with $ \{0,1,\ldots,m\}$. Then $ R$ is a concrete polynomial (with concrete coefficients independent of the given covering), because $ S : = \prod_{j = m+1}^{n+m}(x-j)(y-j)(z-j)$ is. And I think we may show that the coefficient of $ (xyz)^{m}$ in $ R(x,y,z)$ is nonzero. If this is the case, then we may apply CN to the polynomial $ PQ-RS$ and conclude the proof! Thus, modulo my computational claim, we have two different generalizations of the initial problem, still in dimension $ 3$ and with cubes rather than general parallelepipeds! But the generalizations to such questions are countless.

darij grinberg wrote: boxedexe wrote: In another thread, Darij implied that a solution using Combinatorial Nullstellensatz would obtain only 1 point. I didn't say this! I said that the things I had done (generalizing to rectangular parallelpipeda instead of cubes, proving it in the 2D case, and writing "looks like Cauchy-Davenport" on the scratch paper) are likely to get you 1 point. But this seems to be not the case. Darij Sorry, it seemed to me that you were implying that a solution using such a theorem would obtain 1 point. Apparently, I misunderstood what you wrote.

http://www.imo2007.edu.vn/images/Category/Category_1610107.JPG Well, it looks like that the intended solution is the CN-motivated one. No surprise there ...

Im PER1, today, i knew that i have 0 in question 6; back to the problem, i find my mistake and now i present the combinatorial solution: Induction on $ m+n+p$:"If S={(x,y,z), such that $ 0\leq x\leq m$;$ 0\leq y\leq n$;$ 0\leq z\leq p$,$ x+y+z>0$}, then is neccesary $ m+n+p$ planes that cover S but not O(0,0,0)". Prove: If $ m+n+p=1$, is trivial. Suposing that for $ m+n+p=N$, is true, then for a configuration with $ m+n+p=N+1$, we have: Denote $ A, B, C$ the corners of the parallelepiped, and let $ A_{1}, B_{1}, C_{1}, O_{1}$ their respectives opposite corners of $ A,B,C,O$. There are at least n planes "cutters" that cut OB(if two points of OB and S are in a plane, then O belong to the plane). We take a plane "cutter" by each one of this points(of OB and S) Consider the figure G formed for the points of S, such that $ x=0, x=m, z=0, z=p$, as 2m+2p rows of (n+1) poimts, for each plane "cutter" and each row(distinct to OB), at most they share a point(Either, O belongs to the plane), then we can chose a point of every row(distinct to OB) which not belong to this n planes "cutters", and denote this points as "cheveres points". If a plane is O_1B_1AC_1, we are done by the inductive hippotesis, similarly, if a plane is O_1B_1CA_1. Either, each plane parallel to OB have at most 2 "cheveres points", then there are at least $ m+p(=[(2m+2p-1)/2])$ planes parallel to OB, hence is neccesary $ m+n+p=N+1$ planes for cover S but not O. Finally is sufficient m+n+p planes, consider the plnes:P_r={x+y+z=r}, 0<r<=m+n+p. For m=n=p, the answer is 3n.

There appears to be a flaw in your argument: You first consider n plane "cutters" and the "cheveres points" that the imply. However, you forget that there might be additional plane "cutters" that could contain quite a few of those "cheveres points". Note that my solution directly solves the more general problem given here, in the generalized form: Suppose that: (1) we have covered all points of the cube with $ \{0,1,\ldots,n+m\}$ except possibly some points of the cube with $ \{0,1,\ldots,m\}$; and (2) we have not covered at least one point of the cube with $ \{0,1,\ldots,m\}$. Then we have used at least $ 3n$ hyperplanes. Similarly for the obvious generalization.

billzhao wrote: http://www.imo2007.edu.vn/images/Category/Category_1610107.JPG Well, it looks like that the intended solution is the CN-motivated one. No surprise there ... Thanks, Yufei, for pointing this out. That makes it impossible for those who don't know CN to solve the problem. A problem is bad if it places the contestants in unequal situation. I think this is not olympic-type problem, it is rather guess-what-I-am-thinking problem.

Let's look at the planes introducted from anywhere but not of origin (in fact, any of these planes must pass through based on a condition of the problem) and let's take projections of these planes on to a plane one from x-y, y-z or x-z planes. Denote by n(d) the number of the points of the set S the plane d passes through. Then n(f(n +1) - f(n)) <=(2n +4)/3 over this projection obviously (if it is not obvious then induct on n easily gives the result we want) then it is okay that f is a second degree polynomial (because informs the number of the introductory points this plane has depending on the variable k). So f(n) <=(n^2)/3 +n +1.

We know and conclude easily that number of sets is determined Sum(S)/f(n) and it is >= 3n so the minimum number of the planes is 3n openly.

vess: I think you are making mszew's ques harder. To cover {0,1,……,n+m} without {0,1……m-1} means(necessarily) to cover {m-1,m,m+1,…m+n} without {m-1}. As already shown, the least num is 3(n+1). But these 3n+3 planes can be easily found, they are x,y,z=m,m+1……n+m

I think it is a very hard problem I like this problem and its solution it is nice I saw a problem a few days ago: "Let n be a positive integer. Consider S={(x,y):-1<x,y<n+1 x,y are integer} as a set of (n+1)^2-1 points in the two- dimensional space. Determine the smallest possible number of lines, the union of which contains S but does not include (0,0)." It can be proven by induction but its generalized from m,n and we induct on (m+n).I think this problem is nice too.

In case D.Radchenko didn't write the proof of cns and just quoted it, the fact that he recieved 7pts for the problem would imply it's totally ok to use this theorem without proving it - so I wonder if anyone knows or if he himself is around

Here is a proof that looks simpler that the official solution, even though it uses the same principle. It is similar to a 'A short proof of Combinatorial Nullstellensatz' given by Mateusz Michalek. I'd be really grateful if someone could check this for mistakes. Let $n_1, \ldots, n_d \in \mathbb{N}$. Let \[S(n_1, \ldots, n_d) = \{(x_1, \ldots, x_d)\, | \, 0 \leq x_i \leq n_i,\, x_1 + \ldots + x_d > 0\}.\]Consider a polynomial $P$ that solves $S(n_1, \ldots, n_d)$, that is, $P(x_1, \ldots, x_d) = 0$ for all $(x_1, \ldots, x_d) \in S$ and $P(0, \ldots, 0) \neq 0$. We show by induction that $\deg(P) \geq n_1 + \ldots + n_d$. Assume w.l.o.g. that $n_1 > 0$. Apply polynomial division to write \[P = P'(x_1 - n_1) + R,\]such that $\deg(R) \leq \deg(P)$ and $R$ does not contain $x_1$. It is easy to see that \[R(x_1, \ldots, x_n) = R(n_1, x_2, \ldots, x_n) = P(n_1, x_2, \ldots, x_n).\]This means that $R(x_1, \ldots, x_d) = 0$ for all $(x_1, \ldots, x_d) \in S(n_1, \ldots, n_d) \cup \{0\}$. Clearly then $P'$ solves $S(n_1 - 1, \ldots, n_d)$. By induction we are done since \[\deg(P) \geq \deg(P - R) = \deg(P'(x_1 - n_1)) = \deg(P') + 1.\]

I realized that my solution is the same as https://artofproblemsolving.com/wiki/index.php?title=2007_IMO_Problems/Problem_6

How about a slightly twisted version of this problem: what if you remove all internal points of the cube and disallow any plane to cover a whole face? What is the minimal number of planes then? Looks like the polynomial solution might not work any more: it is trivial to show that the number is still 2n in 2 dimensions, and yet you can easily come up with a polynomial of a smaller degree that covers all of the external points (think circles). So what do we do now?

Not sure if that's in the spirit of the forum, but I'd offer a generous bounty for a solution of the twisted version above. Just get in touch with me directly.

Peter Scholze wrote: There appears to be a flaw in your argument: You first consider n plane "cutters" and the "cheveres points" that the imply. However, you forget that there might be additional plane "cutters" that could contain quite a few of those "cheveres points". Note that my solution directly solves the more general problem given here, in the generalized form: Suppose that: (1) we have covered all points of the cube with $ \{0,1,\ldots,n+m\}$ except possibly some points of the cube with $ \{0,1,\ldots,m\}$; and (2) we have not covered at least one point of the cube with $ \{0,1,\ldots,m\}$. Then we have used at least $ 3n$ hyperplanes. Similarly for the obvious generalization. This is the Field Medalist

We claim the answer $3n$. As an example take a union of planes $x+y+z=c$ for $c=1,2,\dots ,3n.$ Assume FTSOC that planes $a_ix+b_iy+c_iz+d_i=0$ for $i=1,2,\dots ,k<3n$ cover $S;$ consider polynomial $$P(x,y,z)=(x+y+z)\prod_{i=1}^{k} (a_ix+b_iy+c_iz+d_i)$$and set $\mathcal A=\left \{ 0,1,2,\dots ,n\right \} .$ Since $d_i\neq 0,$ at least one monom $x^py^qz^r$ of $P$ (with $p+q+r\leq k+1$) has a nonzero coefficient, hence by the Combinatorial Nullstellensatz there exist $s_{1,2,3}\in \mathcal A$ such that $P(s_1,s_2,s_3)\neq 0.$ Since $P(0,0,0)=0,$ we get the obvious contradiction, as desired.

The answer is $3n$. For the construction, use the planes $x=1, 2, \ldots, n$, $y=1, 2, \ldots, n$, and $z=1, 2, \ldots, n$. Now we show that no number of planes $k<3n$ works. Assume for contradiction that a configuration with $k<3n$ planes exists. Let these planes be $a_ix + b_iy + c_iz + d_i=0$ for $1 \le i \le k$. Define \[ f(x, y, z) = \prod_{i=1}^k (a_ix + b_iy + c_iz + d_i) \ \text{and} \ g(x, y, z) = \prod_{i=1}^n (x-i) \prod_{i=1}^n (y-i) \prod_{i=1}^n (z-i). \]Furthermore, let \[ P(x, y, z) = f(x, y, z)-\frac{f(0, 0, 0)}{g(0, 0, 0)} g(x, y, z). \]Note that $P$ vanishes on $\{0, 1, \ldots, n\}^3$. However, the coefficent of $x^ny^nz^n$ in $P$ is $-\frac{f(0, 0, 0)}{g(0, 0, 0)}$ which is nonzero, so the combinatorial Nullstellensatz yields a contradiction, which completes the proof.

50 mohs simulator. Claim: A construction with $3n$ planes works. Proof. Taking $x + y + z = i$ for $i = 1, 2, \dots, 3n$ works. Taking $x = i, y = i, z = i$ for $i = 1, 2, \dots, n$ does as well. $\blacksquare$ Claim: $3n$ is optimal. Proof. FTSOC there exists a construction with $N < 3n$ planes. Let the planes be of the form $a_ix + b_iy + c_iz + 1 = 0$. Define \begin{align*} A(x,y,z) &= \prod_{i=1}^n (x-i)(y-i)(z-i) \\ B(x,y,z) &= \prod_{i=1}^N \left( a_i x + b_i y + c_i z + 1 \right). \end{align*}Both of these polynomials vanish entirely on $S$ with $A(0, 0, 0) = (-1)^{n} (n!)^3$ and $B(0, 0, 0) = 1$. However, then $A - (-1)^{n} (n!)^3 \cdot B(0, 0, 0)$ is nonzero, and vanishes on all of $\{0, 1, \dots n\}^3$, contradiction of combinatorial nullstellensatz since it has nonzero coefficient $x^ny^nz^n$. $\blacksquare$

Answer is $3n$. FTSOC assume that there are $p < 3n$ planes. Then let polynomials $P_1(x, y, z) = \prod_{i=1}^p (a_ix + b_iy + c_iz + 1)$ where $a_ix + b_iy + c_iz + 1 = 0$ determines the planes in question. Then let $P_2(x, y, z) = \prod_{i=1}^k (x-i)\prod_{i=1}^k (y-i)\prod_{i=1}^k (z-i)$. Note that both $P_1$ and $P_2$ vanish completely on $S$. Clearly both $P_1(0, 0, 0)$ and $P_2(0, 0, 0)$ are nonzero. So then $P(x, y, z) = P_1(x, y, z) - \frac{P_1(0,0,0)}{P_2(0,0,0)} \cdot P_2(x,y,z)$ has total degree of less than $3n$, and it vanishes completely over $T^3$ where $T = (0, 1, \dots, n)$. Then Combinatorial Nullstellensatz gives us that $P(x,y,z)$ has no nonzero terms, which is a contradiction as $P_1$ and $P_2$ both have a nonzero ending coefficient of $1$ and $(-1)^n \cdot n!$ respectively so we have proved the bound. For our construction, just take $3n$ planes, split into $n$ groups of planes that are parallel to the $XY$, $XZ$, and $YZ$ planes passing through $(0, 0, 0)$. It is easy to arrange the planes so that they pass through all of $S$ so we are done.

I really like the official "normal" solution (if almost everyone preferred the comb null solution, then I doubt this is that normal) . In any case, here we go. Define $P$ in the same way as everyone else, while notice that $P(0, 0, 0) \neq 0$, and assume that $\deg{P} < 3n$. Let $P(x, y, z) = \sum_{\alpha+\beta+\gamma < 3n}p_{\alpha,\beta,\gamma}x^{\alpha}y^{\beta}z^{\gamma}$. Now consider the sum \begin{align*} \sum_{i=0}^{n} \sum_{j=0}^{n} \sum_{k=0}^{n} (-1)^{i+j+k} \binom{n}{i} \binom{n}{j} \binom{n}{k} \sum_{\alpha+\beta+\gamma \leq N} p_{\alpha,\beta,\gamma} i^{\alpha} j^{\beta} k^{\gamma} \end{align*}Notice this has to evaluate to $P(0, 0 ,0) \neq 0$ as every other term is $0$. However, turns out that you can compute this as \[\sum_{\alpha+\beta+\gamma \leq N} \left( \sum_{i=1}^{n}(-1)^{i}\binom{n}{i}i^{\alpha}\right) \left( \sum_{j=1}^{n}(-1)^{j}\binom{n}{j}j^{\beta} \right) \left( \sum_{k=1}^{n}(-1)^{k}\binom{n}{k}k^{\gamma} \right)\]which is always $0$, because one of $\alpha$, $\beta$, $\gamma$ will be less than $n$, say it is $\alpha$, and so is well known $\sum_{i=1}^{n}(-1)^{i}\binom{n}{i}i^{\alpha} = 0$. Which is a contradiction. $\Box$