Proving Subset Sum Equality and Recursive Relations - Pigeonhole Problem Set

  • Thread starter andytran
  • Start date
  • Tags
    Set
In summary, the conversation includes a request for hints on a problem involving subsets and sums, and a discussion about the number of 5-subsets of a given set and their possible sums. The conversation ends with a clarification on the solution to the problem.
  • #1
andytran
41
0
Hi,

It was a big mistake leaving my assignment till the last minutes. Now I'm stuck on a few questions and got no where to turn to except the net.
Please do give any hints you may have..
Thank You!1. Let A subset {1,2,3,...,25} where |A| = 9. For any subset B of A let SB denote the sum of the elements in B. Prove that there are distinct subsets C, D of A such that |C|=|D|=5 and SC=SD.

2.Let R subset Z+ X Z+ (Z+ means positive int, and X means cross product) be the relation given by the following recursive definition.
1. (1,1) element of R; and
2. for all (a,b) element of R, the three ordered pairs (a+1,b), (a+1,b+1), and (a+1, b+2) are also in R.
Prove that 2a _> b for all (a,b) element of R.
 
Last edited:
Physics news on Phys.org
  • #2
How many 5-subsets of A are there? How small and how large could their sums possibly be?
 
  • #3
Muzza said:
How many 5-subsets of A are there? How small and how large could their sums possibly be?
the number of subset of A of length 5 is 126.

there smallest sum would be 1+2+3+4+5=17 and largest 25+24+23+22+21 = 115.
 
Last edited:
  • #4
What do you mean still clueless? You have 126 sets and only at most 98 possible sums and the thread is entitled pigeon hole principle.
 
  • #5
matt grime said:
What do you mean still clueless? You have 126 sets and only at most 98 possible sums and the thread is entitled pigeon hole principle.

I got it now, at first i thought the question requires you to take the number of combination of the set A in account.

thx
 
  • #6
1+2+3+4+5 is not 17, but it doesn't make a big difference.
 

1. What is the Pigeonhole principle and how does it relate to Subset Sum Equality?

The Pigeonhole principle states that if you have n boxes and n+1 objects to put into them, then at least one box must contain more than one object. This principle is used in the Subset Sum Equality problem, where we have a set of integers and we need to find if there exists a subset that sums up to a given target number. If we have more numbers in our set than the target number, then by the Pigeonhole principle, there must be at least one subset that sums up to the target number.

2. How can we prove Subset Sum Equality using the Pigeonhole principle?

To prove Subset Sum Equality, we can use the Pigeonhole principle in a constructive way. We can create n+1 boxes, where n is the number of integers in our set. Each box represents a possible subset of our set. We then place each integer into its corresponding box according to its value. If we have more numbers than our target number, then at least one box will have more than one integer. This means that the subset represented by that box will have a sum greater than our target number. Therefore, we can conclude that there exists a subset that sums up to our target number.

3. What is a recursive relation and how is it used in the Pigeonhole problem set?

A recursive relation is a mathematical relationship where a term in a sequence is defined in terms of previous terms. In the Pigeonhole problem set, we can use a recursive relation to find the sum of all the numbers in our set by breaking it down into smaller subsets. For example, we can find the sum of all the numbers in our set by adding the sum of the first half of the set to the sum of the second half of the set. This recursive relation allows us to efficiently find the sum of a large set of numbers.

4. How can we use the Pigeonhole principle to optimize the solution for the Subset Sum Equality problem?

The Pigeonhole principle can be used to optimize the solution for the Subset Sum Equality problem by reducing the search space. Instead of checking every possible subset, we can use the Pigeonhole principle to identify which subsets are worth checking. By dividing our set into smaller subsets, we can eliminate subsets that are guaranteed to have a sum greater than our target number. This can significantly reduce the time and resources needed to solve the problem.

5. Are there any other applications of the Pigeonhole principle in computer science?

Yes, the Pigeonhole principle has many applications in computer science, including data compression, hashing algorithms, and scheduling problems. In data compression, the principle is used to prove that there must be at least one string that is compressed to the same output as another string. In hashing algorithms, the principle is used to prove that there must be at least one collision when hashing a large number of values into a smaller set of values. In scheduling problems, the principle is used to prove that there must be at least one time slot where more than one task is scheduled, which can help optimize the schedule.

Similar threads

Prove every subset of countable set is either finite or else countable
    • Calculus and Beyond Homework Help
Replies
1
Views
503
Prove that every subset ##B## of ##A=\{1,...,n\}## is finite
    • Calculus and Beyond Homework Help
Replies
4
Views
495
Proving intersection of finitely many open sets is open
    • Calculus and Beyond Homework Help
Replies
1
Views
1K
Prove if ##a\cdot c = b \cdot c## then ##a = b## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
2
Views
266
Prove ##1 + a=s(a)=a+1## for ##a \in \mathbb{N}##
    • Calculus and Beyond Homework Help
Replies
1
Views
574
Is the set open, closed, neither, bounded, connected?
    • Calculus and Beyond Homework Help
Replies
7
Views
2K
Prove ##a \cdot 1 = a = 1 \cdot a## for ##a \in \mathbb{N}##
    • Calculus and Beyond Homework Help
Replies
1
Views
511
Prove ##a + b = b + a## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
3
Views
809
Prove ##(a+b)\cdot c=a\cdot c+b\cdot c## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
3
Views
516
Combinatorics: looking for an alternative solution
    • Calculus and Beyond Homework Help
Replies
7
Views
1K

Hot Threads

Recent Insights

Back
Top