Using the mathod of mathematical induction

Click For Summary
SUMMARY

The discussion centers on proving that any ten-element set of positive integers ranging from 1 to 99 contains two disjoint subsets A and B with equal sums. This problem utilizes the pigeonhole principle rather than mathematical induction. Participants emphasize the importance of calculating the number of possible subsets and the range of sums achievable with the selected integers. The conclusion is that the pigeonhole principle guarantees the existence of such subsets due to the limited range of sums compared to the number of subsets.

PREREQUISITES
  • Pigeonhole principle
  • Subset sum problem
  • Basic combinatorics
  • Understanding of positive integers
NEXT STEPS
  • Study the pigeonhole principle in depth
  • Explore the subset sum problem and its applications
  • Learn about combinatorial counting techniques
  • Investigate properties of positive integers and their distributions
USEFUL FOR

Mathematics students, educators, and anyone interested in combinatorial proofs and number theory will benefit from this discussion.

cocobaby
Messages
9
Reaction score
0

Homework Statement


Let H be a ten- element set of potive integers ranged from 1 to 99. Prove that H has two disjoint subsets A and B so that the sum of the elements of A is equal to the sum of the elements of B.
 
Physics news on Phys.org
This is a pigeonhole question, not an induction question.
hint:

If you have 10 different numbers, how many different ways can you choose a subset of them? (to make a sum)and also,

what is the range of answers you can possibly get? (numbers chosen from 1-99 and up to a maximum of 10 numbers)
 

Similar threads

[L'Hospital's Rule] Can I Use Mathematical Induction to Prove This?
  • · Replies 6 ·
Replies
6
Views
2K
Using the method of mathematical induction
  • · Replies 1 ·
Replies
1
Views
3K
Do these two statements imply an underlying induction proof?
  • · Replies 7 ·
Replies
7
Views
1K
Proof by mathematical induction
  • · Replies 4 ·
Replies
4
Views
2K
Prove every subset of countable set is either finite or else countable
  • · Replies 1 ·
Replies
1
Views
2K
Strong Induction: Proving Every Int n>1 is a Product of Primes
  • · Replies 5 ·
Replies
5
Views
2K
Is the Empty Set an Inductive Set?
  • · Replies 2 ·
Replies
2
Views
5K
Undergrad Use of induction in the proof of the Chinese Remainder Theorem
  • · Replies 7 ·
Replies
7
Views
3K
Proofs By Induction: Proving P(n) for All n
  • · Replies 3 ·
Replies
3
Views
2K
Prove that every subset ##B## of ##A=\{1,...,n\}## is finite
  • · Replies 4 ·
Replies
4
Views
1K