Another problem, this time from the IMO, that we can kill by Combinatorial Nullstellensatz:
I claim the minimum is
planes, and a configuration exists for
- just consider the set of planes that are of the form
, where
is an integer from
to
.
We now show no configuration exists for less than
planes, and we do so by contradiction. Suppose we do have a set of planes
such that
. Now consider the
polynomialRemember that Combinatorial Nullstellensatz depends solely on a well-chosen polynomial. Using the notation of the statement of Combinatorial Nullstellensatz, we want a polynomial of degree
, and sets
, 
, 
. Our sets
satisfy the preconditions of the lemma so far.
However, we want to make
, our polynomial, zero on all points in
. There are two ways we could do this. One is simply considering the product
. This would make it zero on all points except when
. We'll get to how to deal with this later.
The other way to consider this is if we have a product of all the plane equations. Suppose each element in
is of the form
(the equation of the plane), and our product is
. This is zero on all
, but not
. Therefore
is nonzero.
The key here is that our polynomial must equal zero at
, otherwise, we may not have a contradiction. So we multiply
by
, which makes the polynomial
our desired polynomial that satisfies all the conditions of Combinatorial Nullstellensatz. (Note that
and is defined, because
and
are non-zero, so we don't have problems.
such that
where each element
in
is of the form
, or the equation of the plane
, and
is some constant, non-zero, such that
for all
.
Consider the term
. Since the second product has degree less than
, no terms of this sort arise as a result of this product. Thus, we need only consider the first product. The product itself produces the monic term
but is then multiplied by
. Therefore the coefficient is
, but this is non-zero. By Combinatorial Nullstellensatz,
for some
, creating a contradiction.
Therefore the set of planes
has
, and hence
is our minimum number of planes.
Credit is where credit is due - adamov1 helped me through this problem over Thanksgiving break after trying my hand at it for a solid two hours. It turns out I was missing the crucial first product in the polynomial so it would be zero at the origin. Thanks adamov1!
Speaking of which, Thanksgiving break! I attended one of those aptly named "Asian parties" in the US where we stuffed ourselves with turkey and stuff. Don't worry, rest of the world. It's one of those weird American things we do.
by agbdmrbirdyface, Nov 28, 2016, 3:05 AM 
be a positive integer. Consider ![\[S=\{(x,y,z)~:~x,y,z\in \{0,1,\ldots,n \},~x+y+z>0\}\]](//latex.artofproblemsolving.com/0/9/3/093e2981f00291b1f43718a1442f9967e2df0a27.png)
as a set of 
points in three-dimensional space. Determine the smallest possible number of planes, the union of which contain 
be a positive integer. Consider ![\[S=\{(x,y,z)~:~x,y,z\in \{0,1,\ldots,n \},~x+y+z>0\}\]](http://latex.artofproblemsolving.com/0/9/3/093e2981f00291b1f43718a1442f9967e2df0a27.png)
as a set of 
points in three-dimensional space. Determine the smallest possible number of planes, the union of which contain 
but does not include 
.
planes, and a configuration exists for 
,
is an integer from 
to 
such that 
.
,
,
,
.
satisfy the preconditions of the lemma so far.
,
.
.
is of the form 
(the equation of the plane), and our product is 
.
is nonzero.
by 
,
our desired polynomial that satisfies all the conditions of Combinatorial Nullstellensatz. (Note that 
and is defined, because 
and 
are non-zero, so we don't have problems.
where each element 
in 
is some constant, non-zero, such that 
for all 
.
.
for some 
,
,
May 2017
April 2017