A set of $n$ positive integers is said to be balanced if for each integer $k$ with $1 \leq k \leq n$, the average of any $k$ numbers in the set is an integer. Find the maximum possible sum of the elements of a balanced set, all of whose elements are less than or equal to $2017$.
Problem
Source: Mexico National Olympiad 2017, Problem 2
Tags: number theory, Average
RagvaloD
06.11.2017 23:32
If all elements are 2017, then sum is $2017n$
juckter
06.11.2017 23:35
RagvaloD wrote: If all elements are 2017, then sum is $2017n$ We're talking about a set, so the elements must be distinct.
juckter
07.11.2017 00:08
The answer is $12859$ which is achieved by choosing the set of the numbers $2017 - 60k$ for $k = 0, 1, \dots, 6$. Any set with 6 or less elements has a sum smaller than $2017 \cdot 6 < 12859$ and hence $n \geq 7$ must hold in order for a set to achieve the maximal sum.
Claim. For a balanced set $S$ with $n$ elements and for any $2 \leq m \leq n - 1$, all of the elements of $S$ are congruent modulo $m$.
Proof. Assume by contradiction that two elements $a$ and $b$ of $S$ are not congruent modulo $m$ and let $T$ be an $m$-element subset of $S$ which contains $a$ and $b$, then $m$ must divide the sum of the elements of $T$. Now for any $c \in S \setminus T$, the sum of the elements of the sets $(T \setminus \{a\})\cup\{c\}$ and $(T \setminus \{b\})\cup\{c\}$ must be a multiple of $m$, which implies $c$ must be congruent to both $a$ and $b$ modulo $m$, this is a contradiction.
Now, this implies that any balanced set with $n$ elements must satisfy that they are all congruent modulo $d = [2, 3, \dots, n - 1]$ and hence the smallest element of the set is at most $2017 - (n - 1)d$. Since this may not be negative we easily find that $n$ may not be greater than or equal to $8$, and thus $n$ must be exactly $7$, and all of the elements of the set must be congruent modulo $[2, 3, \dots, 6] = 60$. Since the largest element of the set is at most $2017$, the set described at the beginning indeed achieves the largest possible sum.
RagvaloD
07.11.2017 00:11
If so For every $i,j$ we can take some subset of $a_{i_1},...,a_{i_{k-1}}$ that does not contain $a_i,a_j$ and $k|a_{i_1}+...a_{i_{k-1}}+a_i-(a_{i_1}+...a_{i_{k-1}}+a_j)=a_i-a_j $ Let $a_1<a_2<...<a_n$ For every prime $p<n$ is true, that $p|a_{i+1}-a_i$. Let $p_1,...,p_k$ are all primes less then $n$ then $p_1...p_k|a_{i+1}-a_i$ so $a_2 \geq p_1...p_k+a_1 \geq p_1...p_k+1$ $a_3 \geq p_1...p_k+a_2 \geq 2p_1...p_k+1$ $a_n \geq (n-1)p_1...p_k+1 \geq p_k (p_1...p_k)+1$ $2017 \geq p_k (p_1...p_k)+1 \to p_k \leq 7$ If $p_k=7$ then $n-1 \leq \frac{2016}{2*3*5*7}=9.6 \to n \leq 10$ If $ n=8,9,10$ then $4*3*5*7|a_{i+1}-a_{i}$ then $a_n \geq 7*4*3*5*7+1>2017$ So $n \leq 7$ and we can build sequence as $2017,2017-60,...2017-6*60$ for $n=7$
MiltonMath12
04.09.2018 13:07
My solution is for the Chinese theorem of the residue, I upload it tomorrow
TheBrightness
07.09.2018 01:31
MiltonMath12 wrote: My solution is for the Chinese theorem of the residue, I upload it tomorrow Upload it please.
Mathlete2017
07.09.2018 03:30
MiltonMath12 wrote: My solution is for the Chinese theorem of the residue, I upload it tomorrow Can we see?
MiltonMath12
07.09.2018 21:53
Quoting jucker Quote: Claim. For a balanced set $S$ with $n$ elements and for any $2 \leq m \leq n - 1$, all of the elements of $S$ are congruent modulo $m$. So we know that for theorem chinese of the residue $x_{1} \equiv x_{2} \equiv ... \equiv x_{n} mod \ L$ Where L is the LCM of 2.3, ..., n. So $L>840$ if $n>9$ Let $x_{n} > x_{n-1} > ... > x_{2} > x_{1}$ be So $0\leq x_{9} \leq 2017-8L \leq -4703$, wich is a contradiction, so $n\leq8$ And for this last fact there are few sets that meet it and the one with the greaters sum is $(2017,2017-60,2017-2*60,...,2017-6*60)$ and its sum is $12859$