*)Lemma. Among any $ 2n - 1$ integers one choose $ n$ integers whose sum is divisible by $ n$. Proof. If lemma holds for $ m,n$ then lemma holds for $ mn$. So we have prove for $ n$ is prime. Let $ 2n - 1$ integers are $ a_1,a_2, . . . ,a_{2n - 1}$. Indeed, assume any $ n$ integers whose sum isn't divisible by $ n$, then apply theorem Fermat: $ \sum_{1\leq i_1 < i_2 < . . . < i_n\leq 2n - 1}(a_{i_1} + a_{i_2} + . . . + a_{i_n})^{n - 1}\equiv (^{2n - 1}_n)$(mod n). Impossible, hand-left is divisible by $ n$, hand-right isn't divisible by $ n$. *)We have $ 2n - 2$ integer: $ (0,0, . . . ,0,1,1, . . . ,1)$ satisfy no $ n$ integer whose sum is divisible by $ n$. *)So $ n$ smallest in problem is $ 35$.

Hello, I have two questions about your proof... Why is the following true? Thjch Ph4 Trjnh wrote: If lemma holds for $ m,n$ then lemma holds for $ mn$. Also why is the left hand side divisible by $ n$ if $ n$ is prime? Thjch Ph4 Trjnh wrote: $ \sum_{1\leq i_1 < i_2 < . . . < i_n\leq 2n - 1}(a_{i_1} + a_{i_2} + . . . + a_{i_n})^{n - 1}\equiv \binom{2n - 1}{n}\pmod{n}$ Thank you,

http://www.mathlinks.ro/viewtopic.php?p=389030

moldovan wrote: Determine the smallest natural number $ n$ such that among any $ n$ integers one can choose $ 18$ integers whose sum is divisible by $ 18$. sorry, but i could not understand your question. according to the statement of the question, i am allowed to choose any $ n$ naturals out of which i choose some $ 18$ numbers whose sum is divisible $ 18$. if so then $ n$ can be $ 18$ itself as i can choose $ 18$ multiples of $ 18$ and their sum is obviously divisible by $ 18$. there is something missing..(either in the question or my comprehension)..please clear it

"Any" means "for all".

Quote: Hello, I have two questions about your proof... Why is the following true? Thjch Ph4 Trjnh wrote: If lemma holds for $ m,n$ then lemma holds for $ mn$. Assume lemma holds for $ m,n$. Let $ 2mn-1$ integers are:$ a_1,a_2, . . .,a_{2mn-1}$. Among $ a_1,a_2, . . .,a_{2n-1}$ has $ n$ number whose sum is divisible by $ n$, assume is $ a_1,a_2, . . . ,a_n$. Among $ a_{n+1},a_{n+2},. . .,a_{3n-1}$ ... .... So have $ (2m-1)$ $ n-$tuples $ (a_{i_1},a_{i_2},. . .,a_{i_n})$. Donote $ b_i=\frac{a_{i_1}+a_{i_2}+. . .+a_{i_n}}{n}$ so $ b_i\in Z$. We obtain $ (2m-1)$ $ n-$tuples $ b_i$. So have $ m$ numbers of these whose sum is divisible by m. Completes.

Hi, can someone post a clearer proof of the generalization? Thanks

Hi, the generalization actually cannot be proven with elementary means I believe; see here.

As mavropnevma sir says mavropnevma wrote: Erdös-Ginsburg-Ziv theorem: Out of $2n-1$ integers there exist $n$ with sum divisible by $n$. the general proof is elementary, but kind of complicated; in this thread British MO 2000 http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=592776 This is a very similar but much simpler question

Thjch Ph4 Trjnh wrote: $ \sum_{1\leq i_1 < i_2 < . . . < i_n\leq 2n - 1}(a_{i_1} + a_{i_2} + . . . + a_{i_n})^{n - 1}\equiv (^{2n - 1}_n)$(mod n). . How do your prove that the LHS is divisible by n?

Actually it has been a long time since the discussion, but anyway. So the problem can be generalized for every k positive integer and here is why: Claim1: It works for any $p \in P$. Indeed, it is straightforward that the answer is at least $2p-1$, otherwise there is a tuple $(0,0,0,0...0,1,1,1...1)$, where $0$s and $1$s appear exactly $p-1$ times, the sum is never divisible by $p$. So it is left to prove that it is sufficient. For the sake of contrary let $a_1, a_2, ..., a_{2p-1}$ be the numbers, so that the $(a_1+a_2+...+a_p)$ is not divisible by $p$ for all permutations of $a_i$. There are exactly $\binom{2p-1}{p}$ ways to pick $a_i,$ it is clear that $\binom{2p-1}{p} \not\vdots p$. Let's count the coefficients of $a_1a_2...a_j$ in $\sum{(a_1+a_2+...+a_p)}^{p-1}$ . From the one hand, by Fermat's, $LHS$ is just $1+1+...+1$ $\binom{2p-1}{p}$ times, meaning that $LHS \not\vdots p$. From the other, each term $a_1^{e_1}*...*a_j^{e_j}$ for $e_1+...+e_j=p-1$ appears once for $(a_1+...+a_j+...)^p$, so there are $\binom{2p-1-j}{p-j}$ appearances of $a_1^{e_1}*...*a_j^{e_j}$, which is divisible by $p$, the contradiction. Claim2: if it works for $k_1, k_2$, then it works for $k_1k_2$ Let's pick $2k_1-1$ among $2k_1k_2-1$, by hypothesis, there are $k_1$ numbers, whose sum $\vdots k_1$. Return the rest $k_1-1$ numbers and do this operation again and again until we get $2k_2-1$ groups where each group's sum $\vdots k_1$. let $b_i=s_i/k_1$, then $ b_i \in Z$. For $b_1, b_2, ..., b_{2k_2-1}$ we have $k_2$ numbers whose sum $\vdots k_2$, so then the union of all these consists of $k1*k2$ terms, the sum is divisible by $k_1*k_2$ and we are done Answer: $2*18-1=35$