CTK Exchange
CTK Wiki Math
Front Page
Movie shortcuts
Personal info
Awards
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Products to download and subscription Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "disjoint sets"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange College math Topic #701
Reading Topic #701
jay_shark
Member since Mar-20-07
Nov-03-08, 11:21 PM (EST)
Click to EMail jay_shark Click to send private message to jay_shark Click to view user profileClick to add this user to your buddy list  
"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

  Subject     Author     Message Date     ID  
disjoint sets jay_shark Nov-03-08 TOP
  RE: disjoint sets jay_shark Nov-21-08 4
     RE: disjoint sets jay_shark Nov-21-08 5
  RE: disjoint sets Pierre Charland Nov-24-08 6
  RE: disjoint sets Gerry Nov-24-08 7
     RE: disjoint sets jay_shark Nov-25-08 8
         RE: disjoint sets jay_shark Dec-08-08 9
             RE: disjoint sets alexb Dec-08-08 11
                 RE: disjoint sets jay_shark Dec-18-08 12
                     RE: disjoint sets jay_shark Dec-19-08 13
                         RE: disjoint sets alexb Dec-19-08 14
                         RE: disjoint sets alexb Dec-31-08 15
                             RE: disjoint sets jay_shark Feb-26-09 16

Conferences | Forums | Topics | Previous Topic | Next Topic
jay_shark
Member since Mar-20-07
Nov-21-08, 06:21 PM (EST)
Click to EMail jay_shark Click to send private message to jay_shark Click to view user profileClick to add this user to your buddy list  
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
jay_shark
Member since Mar-20-07
Nov-21-08, 07:49 PM (EST)
Click to EMail jay_shark Click to send private message to jay_shark Click to view user profileClick to add this user to your buddy list  
5. "RE: disjoint sets"
In response to message #4
 
Disregard the solution above.

I thought I had it but I guess not.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
Pierre Charland
Member since Dec-22-05
Nov-24-08, 09:11 AM (EST)
Click to EMail Pierre%20Charland Click to send private message to Pierre%20Charland Click to view user profileClick to add this user to your buddy list  
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)
Click to EMail jay_shark Click to send private message to jay_shark Click to view user profileClick to add this user to your buddy list  
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)
Click to EMail jay_shark Click to send private message to jay_shark Click to view user profileClick to add this user to your buddy list  
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
alexb
Charter Member
2336 posts
Dec-08-08, 03:10 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
11. "RE: disjoint sets"
In response to message #9
 
   You need only 31 number to claim that.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
jay_shark
Member since Mar-20-07
Dec-18-08, 02:26 PM (EST)
Click to EMail jay_shark Click to send private message to jay_shark Click to view user profileClick to add this user to your buddy list  
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)
Click to EMail jay_shark Click to send private message to jay_shark Click to view user profileClick to add this user to your buddy list  
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
alexb
Charter Member
2336 posts
Dec-19-08, 08:49 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
14. "RE: disjoint sets"
In response to message #13
 
   Prof. Gordon Walsh made this comment:

The 60/60 problem is quite interesting, but I don't know whether there's a short proof. I've more or less proved it by contradiction: obviously 60 can't be used, 59 can't be used (because at least one 1 is then required), 58 can't be used (because at least a 2 or two 1s are then required), 57 can't be used, etc., down to 4. Then 3, 2, 1 are obvious. Messy.

I'd say that a better argument may be to look for the largest integer.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
2336 posts
Dec-31-08, 00:17 AM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
15. "RE: disjoint sets"
In response to message #13
 
   Gordon Walsh also observed that, for 16 numbers that add up to 60, there may not be a subset with the sum of 30:

2*14 + 3 + 29 = 60.

Thus the induction can't possibly work.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
jay_shark
Member since Mar-20-07
Feb-26-09, 12:32 PM (EST)
Click to EMail jay_shark Click to send private message to jay_shark Click to view user profileClick to add this user to your buddy list  
16. "RE: disjoint sets"
In response to message #15
 
Here is a strategy that works.

Order the numbers from least to greatest.

a1<=a2<=a3<=...<=a32

Place a32 in set A and a31 in set B. If they are equal, then place a30 in set A. Otherwise if a32 and a31 are unequal, then we place a30 in set B and we continue adding elements to set B until the sum of the elements is greater than or equal to set A. Once this occurs, we continue adding elements to set A and the process is continued.

First we need to show that if the sum of the elements of A is S, then the sum of the elements from set B cannot jump from something less than S to something greater than 60 for 30 <= S <= 57

since (61 + S)/(61 - S) + 120 - (61 + S) < 32

This shows that the sum of the elements in either set must eventually reach 57. We can eliminate 58-62 since this would imply that the sum of the 32 numbers is at least
4*32 > 120, a contradiction. Therefore we can conclude that the game will terminate with the score 59-61 or 60-60.

WLOG, suppose set B is 61 and set A is 59.

RTP : We can always find a subset from set B that adds to k+1 and a subset from set A that adds to k for 2 <= k <= 57

Proof: Suppose the above claim is untrue.

case 1: The score is 58-58 and the last two elements are 3 and 1 making the final score 59-61. Retracing our steps backwards we sum the elements from least to greatest such that the sum of the 32 numbers is a minimum. Of course, without the above restrictions the sum of these numbers must add to 120. To minimize the sum of these elements we require one selection from set A, then another selection from set B, then another from set A and so on until we have 16 members in each set.

The sum of the 32 numbers must be at least 1 + 3*19 + 4 + 6*11 > 120, a contradiction.

case 2: The score is 59-58 and the last element is a 3 making the final score 59-61. As before, we find a lower bound for the sum of these numbers which occurs when we've selected 16 members in each set. The sum of the 32 numbers must exceed 120 which we can verify since

3*19 + 4 + 5*12 > 120

case 3: The score is 59-59 and the last element is a 2. The sum of the 32 numbers must be at least

2*29 + 3 + 30*2 > 120, a contradiction.

In all three cases we've reach a contradiction which shows that a trade off must occur to reach 60-60. Simply take the sum of the elements from set B that adds to k+1 and trade it to set A for the sum of the elements from A that adds to k.

--------------------------------------------------------------------------------


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

Copyright © 1996-2018 Alexander Bogomolny

Search:
Keywords:

Google
Web CTK