MathDB

Czech-Polish-Slovak Match 2016

Source: Czech-Polish-Slovak Match 2016,P3,day 1

July 12, 2016

combinatorics

Problem Statement

Let

n

be a positive integer. For a finite set

M

of positive integers and each

i \in \{0,1,..., n-1\}

, we denote

s_i

the number of non-empty subsets of

M

whose sum of elements gives remainder

i

after division by

n

. We say that

M

is "

n

-balanced" if

s_0 = s_1 =....= s_{n-1}

. Prove that for every odd number

n

there exists a non-empty

n

-balanced subset of

\{0,1,..., n\}

. For example if

n = 5

and

M = \{1,3,4\}

, we have

s_0 = s_1 = s_2 = 1, s_3 = s_4 = 2

so

M

is not

5

-balanced.(Czech Republic)

Back to Problems View on AoPS