It is given positive integer $n$. Let $a_1, a_2,..., a_n$ be positive integers with sum $2S$, $S \in \mathbb{N}$. Positive integer $k$ is called separator if you can pick $k$ different indices $i_1, i_2,...,i_k$ from set $\{1,2,...,n\}$ such that $a_{i_1}+a_{i_2}+...+a_{i_k}=S$. Find, in terms of $n$, maximum number of separators
Problem
Source: Bosnia and Herzegovina EGMO Team Selection Test 2018
Tags: combinatorics, maximization, Extremal combinatorics
Jjesus
09.02.2021 17:39
any ideas?
Rooptak
10.02.2021 07:33
I'm not sure if I interpreted the question correctly but it may depend on the sequence of positive integers given. For example taking $(2,2^2,2^3...2^n)$, we would have $S \equiv 1mod(2)$ but sum of any subset of the sequence of numbers is even, so $k=0$ here @below Ahhhh!! yeaaaa So isn't it gonna be $n-1$ cause we can take the sequence to be $(1,1,....1,n-1)$ and $i_k=k (\forall 1 \leq k \leq n-1) $
tobylong
10.02.2021 07:52
Rooptak wrote: I'm not sure if I interpreted the question correctly but it may depend on the sequence of positive integers given. For example taking $(2,2^2,2^3...2^n)$, we would have $S \equiv 1mod(2)$ but sum of any subset of the sequence of numbers is even, so $k=0$ here Well, you get the minimum of the separators, but the original question asks for the maximum...
MathsLion
10.02.2021 11:27
Problems of Bosnian TST's are rarely original. For example this is: Russia 2001
tobylong
10.02.2021 12:23
Rooptak wrote: I'm not sure if I interpreted the question correctly but it may depend on the sequence of positive integers given. For example taking $(2,2^2,2^3...2^n)$, we would have $S \equiv 1mod(2)$ but sum of any subset of the sequence of numbers is even, so $k=0$ here @below Ahhhh!! yeaaaa So isn't it gonna be $n-1$ cause we can take the sequence to be $(1,1,....1,n-1)$ and $i_k=k (\forall 1 \leq k \leq n-1) $ Are you sure you are right? I think the sequence $(1,1,....1,n-1)$ have only $2$ separators: $k=1$ and $k=n-1$.
Rooptak
10.02.2021 14:30
Ohhhhh ohk, I again misinterpreted, I thought we had to find $max\{k\}$