Find the least k

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Find the least k

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Iran TST 2015, first exam, day 2 problem 1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

97 posts

#1 h May 11, 2015, 1:55 PM • 3 Y

Y by Dadgarnia, Adventure10, Mango247

$n$ is a fixed natural number. Find the least $k$ such that for every set $A$ of $k$ natural numbers, there exists a subset of $A$ with an even number of elements which the sum of it's members is divisible by $n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

314 posts

#2 h May 12, 2015, 4:05 PM • 1 Y

Y by Adventure10

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.

This post has been edited 1 time. Last edited by junioragd, Aug 14, 2015, 10:49 AM
Reason: Fixing the red part

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

824 posts

andria

#3 h Aug 14, 2015, 6:49 AM • 2 Y

Y by Adventure10, Mango247

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....

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

824 posts

andria

#4 h Aug 14, 2015, 6:57 AM • 4 Y

Y by ferma2000, for63434, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

314 posts

#5 h Aug 14, 2015, 10:45 AM • 2 Y

Y by Adventure10, Mango247

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$ .

This post has been edited 1 time. Last edited by junioragd, Aug 14, 2015, 10:46 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

824 posts

andria

#6 h Aug 14, 2015, 12:08 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

314 posts

#7 h Aug 14, 2015, 5:44 PM • 1 Y

Y by Adventure10

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$ .

This post has been edited 1 time. Last edited by junioragd, Aug 14, 2015, 5:47 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

824 posts

andria

#8 h Aug 21, 2015, 7:05 PM • 1 Y

Y by Adventure10

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

62 posts

#9 h Jan 1, 2016, 11:00 AM • 1 Y

Y by Adventure10

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

105 posts

#10 h Feb 5, 2017, 4:12 PM • 1 Y

Y by Adventure10

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

25 posts

#11 h Jun 20, 2019, 2:34 PM • 2 Y

Y by Infinityfun, Adventure10

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$ .

This post has been edited 2 times. Last edited by ComiCabE, Jun 22, 2019, 10:35 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a