\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{Shortlist 2003 N8}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 37}
\maketitle

\section*{Problem}
Let $p$ be a prime number and let $A$ be a set of positive integers
that satisfies the following conditions:
\begin{enumerate}
\ii[(i)] the set of prime divisors of the elements in $A$ consists of $p-1$ elements;
\ii[(ii)]  for any nonempty subset of $A$,
the product of its elements is not a perfect $p$-th power.
\end{enumerate}
What is the largest possible number of elements in $A$ ?

\section*{Video}
\href{https://www.youtube.com/watch?v=0Ax32Q0Z0Ho&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/0Ax32Q0Z0Ho}}

\section*{External Link}
\url{https://aops.com/community/p119994}

\newpage

\section*{Solution}
Let $D = p-1$.
Then the question (thinking in terms of the exponents)
can be phrased as follows:
\begin{quote}
  What's the largest multiset of vectors in $\FF_p^{D}$
  such that no nonempty subset has zero sum?
\end{quote}

We claim the answer is $D \cdot (p-1)$.
A construction is given by taking
\begin{itemize}
\ii $p-1$ copies of the vector $\left< 1, 0, \dots, 0\right>$;
\ii $p-1$ copies of the vector $\left< 0, 1, \dots, 0\right>$;
\ii \dots;
\ii $p-1$ copies of the vector $\left< 0, 0, \dots, 1 \right>$.
\end{itemize}
To show it's best possible,
suppose we have vectors $v_1$, \dots, $v_N$ with coordinates given as
\[ v_k = \left< v_{k,1}, v_{k,2}, \dots, v_{k,D} \right>
  \qquad k = 1, 2, \dots, N.  \]
Then, we construct the polynomial
\[
  F(X_1, \dots, X_N)
  = \prod_{i=1}^D
  \left[ 1 - \left( \sum_{k=1}^N X_k v_{k,j} \right)^{p-1} \right]
  - \prod_{i=1}^N (1-X_i)
\]
If we imagine the $X_i \in \{0,1\}$ as Bernoulli random variables
indicating whether $v_k$ is used in a set or not,
then $F(X_1, \dots, X_N) \neq 0$
exactly when the $X_i$'s equal to $1$ correspond to a nonempty subset
of the vectors which have vanishing sum.

Now assume for contradiction $N < D \cdot (p-1)$.
Then the largest degree term is given in the latter product;
it is exactly $(-1)^{N+1} X_1 X_2 \dots X_N$.
So if we quote Alon's combinatorial nullstellensatz,
it now follows that there is a choice of $X_i \in \{0,1\}$
such that $F(X_1, \dots, X_N) \neq 0$ which is a contradiction.

\end{document}
