Olympiad problems

Found problems: 2

2024 Romanian Master of Mathematics, 2

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$. [i]Will Steinberg, United Kingdom[/i]

2015 Romania Team Selection Tests, 3

Let $n$ be a positive integer . If $\sigma$ is a permutation of the first $n$ positive integers , let $S(\sigma)$ be the set of all distinct sums of the form $\sum_{i=k}^{l} \sigma(i)$ where $1 \leq k \leq l \leq n$ . [b](a)[/b] Exhibit a permutation $\sigma$ of the first $n$ positive integers such that $|S(\sigma)|\geq \left \lfloor{\frac{(n+1)^2}{4}}\right \rfloor $. [b](b)[/b] Show that $|S(\sigma)|>\frac{n\sqrt{n}}{4\sqrt{2}}$ for all permutations $\sigma$ of the first $n$ positive integers .

permutation probabilistic method combinatorics partial sums number theory permutations