The anwer is $k=2n$ for odd $n$ and $k=n+1$ for even $n$.Counterexample for odd $n$ is $2n-1$ nummbers that are $1$ $modn$ and for even $n$ $n-1$ numbers that are $1$ $modn$ and one number that is $0$ $modn$. Lemma:We have a set $S$ of $n$ numbers.Then,we can pick a subset of those $n$ numbers such that its sum is divisble with $n$.It is enough to pick $n$ distinct subsets of $S$ $A1,A2,...An$ such that $Ai$ is a subset of $Aj$ for all $i<j$(we can trivialy do this).Now,if some of these sets is $0$ $modn$,then we are done,so assume no set is $0$ $modn$.Now,by pigenhole there will exist two sets $Ai$ and $Aj$ which are same $modn$.Then $Aj/Ai$ will be $0$ $modn$,so we proved our lemma. Now,for odd $n$,since we have at least $k=2n$ elements,pick two disjont subsets of $n$ elements and we have that in both of these sets we have a subset which sum is $0$ $modn$,now if some of them has even cardinality we are done and if both have an odd cardinality,their union will have an even cardinality and sum divisible with $n$,which ends the proof for odd $n$.Now,proof for even $n$.First,let's prove for $n=2*m$,where $m$ is odd.Let $E$ be the subset of $A$ which contains all even elements and $O$ be a subset of $A$ of all odd elements.Now,let cardinality of $E$ be $e$ and the cardinality of $O$ be $o$.Consider a family of subsets $Fe$ such that every set is a subset of $E$ and $Ei$ is a subset of $Ej$ for all $i<j$ and $E1$ has $2$ elements,$E2$ $4$ elements etc.Similary,pick $Fo$.Now,$Fe$ and $Fo$ have respectively $e/2$ and $o/2$ elements and $e/2+o/2>=m$.Now,suppose opposite.Then no set in $Fo$ and $Fe$ have sums $0$ $modm$.Also,if two sets are in the same family,they have a different sum $modm$.Now,if in family $Fo$ some set has sum $x$ $modm$,then no set in $Fe$ can't have $-x$ $modm$(cause their union will have even cardinality and sum $0$ mod $2m$),so we conclude that $m<=e/2+o/2<=m-1$ which is a contradiction. Now,assume it is true for some $n=2p$,then it is true for $n=4p$. Proof:Pick a subset of cardinality $2p+1$.By assumption,we can find an even-cardinality subset which is $0$ $mod2p$.Now,we are left with at least $2p+1$ elements and now among them pick an even-cardinality subset which is $0$ $mod2p$. Now,if both are $2p$ $mod4p$ then their union is $0$ $mod2p$ and else we are done,so this ends our proof.

junioragd wrote: let's prove for $n=2*m$,where $m$ is odd.Let $E$ be the subset of $A$ which contains all even elements and $O$ be a subset of $A$ of all odd elements.Now,let cardinality of $E$ be $e$ and the cardinality of $O$ be $o$.Consider a family of subsets $Fe$ such that every set is a subset of $E$ and $Ei$ is a subset of $Ej$ for all $i<j$ and $E1$ has $2$ elements,$E2$ $4$ elements etc.Similary,pick $Fo$.Now,$Fe$ and $Fo$ have respectively $e/2$ and $o/2$ elements and $s/2+o/2>=m$.Now,suppose opposite.Then no set in $Fo$ and $Fe$ have sums $0$ $modm$.Also,if two sets are in the same family,they have a different sum $modm$.Now,if in family $Fo$ some set has sum $x$ $modm$,then no set in $Fe$ can't have $-x$ $modm$(cause their union will have even cardinality and sum $0$ mod $2m$),so we conclude that e/2+o/2<=m-1>=m which is a contradiction. the red part is completely wrong....

My solution: The answer is $2n$ for odd $n$ and $n+1$ for even $n$. In this solution $\overline{Y}$ means the sum of elements of the set $Y$. First I prove a lemma: Lemma: let $n$ be a positive integers then among any $n$ integers $X=\{x_1,x_2,\dots ,x_n\}$ there is a subset $A$ of $X$ such that the sum of elements of $A$ is divisible by $n$. Proof to the lemma: Consider the following sets: $A_1=\{a_1\}$ $A_2=\{a_1+a_2\}$ $\dots$ $A_n=\{a_1+a_2+\dots +a_n\}$ then if for some $i$: $\overline{A_i}\equiv 0\pmod{n}$ we are done. Otherwise we can find two subsets $A_i,A_j$, $j>i$ such that $\overline{A_i}\equiv \overline{A_j}$ then $\overline{A_j-A_i}=a_{i+1}+\dots +a_j\equiv 0\pmod{n}$. And our lemma proved hear. ___________________________________________________________________________________________________________________________________________________________ Now consider three cases: 1) $n=2k$ is even and $k$ is odd integer. Take $n+1$ arbitrary positive integers. then partition $n+1$ numbers to $A=\{ a_1,a_2,\dots ,a_t\},B=\{b_1,b_2,\dots ,b_s\}$ so that $A$ contains all odd numbers and $B$ contains all even numbers among our $n+1$ integers. Now because $t+s=n+1$ is odd number one of $t,s$ is odd and the other is even. First assume that $t$ is even then partition elements of $A$ into $\frac{t}{2}$ subsets $A_1=\{a_1,a_2\},A_2=\{a_3,a_4\},\dots ,A_{\frac{t}{2}}=\{a_{t-1},a_t\}$ and similarly partition the elements of $B-\{b_s\}$ into $\frac{s-1}{2}$ subsets $B_1=\{b_1,b_2\}, B_2=\{b_3,b_4\},\dots , B_{\frac{s-1}{2}}=\{b_{s-2},b_{s-1}\}$ let $\overline{X}$ be the sum of elements of the set $X$. then the numbers $\overline{A_1},\overline{A_2},\dots,\overline{A_{\frac{t}{2}}},\overline{B_1},\overline{B_2},\dots,\overline{B_{\frac{s-1}{2}}}$ are $\frac{t+s-1}{2}=\frac{n}{2}$. So from our lemma there is a subset of these $\frac{n}{2}=k$ numbers such that their sum is divisible by $k$ but since they are even and $k$ is odd we get that also $n=2k$ divides that sum but because every $A_i,B_j$ has two elements we deduce that the sum has got even elements of our main set $\{a_1,a_2,\dots,a_t,b_1,b_2,\dots ,b_t\}$ so we are done. (The case when $t$ is odd is exactly similar.) 2)$4\mid n=2k$ then let $A=\{a_1,a_2,\dots ,a_{n+1}\}$ be the set of $n+1$ arbitrary numbers then consider $A_1=\{a_1,a_2,\dots ,a_{k+1}\}$ since $k$ is even from the case $(1)$ we get that there is a subset $X_1$ of $A$ with even elements such that sum of its elements is divisible by $k$. so $\overline{X_1}=kt$. Now since $k$ is even the the number of elements of $X_1$ is less than $n+1$ so $A-X_1$ has at least $k+1$ elements and similarly we can find subset $X_2$ of $A-X_1$ with even elements such that $\overline{X_2}\equiv 0\pmod{k}$ so $X_1=Kl$ if one of $t,l$ is even we are done so both of them are odd but in this case $X_1\cup X_2=k(t+l)=2ks$ so we are done. 3)$n$ is odd then consider arbitrary set $A=\{a_1,a_2,\dots ,a_{2n}\}$ then from our lemma we can find two subsets $X_1,X_2$ from the sets $A_1=\{a_1,a_2,\dots ,a_n\},A_2=\{a_{n+1},a_{n+2},\dots ,a_{2n}\}$ such that $\overline{X_1}\equiv \overline{X_2}\equiv 0\pmod{n}$ if one of $X_1,X_2$ has even elements we are done otherwise $X_1\cup X_2$ has even elements with the sum divisible by $n$. DONE

The red part should be wrong because it is a way to reach contradiction.I proved that $e/2 + s/<=m-1$ and $e/2 + s/2>=m$ which is a contradiction.Although,the red part should be written as $m<=e/2 + s/2<=m-1$.

junioragd wrote: The red part should be wrong because it is a way to reach contradiction.I proved that $e/2 + s/<=m-1$ and $e/2 + s/2>=m$ which is a contradiction.Although,the red part should be written as $m<=e/2 + s/2<=m-1$. dear junioragd the way of getting the inquality is wrong. i say the following statement doesn't imply that $e/2 + s/2<=m$ another mistake that you have is that since $e+f=n+1$ one of $e,f$ is odd and the other is even so $\frac{e}{2}+\frac{f}{2}$ isn't integer. junioragd wrote: Then no set in $Fo$ and $Fe$ have sums $0$ $modm$.Also,if two sets are in the same family,they have a different sum $modm$.Now,if in family $Fo$ some set has sum $x$ $modm$,then no set in $Fe$ can't have $-x$ $modm$(cause their union will have even cardinality and sum $0$ mod $2m$),so we conclude that $m<=e/2+o/2<=m-1$ maybe i misunderstood this part. it will be better if you explain this part with details.

Here $e/2$ is the same as $[e/2]$.Now,it is clear that if $e+f>=2m+1$ implies $[e/2]+[o/2]>=m$.Now,for example let $E$ be $a1,...a5$ then the family $Fe$ are sets ${a1,a2}$ and ${a1,a2,a3,a4}$. junioragd wrote: Consider a family of subsets $Fe$ such that every set is a subset of $E$ and $Ei$ is a subset of $Ej$ for all $i<j$ and $E1$ has $2$ elements,$E2$ $4$ elements etc.Similary,pick $Fo$. This explains how familyes look. Now,the part you asked,if some family in $Fe$ or $Fo$ is $0$ $modm$ it is also divisble with $2m$ because every set in the family has sum divisible with $2$.Now,if two sets in the same family WLOG $Fe$ $Ei$ and $Ej$($i<j$) are same $modm$,then $Ej/Ei$ will satisfay the conditions.Now,if there exists $Ei$ and $Oj$ such that $Ei+Oj$ is $0$ $modm$ than EiUOj will satisfay the conditions.So,in $Fe$ we have $[e/2]$ distinct residues $modm$ n on-equal to zero and in $Fo$ we have $[o/2]$ distinct residues $modm$ non-equal to zero and there don't exist a residue $a$ from $o$ and $b$ from $e$ such $a+b$ is $0$ $modm$.Now,for any residue $b$ from $e$ exists a unique $a$ that can't be in $o$,so from this we conclude that $[e/2]+[o/2]<=m-1$.

junioragd wrote: Now,the part you asked,if some family in $Fe$ or $Fo$ is $0$ $modm$ it is also divisble with $2m$ because every set in the family has sum divisible with $2$.Now,if two sets in the same family WLOG $Fe$ $Ei$ and $Ej$($i<j$) are same $modm$,then $Ej/Ei$ will satisfay the conditions.Now,if there exists $Ei$ and $Oj$ such that $Ei+Oj$ is $0$ $modm$ than EiUOj will satisfay the conditions.So,in $Fe$ we have $[e/2]$ distinct residues $modm$ n on-equal to zero and in $Fo$ we have $[o/2]$ distinct residues $modm$ non-equal to zero and there don't exist a residue $a$ from $o$ and $b$ from $e$ such $a+b$ is $0$ $modm$.Now,for any residue $b$ from $e$ exists a unique $a$ that can't be in $o$,so from this we conclude that $[e/2]+[o/2]<=m-1$. finally i understood your solution... i apologies you

andria wrote: 2)$4\mid n=2k$ then let $A=\{a_1,a_2,\dots ,a_{n+1}\}$ be the set of $n+1$ arbitrary numbers then consider $A_1=\{a_1,a_2,\dots ,a_{k+1}\}$ since $k$ is even from the case $(1)$ we get that there is a subset $X_1$ of $A$ with even elements such that sum of its elements is divisible by $k$. so $\overline{X_1}=kt$. Now since $k$ is even the the number of elements of $X_1$ is less than $n+1$ so $A-X_1$ has at least $k+1$ elements and similarly we can find subset $X_2$ of $A-X_1$ with even elements such that $\overline{X_2}\equiv 0\pmod{k}$ so $X_1=Kl$ if one of $t,l$ is even we are done so both of them are odd but in this case $X_1\cup X_2=k(t+l)=2ks$ so we are done. Correct me if I am wrong but I think there is a slight inconsistency in the bolded part of the above quote. You can't use case (1) here because there is no guarantee that $k$ is of the form $2s$ with $s$ odd. This error, I believe, can be patched if we induct on the highest power of two dividing $n$ instead of directly trying to use case (1). Nice proof btw.

Pardon me, <andria> wrote: $A_1=\{a_1,a_2,\dots ,a_{k+1}\}$ since $k$ is even from the case $(1)$ we get that there is a subset $X_1$ of $A$ with even elements such that sum of its elements is divisible by $k$ If you want to use the conclusion of case $(1)$, shouldn't you show that $k=2 * odd$ since that was the supposition?

I had a slightly different approach to proving that $k=n+1$ for even $n$, not requiring to distinguish between the $n=2(2m+1)$ and $n=4m$ cases. We will use the lemma that in any set of at least $n$ elements there is a subset with the sum of it's elements divisible by $n$. It's proof can be found above. Now to the problem. In the set $A=\{a_1,a_2,\dots,a_k\}$ of at least $n+1$ elements there clearly must be $P\ge\frac{n}{2}$ disjoint pairs $(a_{f_i},a_{s_i})$ of elements of the same parity. Let $b_i=\frac{a_{f_i}+a_{s_i}}{2}$ for $i=\overline{1,P}$. By the lemma there is a subset of $\{b_1,b_2,\dots,b_P\}$ with sum of it's elements divisible by $\frac{n}{2}$. But now we can easily reverse-engineer the desired subset of $A$.