The Return of Combinatorial ... something idk
by agbdmrbirdyface, Nov 28, 2016, 3:05 AM
Another problem, this time from the IMO, that we can kill by Combinatorial Nullstellensatz:
Solution:
Tidbit
IMO 2007/6 wrote:
Let
be a positive integer. Consider
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
.

![\[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)



Solution:
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 polynomial
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.






We now show no configuration exists for less than



Remember 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.





However, we want to make




The other way to consider this is if we have a product of all the plane equations. Suppose each element in






The key here is that our polynomial must equal zero at
















Consider the term







Therefore the set of planes



Tidbit
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.
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.