MathDB

4

Part of 2018 Bosnia and Herzegovina EGMO TST

Problems(1)

Bosnia and Herzegovina EGMO TST 2018 Problem 4

Source: Bosnia and Herzegovina EGMO Team Selection Test 2018

9/19/2018
It is given positive integer nn. Let a1,a2,...,ana_1, a_2,..., a_n be positive integers with sum 2S2S, S∈NS \in \mathbb{N}. Positive integer kk is called separator if you can pick kk different indices i1,i2,...,iki_1, i_2,...,i_k from set {1,2,...,n}\{1,2,...,n\} such that ai1+ai2+...+aik=Sa_{i_1}+a_{i_2}+...+a_{i_k}=S. Find, in terms of nn, maximum number of separators
combinatoricsmaximizationExtremal combinatorics