IMO ShortList 2003, number theory problem 8

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

IMO ShortList 2003, number theory problem 8

G H J

Reveal topic tags

modular arithmetic

L

G H BBookmark kLocked kLocked NReply

Source: IMO ShortList 2003, number theory problem 8

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3647 posts

orl

#1 h Oct 4, 2004, 9:46 PM • 2 Y

Y by Adventure10, Mango247

Let $p$ be a prime number and let $A$ be a set of positive integers that satisfies the following conditions:

(i) the set of prime divisors of the elements in $A$ consists of $p-1$ elements;

(ii) for any nonempty subset of $A$ , the product of its elements is not a perfect $p$ -th power.

What is the largest possible number of elements in $A$ ?

Attachments:

This post has been edited 1 time. Last edited by djmathman, May 27, 2018, 3:55 PM
Reason: adjusted wording according to https://anhngq.files.wordpress.com/2010/07/imo-2003-shortlist.pdf

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3647 posts

orl

#2 h Oct 4, 2004, 10:09 PM • 2 Y

Y by Adventure10, Mango247

Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2043 posts

Zhero

#3 h Jul 22, 2010, 4:36 PM • 4 Y

Y by huricane, mijail, Adventure10, Mango247

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6906 posts

#4 h Feb 22, 2021, 9:18 PM • 8 Y

Y by SK_pi3145, Mathematicsislovely, mijail, PIartist, guptaamitu1, HamstPan38825, Ru83n05, starchan

Solution from Twitch Solves ISL:

Let $D = p-1$ . Then the question (thinking in terms of the exponents) can be phrased as follows:

What's the largest multiset of vectors in ${\mathbb F}_p^{D}$ such that no nonempty subset has zero sum?

We claim the answer is $D \cdot (p-1)$ . A construction is given by taking

$p-1$ copies of the vector $\left< 1, 0, \dots, 0\right>$ ;
$p-1$ copies of the vector $\left< 0, 1, \dots, 0\right>$ ;
\dots;
$p-1$ copies of the vector $\left< 0, 0, \dots, 1 \right>$ .

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Math_Is_Fun_101

159 posts

Math_Is_Fun_101

#5 h Oct 13, 2021, 7:49 AM • 2 Y

Y by Derfu37, guptaamitu1

Solution with derfu37 and a hint to use Chevalley's from Al3jandro0000.

We claim the answer is $(p-1)^2$ . This is achievable by taking the set
$A = \{ q_i^{pj+1}\vert(i,j)\in\{1,\ldots,p-1\}^2 \}$ where $\{q_i\}_{i=1}^{\infty}$ is the sequence of primes. Now we show $|A|>(p-1)^2$ is impossible. Let $n=|A|$ . Note that by condition (i) we can represent the elements of $A$ as vectors in $\mathbb F_p^{p-1}$ . Let these be
$v_i = (e_{i1},\ldots,e_{i(p-1)})\text{ for } 1\le i\le n.$ Now, we define $f_j\colon\mathbb F_p^n\rightarrow\mathbb F_p^n$ as
$f_j(x_1,\ldots,x_n) = \sum_{i=1}^n x_i^{p-1}e_{ji}.$ Consider the system of equations $f_j(x_1,\ldots,x_n)=0$ for $1\le j\le p-1$ . Note that $(0,\ldots,0)$ is a trivial solution. Suppose for the sake of contradiction that $n>(p-1)^2$ . Then, we have
$n>(p-1)^2=(p-1)\cdot(p-1)=\sum_{j=1}^{p-1}\deg(f_j).$ Thus, quoting Chevalley's Theorem there must exist a nontrivial solution to the system. However, since $x_i^{p-1}\in{0,1}$ , this nontrivial solution specifies a nonempty subset of $A$ for which the product is a perfect $p-$ th power, yielding the desired contradiction. $\blacksquare$

This post has been edited 3 times. Last edited by Math_Is_Fun_101, Oct 13, 2021, 7:51 AM
Reason: Mispelled Chevalley's

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

577 posts

#6 h Mar 31, 2023, 10:03 PM

Y by

One can easily rephrase this problem using the prime factorizations of the elements of $A$ ; this asks for the size of the largest multiset of vectors of $\mathbb{F}_p^{p-1}$ where no nonempty subset has a sum of zero.

The answer is $(p-1)^2$ ; this can be obtained by taking $\bigcup_{\textbf{x}\in \mathbb{F}_p^{p-1} \\ |\textbf{x}|=1}\{\textbf{x} \ \text{repeated} \ p-1 \ \text{times}\}.$ Assume for contradiction that there is a solution of vectors $v_1, \ldots, v_N$ with $N>p-1$ that works, where we write $v_i = (e_{i1},\ldots,e_{i(p-1)})$ for each $i$ . Now define $f_k(x_1,\ldots,x_N) = \sum_{i=1}^N x_i^{p-1}e_{ki}$ for all $1 \le k \le p-1$ . Since $(0, \ldots, 0)$ is a common root of all $f_k$ , the Chevalley-Warning theorem guarantees a nontrivial root common to all $f_k$ . By Fermat's Little Theorem, each $x_i^{p-1}$ is either $0$ or $1$ , so there is a nonempty subset of $\{v_1, \ldots, v_N\}$ with a zero sum by using this nontrivial root, a contradiction. Hence $(p-1)^2$ is the size of the largest multiset of vectors of $\mathbb{F}_p^{p-1}$ where no nonempty subset has a sum of zero, and we are done.

This post has been edited 4 times. Last edited by Leo.Euler, Apr 11, 2023, 3:30 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8904 posts

#7 h Apr 13, 2023, 11:43 PM

Y by

Chevalley-Warning essentially nukes this.

The answer is $(p-1)^2$ . For construction, pick primes $q_1, q_2, \cdots, q_{p-1}$ , and use $q_1, q_1^{p+1}, \cdots, q_1^{1+p(p-2)}$ and similarly for the other $q_i$ 's. This obviously satisfies both conditions.

For the proof of maximality, set the $q_i$ to be the same and choose $k = (p-1)^2 + 1$ distinct elements from $A$ , which we will label $x_1$ through $x_k$ . For each $j$ , let $e_{ij}$ be the exponent of $q_i$ in $x_j$ .

Now, for the polynomials $f_i(X_1, \cdots, X_k) = X_1^{p-1}e_{i1} + X_2^{p-1}e_{i2} + \cdots + X_k^{p-1} e_{ik},$ by Chevalley-Warning there exists a nontrivial solution to the system $f_1(x_1, x_2, \cdots, x_k) \equiv f_2(x_1, x_2, \cdots, x_k) \equiv \cdots \equiv 0 \pmod p.$ Pick a subset $B$ of all nonzero $x_i$ in this set that satisfy the condition. Then by definition and Fermat's Little Theorem it follows that $\sum_{j \in B} e_{ij} \equiv 0 \pmod p$ for each $i$ , thus the product of the elements in $B$ is a perfect $p$ th power, contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1306 posts

#8 h May 31, 2023, 4:48 AM

Y by

Claim: If $x_j = (x_{j,1},\cdots, x_{j,n}) \in (\mathbb{Z}/p\mathbb{Z})^n$ ( $j\in \{1,\cdots,K\}$ ) such that for all $e_1, \cdots, e_K \in \{0,1\}$ (not all zero), then $\sum e_jx_j \ne 0$ . Then $K\le n(p-1)$ (this bound is optimal because I can have $p-1$ copies of $(\underbrace{0, \cdots, 0}_{j}, 1, \underbrace{0, \cdots, 0}_{n-1-j})$ for $j=0,\cdots,n-1$ )

Proof: Assume $K\ge n(p-1)+1$ . Consider the polynomial

$P(f_1, \cdots, f_K) = \prod\limits_{j=1}^n (1-(\sum_{k=1}^K f_kx_{k,j})^{p-1})$
If $\sum e_jx_j \ne 0 \iff$ there exists $t$ such that $\sum_k e_k x_{k,t} \ne 0$ . Then $1-(\sum_k e_k x_{k,t})^{p-1}=0$ in $\mathbb{Z}/p\mathbb{Z}$ . Hence $P(f_1,\cdots,f_K)=0$ for all $f_1,\cdots,f_k \in \{0,1\}$ that are not all zero, and $P(0,\cdots,0)=1$ .

We first flatten the polynomial i.e. replace $f_k^j$ with $f_k$ when $j\ge 2$ (i.e. we take this polynomial and take its remainder mod $f_1^2-f_1, f_2^2-f_2, \cdots, f_K^2-f_K$ ). Call this polynomial $\tilde P$ . Now note $\tilde P + (1-f_1)(1-f_2)\cdots (1-f_K)$ vanishes in $\{0,1\}^K$ , but one can show that $v\colon [K] \to (\mathbb{Z}/p\mathbb{Z})^{2^K}, v_S = ( \prod\limits_{j\in S} f_j )_{(f_1,\cdots,f_k)\in \{0,1\}^K}$ are linearly independent in $\{0,1\}^K$ (or we induct by seeing this as a linear poly in $f_1$ namely $R(f_2,\cdots,f_K) f_1 + Q(f_2,\cdots,f_K)$ and since this poly is 0 when $f_1\in \{0,1\}$ , $R(f_2,\cdots,f_K), Q(f_2,\cdots,f_K)$ satisfy the problem conditions for $K-1$ ) so $\tilde P + (1-f_1)(1-f_2)\cdots (1-f_K) \equiv 0$
This is absurd since $\deg \tilde P < K$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1633 posts

#9 h Aug 6, 2023, 5:18 AM

Y by

Yet another C-W nuke solution

Claim: $|A| = (p-1)^2$ is achieveable.
Proof. Let $p_n$ denote the $n$ th prime for $1 \le n \le p - 1$ . Then $p-1$ occurences of each $p_n$ suffices. $\blacksquare$

Claim: $(p-1)^2$ is maximal.
Proof. FTSOC assume there exists some $A$ of size $n = p^2 - 2p$ . Enumerate $A$ as $a_{1}, a_{2}, \dots, a_n$ and the prime divisors as $p_1, p_2, \dots, p_n$ . For each $i$ , let $a_i = p_1^{c_{i1}}p_2^{c_{i2}}\dots p_n^{c_{in}}$ .
Construct the $p-1$ polynomials $f_1, f_2, \dots f_{p-1}$ in ${\mathbb F}_p$ such that $f_i(x_1, x_2, \dots, x_n) = \sum_{j=1}^{n} c_{ij}x_j^{p-1}.$ Note that $\deg f_i = p-1$ and that $f_i$ is $0$ iff the elements of $A$ at its nonzero inputs have a product with $\nu_{p_i}$ divisible by $p$ .
Since $n > \deg f_i \cdot (p-1) = (p-1)^2$ , and $(0, 0, \dots, 0)$ is one of the common roots of every polynomial, by Chevalley-Warnining there exists another root, contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

107 posts

#11 h Dec 9, 2023, 11:09 AM

Y by

Let $D = p-1$ . Then the question (thinking in terms of the exponents) can be phrased as follows:

What's the largest multiset of vectors in ${\mathbb F}_p^{D}$ such that no nonempty subset has zero sum?

We claim the answer is $D \cdot (p-1)$ . A construction is given by taking

$p-1$ copies of the vector $\left< 1, 0, \dots, 0\right>$ ;
$p-1$ copies of the vector $\left< 0, 1, \dots, 0\right>$ ;
$......$ ;
$p-1$ copies of the vector $\left< 0, 0, \dots, 1 \right>$ .

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. $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5007 posts

#13 h Jan 5, 2024, 3:45 PM

Y by

The answer is $(p-1)^2$

Interpret each number as a $\mathbb{F}_p^{p-1}$ vector with entries corresponding to their $\nu_q$ modulo $p$ : we are asked to find the largest multiset of vectors such that no nonempty subset of them sum to the $0$ vector. For a construction, we may take $p-1$ copies of each of the $p-1$ vectors with one entry equal to $1$ and the rest $0$ .

I will now prove that $k:=|A|>(p-1)^2$ is impossible. To that end, suppose we had $k$ vectors $v_1,\ldots,v_k$ and the $j$ -th element of $v_i$ was $a_{ij}$ . Consider the following polynomial in $\mathbb{F}_p[x_1,\ldots,x_k]$ :
$P(x):=\prod_{i=1}^{k} (1-x_i)-\prod_{j=1}^{p-1} \left(1-\left(\sum_{i=1}^k a_{ij}x_i\right)^{p-1}\right).$ If we restrict $x_i \in \{0,1\}$ for all $i$ , then choosing some subset of the vectors and summing them is equivalent to setting some subset of the $x_i$ to $1$ (and the rest $0$ ). If we choose the empty set, i.e. $x_i=0$ always, then the first and second products are both $1$ . Otherwise, the first product clearly vanishes, and by hypothesis, since some entry of their sum is nonzero, Fermat's little theorem guarantees that the second product vanishes as well. Thus $P$ vanishes for any choice of $(x_1,\ldots,x_k) \in \{0,1\}^k$ , but since $k>(p-1)^2$ it contains the maximal-degree term $(-1)^kx_1\ldots x_k$ , which yields a contradiction by combinatorial nullstellensatz. $\blacksquare$

This post has been edited 1 time. Last edited by IAmTheHazard, Jan 8, 2024, 2:08 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a