MathDB

Combinatorics on partial sums and divisibility

Source: RMM 2024 Problem 2

February 29, 2024

algorithmnumber theoryprime numbersPartial sumspermutationsRMM

Problem Statement

Consider an odd prime

p

and a positive integer

N < 50p

. Let

a_1, a_2, \ldots , a_N

be a list of positive integers less than

p

such that any specific value occurs at most

\frac{51}{100}N

times and

a_1 + a_2 + \cdots· + a_N

is not divisible by

p

. Prove that there exists a permutation

b_1, b_2, \ldots , b_N

of the

a_i

such that, for all

k = 1, 2, \ldots , N

, the sum

b_1 + b_2 + \cdots + b_k

is not divisible by

p

.
Will Steinberg, United Kingdom

Back to Problems View on AoPS