CAPS 2016 Problem 3

Let $n$ be a positive integer. For a finite 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)