|
|
CTK Exchange
jay_shark
Member since Mar-20-07
|
Nov-03-08, 11:21 PM (EST) |
 |
"disjoint sets"
 |
Hey Alex, here is an interesting problem taken from 2001 Israel Binational mathematics competition problem 6. You have 32 natural numbers such that: a_1 + a_2 + ...... + a_32 = 120 All a's belong to {1,2,3,4, .....,59,60} i.e. 1<= a_i <= 60 Prove you can find 2 disjoint collections of the 32 numbers, such that the sum of the elements of one collection is equal to the sum of the elements of the other. For instance, (1+1+1+...+1) + 30 + 60 = 120 (30 1's) And the partitions would be {(1+1+1+....+1) + 30} , {60}
|
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
jay_shark
Member since Mar-20-07
|
Nov-21-08, 06:21 PM (EST) |
 |
4. "RE: disjoint sets"
In response to message #0
 |
Hi Alex, I came up with a solution but I worked way too hard on this one. Given any sequence of 32 numbers, from the set {1,2,3,…,60) which sums to 120, we can always find a subsequence which adds up to 60. Sol’n - Separate the even numbers from the odd numbers. For instance, lets say we have 16 even numbers and 16 odd numbers. Then we can always find a subsequence from the even set which sums to 30 and a subsequence from the odd set which sums to 30. Let a_k denote the even numbers and b_k denote the odd numbers. Define Xi = sum {k=1 to k=i} a_k And Yi = sum { k=1 to k=i} b_k By the pigeonhole principle, two of the Xi’s must be congruent mod 30 since there are at most 15 even numbers from the set {2,4,6,…,30} Similarly, two of the Yi’s must be congruent mod30 since there are 15 odd numbers from the set {1,3,5,…,29} Combine the two sets and we get a sum of 60. It turns out that this is true in general. Suppose we have 18 even numbers and 14 odd numbers. From the even set, we can always find a subsequence which sums to 18*2 – 2 and a subsequence from the odd set that sums to 14*2 – 2. Together, they combine for a total sum of 60. And in general, if we have n even numbers and 32-n odd numbers where n is necessarily even, then 2n-2 + 2*(32-n)-2 = 60 QED |
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
 |
|
Pierre Charland
Member since Dec-22-05
|
Nov-24-08, 09:11 AM (EST) |
 |
6. "RE: disjoint sets"
In response to message #0
| |
Comments: we have 1<= a_i <= 60 also 0<= a_i <= 29 (mod 30)Let s the 32-set {a_1, ..., a_32} Let sa and sb the 2 disjoint subsets, with (sa union sb = s). sum(s) = sum(sa) + sum(sb) sum(s) = 120 = 0 mod 30 sum(sa) + sum(sb) = 0 mod 30 sum(sa) = -sum(sb) mod 30 We have 32 numbers, 30 < 32, so they are not all distinct mod 30. then ?? (I am sure this could be useful, with the pigeonhole principle, but I don't know how to proceed from here) AlphaChapMtl |
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
Gerry

guest
|
Nov-24-08, 10:04 PM (EST) |
|
|
7. "RE: disjoint sets"
In response to message #0
| |
>Hey Alex, here is an interesting problem taken from 2001 >Israel Binational mathematics competition problem 6. > >You have 32 natural numbers such that: > >a_1 + a_2 + ...... + a_32 = 120 > >All a's belong to {1,2,3,4, .....,59,60} i.e. 1<= a_i <= 60 > >Prove you can find 2 disjoint collections of the 32 numbers, >such that the sum of the elements of one collection is equal >to the sum of the elements of the other. Are you sure you have the full statement of the problem? It seems much too easy. If any number appears twice, say, a_i = a_j for i > j, then your two disjoint collections are {a_i} and {a_j}. If the numbers are all distinct, then they add up to at least 1 + 2 + ... + 32 which is much greater than 120. |
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
 |
jay_shark
Member since Mar-20-07
|
Nov-25-08, 09:59 AM (EST) |
 |
8. "RE: disjoint sets"
In response to message #7
 |
>>Hey Alex, here is an interesting problem taken from 2001 >>Israel Binational mathematics competition problem 6. >> >>You have 32 natural numbers such that: >> >>a_1 + a_2 + ...... + a_32 = 120 >> >>All a's belong to {1,2,3,4, .....,59,60} i.e. 1<= a_i <= 60 >> >>Prove you can find 2 disjoint collections of the 32 numbers, >>such that the sum of the elements of one collection is equal >>to the sum of the elements of the other. > >Are you sure you have the full statement of the problem? It >seems much too easy. If any number appears twice, say, a_i = >a_j for i > j, then your two disjoint collections are {a_i} >and {a_j}. If the numbers are all distinct, then they add up >to at least 1 + 2 + ... + 32 which is much greater than 120. The two disjoint collections must partition the set of 32 numbers. That is, the two disjoint collections must each add up to 60.
|
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
 |
jay_shark
Member since Mar-20-07
|
Dec-08-08, 10:20 AM (EST) |
 |
9. "RE: disjoint sets"
In response to message #8
 |
We can prove easily that a sum of 30 or 60 can be attained. Let Si = <Sum k=1 to k=i> a_k by the pigeonhole principle,two of the Si's must be congruent mod30. For some i and j with 1<= i<j <=32 we have a_k+1 + a_k+2 + ... + a_j is a multiple of 30. Therefore it sums to 30,60 or 90. If it sums to 90, then taking the complement we get a subset which sums to 30. We conclude that a sum of 30 or 60 is attainable. |
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
 |
|
 |
jay_shark
Member since Mar-20-07
|
Dec-18-08, 02:26 PM (EST) |
 |
12. "RE: disjoint sets"
In response to message #11
 |
I will prove a more general statement. Given a set of n+2 integers that sums to 4n, and none of the integers exceeds 2n, then we can always find two disjoint sets each of which sums to 2n. Sol'n : I will proceed using mathematical induction. The statement is obviously true for n=1 and can be shown to be true for n=2. Moreover, for n=k=2 the result below can be shown to be true. That is, for n=k, given any set of k+2 integers that sums to 4k+3, we can always find a subset that sums to 2k+1; given any set of k+2 integers that sums to 4k+2, we can always find a subset that sums to 2k; given any set of k+2 integers that sums to 4k+1, we can always find a subset that sums to 2k-1. We need to prove that given a set of (K+1) + 2 integers that sums to 4(k+1), and none of the integers exceeds 2(k+1), then we can always find two disjoint sets each of which sums to 2(k+1) proof: If one of the integers is 2(k+1), then we're done. Additionally, if one of the integers is 2(k+1) - 1, then we're done since 2(k+1) - 1 + 2(k+2) = 4k+5 > 4k + 4 Therefore we can assume that all of the integers is less than or equal to 2*k. Since 4(k+1)/(k+1+2) < 4 for all values of k, then one of the (k+1) + 2 integers must be 1, 2 or 3. If it is 1, then of the remaining K+2 integers that are less than or equal to 2k, there is a subset that sums to 2k+1 If it is a 2, then of the remaining k+2 integers that are less than or equal to 2k, there is a subset that sums to 2k. If it is a 3, then of the remaining k+2 integers that are less than or equal to 2k, there is a subset that sums to 2k-1. We can check that 1 + 2k+1 = 2k+2, 2 + 2k= 2k+2 and 3+2k-1 = 2k+2 completing the induction.
|
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
 |
jay_shark
Member since Mar-20-07
|
Dec-19-08, 10:07 AM (EST) |
 |
13. "RE: disjoint sets"
In response to message #12
 |
> > >Moreover, for n=k=2 the result below can be shown to be >true. > >That is, for n=k, given any set of k+2 integers that sums to >4k+3, we can always find a subset that sums to 2k+1; given >any set of k+2 integers that sums to 4k+2, we can always >find a subset that sums to 2k; given any set of k+2 integers >that sums to 4k+1, we can always find a subset that sums to >2k-1. . Here is the problem. If the above is true for general k, then the problem is solved. I can't prove this in general. I'm optimistic that a proof by mathematical induction might work.
|
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|

You may be curious to have a look at the old CTK Exchange archive. Please do not post there.
Copyright © 1996-2009 Alexander Bogomolny
|
|