Saint-Peterburg 2003 [sums divisible by prime p]

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

Saint-Peterburg 2003 [sums divisible by prime p]

G H J

Reveal topic tags

combinatorics proposed

L

G H BBookmark kLocked kLocked NReply

Source: Saint-Peterburg 2003, 10th grade, last problem, created by Andrey Badzyan

The post below has been deleted. Click to close.

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

7 posts

#1 h Feb 13, 2008, 2:13 PM • 7 Y

Y by Exista, Adventure10, ObjectZ, Mango247, and 3 other users

Let $p$ be a prime number, and $n$ be an integer such that $n\geq p$ . Assume that $a_1$ , $a_2$ , ..., $a_n$ are arbitrary integer numbers. For every $k$ , we denote by $f_k$ the number of $k$ -subsets $\left\{s_1,s_2,...,s_k\right\}$ of the set $\left\{1,2,...,n\right\}$ such that the sum $a_{s_1} + a_{s_2} + ... + a_{s_k}$ is divisible by $p$ . Prove that
$p\mid \sum_{k = 0}^n\left( - 1\right)^kf_k$ .
(Here, we understand $f_0$ to be $= 1$ .)

Z K Y

The post below has been deleted. Click to close.

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

644 posts

#2 h Feb 14, 2008, 7:12 PM • 6 Y

Y by Kanep, Adventure10, Mango247, and 3 other users

Nice one!

Consider

$A = \prod_{i = 1}^n (1 - \zeta_p^{a_i})\in \mathbb{Q}(\zeta_p)$

where $\zeta_p$ is a primitive $p$ -th root of unity.

It is easily seen that

$p\sum_{k = 0}^n ( - 1)^k f_k = \text{tr}_{\mathbb{Q}(\zeta_p)/\mathbb{Q}} A$ .

Here $\text{tr}_{\mathbb{Q}(\zeta_p)/\mathbb{Q}}$ denotes the trace from $\mathbb{Q}(\zeta_p)$ to $\mathbb{Q}$ . Now, obviously $(1 - \zeta_p^{a_i})$ is divisible by $(1 - \zeta_p)$ , thus by the assumption $n\geq p$ , $(1 - \zeta_p)^p$ divides $A$ . However, $(1 - \zeta_p)^{p - 1} = pe$ where $e$ is a unit(I guess $e = \zeta_p^{(p-1)/2}$ ). Thus $1 - \zeta_p$ divides $\frac Ap$ ; it follows that $1 - \zeta_p$ divides $\frac 1p \text{tr}_{\mathbb{Q}(\zeta_p)/\mathbb{Q}} A$ . But since $\frac 1p \text{tr}_{\mathbb{Q}(\zeta_p)/\mathbb{Q}} A$ is rational, we must have that it is divisible by $p$ . The conclusion follows.

Z K Y

The post below has been deleted. Click to close.

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

6555 posts

#3 h Feb 16, 2008, 1:12 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

I have just uploaded a more elementary (but longer) proof on my webpage:
St. Petersburg 2003: An alternating sum of zero-sum subset numbers.
(Only read until (3), and then from the end of p. 6 on if you know Lemma 2.)
So we have a proof by algebraic number theory and a proof by algebraic combinatorics now. What about one by homology sequences?

darij

This post has been edited 1 time. Last edited by darij grinberg, Nov 18, 2008, 1:09 PM

Z K Y

The post below has been deleted. Click to close.

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

1363 posts

Erken

#4 h Feb 16, 2008, 2:41 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

There is given a short algebraic and elementary proof in the book S-P 2003.Also there is combinatorics proof too,but it is a bit longer.

Z K Y

The post below has been deleted. Click to close.

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

6555 posts

#5 h Feb 16, 2008, 2:45 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

I don't have the book here, and I am not sure whether I have it in Karlsruhe (I definitely have 2002). Can you kindly look up whether the book tells something about where the problem comes from?

darij

Z K Y

The post below has been deleted. Click to close.

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

1363 posts

Erken

#6 h Feb 16, 2008, 10:09 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

The problems author is Andrey Badzyan,and this problems was used as the last and hardest problem for the 10th grade.

Z K Y

The post below has been deleted. Click to close.

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

6555 posts

#7 h May 2, 2008, 10:27 PM • 4 Y

Y by Adventure10, Mango247, and 2 other users

Generalization. Let $p$ be a prime number, $\alpha$ an nonnegative integer, $c$ an integer and $n$ be an integer such that $n\geq p^{\alpha}$ . Assume that $a_1$ , $a_2$ , ..., $a_n$ are arbitrary integer numbers. For every $k$ , we denote by $f_k$ the number of $k$ -subsets $\left\{s_1,s_2,...,s_k\right\}$ of the set $\left\{1,2,...,n\right\}$ such that the sum $a_{s_1} + a_{s_2} + ... + a_{s_k}-c$ is divisible by $p^{\alpha}$ . Prove that
$p\mid \sum_{k = 0}^n\left( - 1\right)^kf_k$ .
(Here, we understand $f_0$ to be $= 1$ .)

This post has been edited 1 time. Last edited by darij grinberg, Jul 3, 2021, 6:06 PM
Reason: Hereby -> Here

Z K Y

The post below has been deleted. Click to close.

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

1363 posts

Erken

#8 h May 12, 2008, 6:29 AM • 7 Y

Y by Adventure10, Mango247, and 5 other users

darij grinberg wrote:

Generalization. Let $p$ be a prime number, $\alpha$ an nonnegative integer, $c$ an integer and $n$ be an integer such that $n\geq p^{\alpha}$ . Assume that $a_1$ , $a_2$ , ..., $a_n$ are arbitrary integer numbers. For every $k$ , we denote by $f_k$ the number of $k$ -subsets $\left\{s_1,s_2,...,s_k\right\}$ of the set $\left\{1,2,...,n\right\}$ such that the sum $a_{s_1} + a_{s_2} + ... + a_{s_k} - c$ is divisible by $p^{\alpha}$ . Prove that
$p\mid \sum_{k = 0}^n\left( - 1\right)^kf_k$ .
(Here, we understand $f_0$ to be $= 1$ .)

The following proof is based on a solution given at the original book.
Proof: Denote $S = \sum_{k = 0}^n\left( - 1\right)^kf_k$ .
WLOG assume that all $a_i$ are $\geq 0$ and that $0\leq c<p^{\alpha}$ .
Consider polynomial $f(x) = (1 - x^{a_1})(1 - x^{a_2})\dots(1 - x^{a_n})$
We need to prove that the sum of coefficients by the $x^c,x^{p^{\alpha} + c},x^{2p^{\alpha} + c}\dots$ (this sum is $S$ ) is divisible by $p$ .
Indeed since $x^{kp^{\alpha} + c}\equiv x^c \mod x^{p^{\alpha}}-1$ and if $x^{d}\equiv x^c \mod x^{p^{\alpha}}-1$ then $d = kp^{\alpha} + c$ ,so $S$ is equal to the coefficient by $x^c$ in polynomial $r(x)$ ,where
$f(x) = q(x)(x^{p^{\alpha}} - 1) + r(x)$ .
We will prove that all coefficients in $r(x)$ are divisible by $p$ .Indeed,since $n\geq p^{\alpha}$ ,then
$f(x)$ is divisible by $(x - 1)^{p^{\alpha}}$ .
Then $f(x) = (x - 1)^{p^{\alpha}}h(x) = (x^{p^{\alpha}} - 1)h(x) + ph(x)r(x)$ .
The last equality follows from the well-known fact:
$p\mid \binom{p^{\alpha}}{i}$ ,where $1\leq i\leq p^{\alpha} - 1$ .
Now it is enough to prove that the coefficients in $ph(x)r(x)$ modulo $x^{p^{\alpha}} - 1$ are divisible by $p$ ,which is trivially true.

This post has been edited 2 times. Last edited by darij grinberg, Jul 3, 2021, 6:07 PM
Reason: Hereby -> Here (in quote)

Z K Y

The post below has been deleted. Click to close.

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

533 posts

#9 h May 12, 2008, 3:57 PM • 1 Y

Y by Adventure10

Very nice Erken!

And this method (COMPLEX COMBINATORICS) is very useful and strong.

Z K Y

The post below has been deleted. Click to close.

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

635 posts

#10 h Sep 20, 2020, 11:39 AM

Y by

We need to prove $(1-y^{a_1}),\hdots,(1-y^{a_n})=0$ in $\frac {\mathbb Z[y]}{(p,y^{p-1})}.$
$(1-y)^p=0\in\frac {\mathbb Z[y]}{(p,y^{p-1})}\,\text{if}\, p=2\,\text {also}.$
Note that, since $p\le n,$ $(1-y)^p\mid\text {left hand side}\text {in}\,\mathbb Z [y].$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a